5 svar
157 visningar
Dani163 1035
Postad: 19 okt 2023 08:25 Redigerad: 19 okt 2023 08:28

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 K5K_5 ä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) K5K_5 ä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 n/2=2.5\geq n / 2=2.5 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 "n2=2.5\geq \frac{n}{2} = 2.5" 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å?

Laguna Online 30721
Postad: 19 okt 2023 12:36

K5 betyder den kompletta grafen med fem hörn.

Dani163 1035
Postad: 24 okt 2023 14:56
Laguna skrev:

K5 betyder den kompletta grafen med fem hörn.

Okej men det var inte det jag undrade.

Laguna Online 30721
Postad: 24 okt 2023 15:13

Du undrade "var ser de 5 hörn"? Tydligen missförstod jag frågan.

Dani163 1035
Postad: 24 okt 2023 15:18 Redigerad: 24 okt 2023 15:19
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.

 

Laguna Online 30721
Postad: 24 okt 2023 15:45

Bilden hör till b. Det är i a det står om K5.

Svara
Close