Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 26. 07. 2021 17:10

dugbutabi
Příspěvky: 183
Reputace:   
 

Eulerovský graf

Dobrý den, prosím o pomoc s tímto příkladem.

Je graf $K_{(5,5)}$ eulerovský?

Pokud není eulerovský, jaký nejmenší počet hran k bychom museli do grafu přidat, aby vznikl eulerovský graf?


Mé řešení:

Graf $K_{(5,5)}$ nakreslím jako úplný bipartitní graf s 10 vrcholy - vrcholy rozdělím na dvě disjunktní množiny a každý vrchol z první množiny spojím hranou s každým vrcholem z druhé množiny.

https://www.google.com/imgres?imgurl=ht … egUIARDcAQ

- graf eulerovský není, protože vrcholy nejsou sudého stupně. Každý vrchol je pátého stupně.

Ale nemůžu přijít na to, kam hrany přidat, aby byl každý vrchol sudého stupně. Děkuji za každou radu.

Offline

  • (téma jako vyřešené označil(a) dugbutabi)

#2 26. 07. 2021 17:33 — Editoval laszky (29. 07. 2021 23:17)

laszky
Příspěvky: 2130
Škola: MFF UK, FJFI CVUT
Reputace:   187 
 

Re: Eulerovský graf

↑ dugbutabi:

Ahoj, vzhledem k tomu, ze hrany muzes pridavat vzdy jen v ramci jedne mnoziny vrcholu a kazda mnozina obsahuje lichy pocet vrcholu licheho stupne, zustane v kazde mnozine po pridani libovolneho poctu hran vzdy lichy pocet vrcholu licheho stupne. A protoze je nula sude cislo...

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson