#1 18. 02. 2010 19:40
Grafy s lichou kruznici
Zadani: Popište všechny grafy, které obsahují pouze kružnice liché délky.
Me reseni:
Vychazim z toho, ze bipartitni graf neobsahuje kruznoici liche delky. Tedy graf, ktery obsahuje kruznici liche delky nelze rozdelit na dve disjunktni mnoziny.
Napada vas neste neco?
Offline
#2 18. 02. 2010 19:44
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Grafy s lichou kruznici
Ano, takové grafy nebudou bipartitní. Ale důlržité je tam to slovo pouze. Např. graf 
není bipartitiní a přitom obsahuje kružnici délky 3.
Pomůže když ukážeme, že žádné dvě kružnice nemohou mít společnou hranu. Pak je jasné, jak budou hledané grafy vypadat.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#4 18. 02. 2010 20:11
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Grafy s lichou kruznici
Jakmile to pomocné tvrzení bude dokázané, tak víme, že mezi kažými dvěma kružnicemi je hrana, hledaný graf proto vznikne ze stromu, v němž vrcholy nahradíme kružnicemi.
K pomocnému tvrzení: mějme dvě kružnice liché délky, pro spor předpokládejme, že mají společnoou hranu. Mohou mít těch hran společných víc, proto musíme vzít dva body u,v tak, že leží na obou kružnicích a vhodně zvolené dva úseky z u do v obou kružnic jsou hranově disjunktní. Nyní máme body u,v spojeny čtyřmi cestami, že dvě cesty dají kružnici sudé délky je trenink na Dirichletův/holubníkový princip.
BRKOS - matematický korespondenční seminář pro střední školy
Offline