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
Stránky: 1
- Hlavní strana
- » Vysoká škola: úvod do studia
- » Teorie grafu-důkaz (TOTO TÉMA JE VYŘEŠENÉ)
#1 17. 11. 2009 14:58
Teorie grafu-důkaz
Ahoj není si někdo rady s tímto příkladem? Vůbec netuším jak na to. Díky
Mějme graf G. Doplněk (komplement) grafu G značíme G' a platí V(G) = V(G'), E(G') = { xy : xy ∉ E(G) } pro každé dva vrcholy x,y ∈ V(G). Dokažte, že pokud |V(G)|≥6, pak G nebo G' obsahuje cyklus délky 3.
Offline
#2 17. 11. 2009 15:25
Re: Teorie grafu-důkaz
Sporem. Každá dvojice vrcholů { x, y } je hrana buď v G nebo v G' (ale ne v obou zároveň) -- takže každý vrchol G je pokryt hranou buď z G nebo z G'. Kdyby jak G tak G' obsahovaly cyklus délky nejvýš 2, tak G může mít nejvýš 4 vrcholy (jinak by musel existovat vrchol, který není obsažen ani v hraně z G ani v hraně z G'), což je spor.
Mýlím se častěji, než bych chtěl. Pokud vám v mém příspěvku něco nehraje, neváhejte se zeptat.
Jsem stále mlád a je mi příjemnější tykání. :)
Offline
#4 17. 11. 2009 15:53
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Teorie grafu-důkaz
↑ Oxyd:A proč tam není cyklus délky 4 a víc? Co je to cyklus délky 2 (když nejsme v multigrafu ani orientovaném grafu)? Možná hloupé dotazy, ale asi tomu nerozumím ...
Moje řešení:
Sporem. Z vrcholu V1 vede v 
|V(G)|-1>4 hran, proto jsou buď 3 z nich v G nebo 3 z nich v G'. Předpokládejme první možnost, tj. V1 je v G spojen s V2,V3 a V4. Aby nebyl v G trojúhelník (cyklus délky 3), nemůže být v G už žádná z hran mezi vrcholy V2,V3,V4. Všechny tři hrany mezi nimi jsou v G' => v G' je trojúhelník => spor.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#5 17. 11. 2009 16:22 — Editoval Oxyd (17. 11. 2009 16:25)
Re: Teorie grafu-důkaz
Kondr napsal(a):
↑ Oxyd:A proč tam není cyklus délky 4 a víc? Co je to cyklus délky 2 (když nejsme v multigrafu ani orientovaném grafu)? Možná hloupé dotazy, ale asi tomu nerozumím ...
To je ze zadání. Cyklus délky tři chápu ve smyslu "délky alespoň tři" (jinak bych tam chtěl slyšet "cyklus délky právě tři"). A délkou cyklu rozumím počet vrcholů, které obsahuje.
Edit: Ale asi máš pravdu, protože cyklus délky alespoň tři nedává moc smyslu, že? To by kružnice na čtyřech vrcholech obsahovala trojúhelník. Svedu to na nedostatek čaje.
Mýlím se častěji, než bych chtěl. Pokud vám v mém příspěvku něco nehraje, neváhejte se zeptat.
Jsem stále mlád a je mi příjemnější tykání. :)
Offline
#6 26. 11. 2009 12:26
Re: Teorie grafu-důkaz
(rezervace řešení skupiny majsla) Sjednocením grafu a doplňku ke grafu dostaneme úplný graf, postupně budeme dosazovat do grafu (a do jeho doplňku) hrany tak, aby se nemohl vytvořit cyklus délky tři 14 hran projde touto podmínkou, ale poslední hrana nemůže být ani v grafu, ani v jeho doplňku, tedy to je ve sporem, že je graf úplný.........
Smutné je, že hlupáci jsou tak sebejistí, zatímco moudří lidé jsou vždy plní pochybností.“ — Bertrand Russell
Offline
Stránky: 1
- Hlavní strana
- » Vysoká škola: úvod do studia
- » Teorie grafu-důkaz (TOTO TÉMA JE VYŘEŠENÉ)