#1 23. 05. 2010 18:36
- PřejetejVlak
- Zelenáč
- Příspěvky: 11
- Reputace: 0
Cesty na obarveném grafu
Zdravím, potřeboval bych poradit s jednou úlohou, vůbec nevím, co s ní.
Hrany grafu K7(úplný graf na 7 vrcholech) jsou obarveny červeně a modře. Dokažte, že v tomto K7 můžeme najít buď modrý trojůhelník nebo červenou cestu na třech vrcholech(ne nutně indukovanou).
Díky moc.
Offline
#2 24. 05. 2010 22:43
Re: Cesty na obarveném grafu
↑ PřejetejVlak:Já bych začal od té cesty.
Když v grafu je červená cesta, jsme hotovi.
Když ne, tak najdeme tři nezávislé vrcholy v "červeném grafu" (rozebrat možnosti). No a to odpovídá něčemu v modrém grafu...
Offline
#3 24. 05. 2010 23:36 — Editoval Kondr (25. 05. 2010 10:44)
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Cesty na obarveném grafu
Včera mě napadlo toto: uvážíme libovolný vrchol. Když z něj vedou dvě červené cesty, jsme hotovi. Když tři modré, také. Ale nejde mi do hlavy proč zrovna K7, když tohle funguje už od EDIT: K5 ...
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#4 25. 05. 2010 09:30
- PřejetejVlak
- Zelenáč
- Příspěvky: 11
- Reputace: 0
Re: Cesty na obarveném grafu
↑ Kondr: No, ale to asi není moc formální důkaz. Já mám takový pocit, že by se na to nějak dala použít Ramseyova věta pro obarvené grafy, která říká, jaký je minimální počet n u Kn, aby obsahoval jednobarevný podgraf, tady K3.
Offline
#5 25. 05. 2010 09:43
Re: Cesty na obarveném grafu
↑ PřejetejVlak:Každý podgraf 
obsahuje i cestu na třech vrcholech, že?
Offline
#6 25. 05. 2010 09:49 — Editoval petrkovar (25. 05. 2010 09:52)
Re: Cesty na obarveném grafu
↑ Kondr:Vememe-li na 
modré 
a dvě nezávislé červené hrany, tak máme protipříklad.
Začal bych od 
, kde funguje (pěkná!) argumentace s počtem modrých a červených hran z libovolného vrcholu.
Offline
#7 25. 05. 2010 10:45
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Cesty na obarveném grafu
↑ petrkovar: Díky. Budu se muset naučit počítat do pěti.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#8 25. 05. 2010 11:15
- PřejetejVlak
- Zelenáč
- Příspěvky: 11
- Reputace: 0
Re: Cesty na obarveném grafu
↑ petrkovar: Ok, tak já to takhle vyzkouším. A ten modrý K3 pomocí Ramseyovy věty by šel?
Offline