Rita en enkel graf och ange sedan en Eulerväg (Grafteori)
Om du har ett antal noder där vardera nods gradtal är givet (2 noder med udda gradtal och resterande noder med jämna gradtal), och du skall rita en enkel graf med denna givna information ( (Med enkel graf menas att varje par av noder bara får ha en väg som binder dem samman). Är enda alternativet att testa sig fram eller finns någon strategi för att lösa detta problem på snabbast möjliga vis? Har försökt hitta information om detta men har inte lyckats.
Som du har definierat enkel graf så låter det som att du menar ett träd? Sedan om grafen är given så är det väl inga problem att rita den? Eller var stöter du på problem?
Stokastisk skrev :Som du har definierat enkel graf så låter det som att du menar ett träd? Sedan om grafen är given så är det väl inga problem att rita den? Eller var stöter du på problem?
Såhär lyder uppgiften: "Rita en enkel graf med 8 noder där gradtalen hos noderna är 2, 2, 3, 4, 4, 5, 6, 6.". Längst ner har jag bifogat hur en sådan graf kan se ut enligt facit, och i mina ögon ser det inte ut som ett träd. 
Aha, var nog lite seg från början, tror jag insåg vad du menade vad problemet är nu. Nej det där är inte ett träd, jag tror du måste kolla upp definitionen på vad en enkel graf är, den du har skrivit stämmer inte. Om du tänker att den ska vara oriktad så blir det missvisande att säga att det bara ska vara en väg mellan dem, eller så tänker du på att det bara ska vara en enda kant mellan dem, då blir det också missvisande att säga att det ska vara en väg mellan dem.
Det du kan göra är att ta den nod med högst grad, ansluta den till alla min lika eller lägre grad (gå i storleksordning), sedan är denna nod "färdig". Så efter det börjar du om, ta den nod bland de som inte är färdig och har högst grad och anslut den till de som har lika eller lägre grad.
Stokastisk skrev :Aha, var nog lite seg från början, tror jag insåg vad du menade vad problemet är nu. Nej det där är inte ett träd, jag tror du måste kolla upp definitionen på vad en enkel graf är, den du har skrivit stämmer inte. Om du tänker att den ska vara oriktad så blir det missvisande att säga att det bara ska vara en väg mellan dem, eller så tänker du på att det bara ska vara en enda kant mellan dem, då blir det också missvisande att säga att det ska vara en väg mellan dem.
Det du kan göra är att ta den nod med högst grad, ansluta den till alla min lika eller lägre grad (gå i storleksordning), sedan är denna nod "färdig". Så efter det börjar du om, ta den nod bland de som inte är färdig och har högst grad och anslut den till de som har lika eller lägre grad.
Jag menade kant när jag skrev väg :) Testade nyligen den strategi du beskrev och det verkar fungera. Tack :)
Om jag nu skall rita in en Eulerväg i denna graf, så vet jag att jag skall börja på den ena noden med udda gradtal, och sedan sluta på den andra noden med udda gradtal, men vad finns det för strategi att tillämpa mellan start och mål för att rita en eulerväg utan att behöva testa sig fram?
Strategin man kan använda är ungefär samma som man kan använda för att bevisa att det existerar en Eulerväg.
Börja med att bara dra en väg så långt du kan, som startar i ena av de udda noderna. Sedan om du saknar någon kant i denna, ta en som sitter längs din befintliga väg. Börjar du en väg där och drar den så långt du kan (denna måste sluta i samma nod som du började den), så du kommer kunna länka in denna väg i din tidigare väg, nu har du en längre väg. Detta fortsätter du med tills alla kanter är med i vägen.
Stokastisk skrev :Strategin man kan använda är ungefär samma som man kan använda för att bevisa att det existerar en Eulerväg.
Börja med att bara dra en väg så långt du kan, som startar i ena av de udda noderna. Sedan om du saknar någon kant i denna, ta en som sitter längs din befintliga väg. Börjar du en väg där och drar den så långt du kan (denna måste sluta i samma nod som du började den), så du kommer kunna länka in denna väg i din tidigare väg, nu har du en längre väg. Detta fortsätter du med tills alla kanter är med i vägen.
Stort tack! :)
