Matematické Fórum

slender · 07. 02. 2016 12:23

Zdravím,
mám v poznámkách z teorie grafů následující větu:

$\text{Graf }G\text{ je eulerovský, právě když má všechny stupně sudé a po odstranění}\nl\text{izolovaných vrcholů (vrcholů stupně 1) zbyde souvislý graf.}$
A pod tím takovýto příklad:
//forum.matweb.cz/upload3/img/2016-02/44093_graf.png

Nemají náhodou izolované vrcholy stupeň 0?

Předem díky...

byk7 · 07. 02. 2016 14:34

Tak si říkám, jestli jsi neudělal chybu v poznámkách. :-) Samozřejmě, že izolované vrcholy jsou stupně nula.

Ale zajímalo by mě, jak jste si definovali eulerovský graf. Já to znám tak, že nutná podmínka pro eulerovskost (multi)grafu je souvislost.

slender

↑ byk7: Dobrý, díky. :)

No, definovali jsme si to jako graf, ve kterém existuje uzavřený eulerovský tah. Eulerovský tah jsme definovali jako tah, který obsahuje všechny hrany. Uzavřený tah jsme pak definovali jako tah, který začíná a končí na tomtéž vrcholu.

Podle té definice by tedy eulerovský graf mohl kromě souvislé komponenty obsahovat právě tyhle izolované vrcholy.

EDIT: Tu větu jsem si opsal z poznámek přednášejícího (str. 46), právě proto mě to zarazilo a radši jsem se zeptal. :)

Matematické Fórum

#1 07. 02. 2016 12:23

Věta o charakteristice eulerovských grafů

#2 07. 02. 2016 14:34

Re: Věta o charakteristice eulerovských grafů

#3 07. 02. 2016 14:39 — Editoval slender (07. 02. 2016 14:41)

Re: Věta o charakteristice eulerovských grafů

Zápatí