Grafteori

Et hjørne af ulige grad må enten være startpunkt eller slutpunkt for turen (hvorfor?). Hvor mange hjørner har ulige grad?

Det er et selvlæst emne vi er igang med, og jeeg følger en pdf. fil vi har fået som vi skal følge (teori/øvelser/opgaver). Indtil nu har der ikke stået noget med ulige grad, ikke andet end at hvert hjørne har en bestemt grad. 

Men tænker, at hjørnerne E, F og B har grad 3 som er ulige; så de har flest kombinationsmuligheder?

Antag at der fandtes en tur, hvor alle kanter blev besøgt netop én gang, og lad være en af de hjørner, hvor turen hverken starter eller slutter. Hvis vi på turen besøger en gang, så må graden af dette hjørne være 2, da vi kommer ind til ad en kant, og forlader ad en anden kant. Hvis vi besøger to gange, så må graden være fire, da vi ved første besøg kommer ind ad en kant og forlader ad en anden kant og ved andet besøg kommer ind ad en tredje kant og forlader ad en fjerde kant. Alment gælder der, at hvis antallet af gange, vi besøger , er , så er graden af dette hjørne .

For at der skal findes en tur, hvor alle kanter bliver besøgt netop én gang, skal graden være lige for alle hjørner, hvor vi ikke starter eller slutter. Graden af de to sidste hjørner kan enten begge være lige (så starter og slutter vi i det samme hjørne) eller begge ulige (så starter og slutter vi i to forskellige hjørner).

I den aktuelle opgave er der tre hjørner af grad 3 og et hjørne af grad 5. Derfor findes der ikke en tur, hvor alle kanter bliver besøgt netop én gang. Men hvis vi fjerner kanten mellem to hjørner af ulige grad, så får disse to hjørner lige grad, og så er der kun to hjørner tilbage med ulige grad. Prøv om du kan lave en tur, der starter i det ene af disse hjørner med ulige grad og slutter i det andet.

Tak for hjælpen og undskyld for det sene svar! 

Jeg fandt ud af, at vi skulle fjerne kanten EF og kan derfor lave turen: A-D-E-A-F-B-A-C-A