Euler/Hamiltongraf
Hej!
jag har en fråga som lyder: G är en öglefri graf med 11 noder och 53 bågar. Visa att G är en hamiltongraf men inte en eulergraf.
Man skulle ju kunna testa att rita den men då man inte vet graden blir väl det lite omständigt, så jag tänker om någon vet hur man lättast går tillväga.
Anm: Jag misstänker att det borde finnas några fler kriterier såsom att grafen är sammanhängande men lämnandes det åt sidan.
Då Euler-egenskapen och Hamilton-egenskapen inte är intimt relaterade kan de i alla fall inledningsvis hanteras som separata problem
Inom grafteori är det ofta enklare att visa att något inte har en egenskap än att det har det så vi börjar med Euler-egenskapen. En möjlighet vore såklart att rita alla öglefria grafer med 11 noder och 53 bågar och experimentellt fastställa att de saknar egenskapen men vi sparar det som en sista utväg.
De första man gör när man angriper ett nytt problem är att fundera på om man tidigare löst ett relaterat eller analogt problem. Har vi stött på grafer utan Eulervägar tidigare...? Königsbergs broproblem var ju ett problem med en graf utan eulervägar så låt oss se om det finns någon inspiration att hämta där.
Resultatet där var ju att om en graf har fler än två noder med ett udda antal bågar så finns ingen eulerväg. Okej, går det att använda här? Vi har ju inget om nodernas grader men kan vi säga något om graderna? Om inget annat så kan vi ju dela upp alla V = 11, E = 53-grafer i två klasser; de med fler än 2 noder med udda antal bågar och de med 0,1 eller fler än 2 och endast rikta uppmärksamhet mot de senare då de första garanterat har eulerkanter.
Fundera kring möjligheterna för nodernas grader.
- Om hamiltonvägar. Gällande Hamiltonvägar så brukar standardsatserna för existens vara lite mer obskyra. Har du stött på något tidigare problem där man visade existensen hos en Hamitlonväg utan explicit hänvisning till grafens form?
En första magkänsla är att det är väldigt många bågar i förhållande till antalet noder. Kolla om den magkänslan stämmer: hur långt ifrån en komplett graf är vi? Med det resultatet blir det ganska lätt att resonera kring Hamiltonvägar
SeriousCephalopod skrev:Anm: Jag misstänker att det borde finnas några fler kriterier såsom att grafen är sammanhängande men lämnandes det åt sidan.
Då Euler-egenskapen och Hamilton-egenskapen inte är intimt relaterade kan de i alla fall inledningsvis hanteras som separata problem
Inom grafteori är det ofta enklare att visa att något inte har en egenskap än att det har det så vi börjar med Euler-egenskapen. En möjlighet vore såklart att rita alla öglefria grafer med 11 noder och 53 bågar och experimentellt fastställa att de saknar egenskapen men vi sparar det som en sista utväg.
De första man gör när man angriper ett nytt problem är att fundera på om man tidigare löst ett relaterat eller analogt problem. Har vi stött på grafer utan Eulervägar tidigare...? Königsbergs broproblem var ju ett problem med en graf utan eulervägar så låt oss se om det finns någon inspiration att hämta där.
Resultatet där var ju att om en graf har fler än två noder med ett udda antal bågar så finns ingen eulerväg. Okej, går det att använda här? Vi har ju inget om nodernas grader men kan vi säga något om graderna? Om inget annat så kan vi ju dela upp alla V = 11, E = 53-grafer i två klasser; de med fler än 2 noder med udda antal bågar och de med 0,1 eller fler än 2 och endast rikta uppmärksamhet mot de senare då de första garanterat har eulerkanter.
Fundera kring möjligheterna för nodernas grader.
- Om hamiltonvägar. Gällande Hamiltonvägar så brukar standardsatserna för existens vara lite mer obskyra. Har du stött på något tidigare problem där man visade existensen hos en Hamitlonväg utan explicit hänvisning till grafens form?
Jag hittade också det där med att max två udda noder kan finnas. Men hur bevisar jag att det måste finnas det? Kan det inte exempelvis finnas typ 5 noder som har grad 8, 5 noder med grad 2 och sedan en nod med grad 3. Då finns ju bara en med udda antal grader.
Var sent på kvällen så jag citerade en mening på wikisidan ganska rakt av men inser nu att meningen var fel i det avseendet att den utelämnar fallet med grafer som endast en nod med udda grad vilket är typen av fall som du konstruerat. Var alltså fel på svenska wikipedia och jag var slarvig...
Korrektare formulering: En graf saknar eulervägar om antalet noder med udda grad är annat än 0 eller 2. (Fallet med en enda nod med udda grad kan inte producera eulervägar)
Idén kommer någonstans ifrån att noder med udda grad måste agera antingen som startpunkter eller slutpunkter i en eulerväg men där en och samma nod inte kan fylla båda roller. Exempelvis för en startnod så rör man sig först ut från noden gånger, in till noden lika många gånger och slutligen lämnar noden en sista gång (1 gång) med ett totum av använda vägar. Notera dock att startnoden i sådana fall inte kan agera slutnod eftersom man efter att ha lämnat noden nu inte kan ta sig tillbaka en sista gång samtidigt som vägen måste terminera någonstans och inte kan göra det vid jämna noder, så för att det ska finnas en eulerväg så måste det finnas en till nod med udda grad där vägen kan terminera; så du kan ha eulervägar med 2 udda noder men inte med 1 udda nod.
En graf med 5 noder med grad 8, 5 noder med grad 2 och en nod med grad 3, kan enligt denna formulering inte ha eulervägar.
Fortsätt därifrån.
