Matematické Fórum

vytautas · 19. 12. 2015 17:09

Zdravím

mám problém s príkladom: Ak graf G je eulerovský, dokážte, že neobsahuje most.

skúšal som to sporom, respektíve obmenou, no nedostal som sa k výsledku.

za každú radu ďakujem .

Freedy · 19. 12. 2015 17:41

Ahoj,

tak sporem.
Pokud by graf G obsahoval most, (označím m), potom $G-m$ je nesouvislý.
Uvažme tedy komponenty $G_1$ a $G_2$ , které vzniknou odebráním hrany m z $G$ .
Graf je eulerovský, právě když má všechny stupně sudé.
Graf G má tedy všechny stupně sudé. Označme $v_1$ vrchol z $G_1$ a $v_2$ vrchol z $G_2$ tak, že mezi těmito vrcholy vedla hrana m. Po odebrání této hrany mají všechny vrcholy mimo $v_1$ v komponentě $G_1$ sudý stupeň a vrchol $v_1$ stupeň lichý. Což ale není možné, protože součet stupňů v každém grafu se rovná dvojnásobku počtu hran. Je to tedy číslo sudé, ale součet sudých čísel + 1 lichého je číslo liché.
Hrana m tedy nemohla být mostem.

vytautas · 19. 12. 2015 18:54

↑ Freedy:

jasné, nenapadlo mi použiť Handshaking Lemma. Ďakujem.

Matematické Fórum

#1 19. 12. 2015 17:09

teória grafov

#2 19. 12. 2015 17:41

Re: teória grafov

#3 19. 12. 2015 18:54

Re: teória grafov

Zápatí