Förståelse av Eulergrafer, Hamiltongrafer och Ores sats
Jag har stött på en uppgift som jag verkligen behöver hjälp med att förstå och skulle uppskatta om någon kunde gå igenom lösningen och förklara vissa delar för mig. Uppgiften handlar om grafteori och specifikt om Eulergrafer och Hamiltongrafer.
Uppgiften lyder som följer:
7. a) Motivera om är eller inte är en Eulergraf eller en Hamiltongraf.
b) Motivera om följande graf är eller inte är en Eulergraf eller en Hamiltongraf:Lösning:
a) är en komplett graf med 5 hörn. I en komplett graf med 5 hörn har alla hörn graden 4, dvs jämnt gradtal, vilket betyder att det finns en Euler cykel och grafen är därmed en Eulergraf. Med hjälp av följdsatsen till Ores sats så är gradtalet för alla hörn vilket innebär att grafen har en Hamiltoncykel och är därmed en Hamiltongraf.
Här är var jag stöter på problemet. Vart ser de 5 hörn? Hur kommer de fram till att "alla hörn har graden 4 i en komplett graf med 5 hörn"?
Jag förstår heller inte riktigt hur följdsatsen till Ores sats tillämpas, och vad "" betyder, och hur det är relaterat till att säkerställa att grafen är en Hamiltongraf. Kan någon förklara detta steg för mig?
b) Då två hörn har udda gradtal så är grafen inte en Eulergraf. Däremot är summan av två icke närliggande hörns gradtal ≥ antal hörn i grafen. Därmed har grafen en Hamiltoncykel och är därmed en Hamiltongraf.
Jag är också förvirrad över varför grafen inte är en Eulergraf när två hörn har udda gradtal, eller när summan av två icke närliggande hörns gradtal ≥ antal hörn i grafen. Kan någon gå igenom detta steg med mig och hjälpa mig att förstå?
K5 betyder den kompletta grafen med fem hörn.
Laguna skrev:K5 betyder den kompletta grafen med fem hörn.
Okej men det var inte det jag undrade.
Du undrade "var ser de 5 hörn"? Tydligen missförstod jag frågan.
Laguna skrev:Du undrade "var ser de 5 hörn"? Tydligen missförstod jag frågan.
Ja men i bilden är det inte 5 hörn så är det något jag missar här eller har de gjort fel i uppgiften?
Jag tolkar en hörn som de blåa cirklarna eller noder på grafen. Jag ser totalt fyra, om inte man syftar på antalet bågar, vilket är fem.
Vidare så ser jag inte hur någon av noderna har graden 4, snarare har två utav dessa graden 2 och andra två har graden 3. Där "grad" tolkas som antalet "förbindelsevägar" med andra noder.
Bilden hör till b. Det är i a det står om K5.