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
Ahoj, nejdřív napíšu zadání, pak svůj postup. Nejsem si v něm ale příliš jistý, a tak prosím o odbornou kontrolu.
Zadání: "Dokažte, že graf je bipartitní právě tehdy, když neobsahuje lichou kružnici."
Můj postup: Důkaz sporem: Předpokládám, že existuje bipartitní graf obsahující jednu lichou kružnici. Tato lichá kružnice bude jeho podgraf, nazvaný:
Tento podgraf není bipartitní, protože se jeho vrcholy nedají rozdělit na disjunktní podmnožiny, tj.:
^
A proto tento podgraf znemožňuje, aby byl celý graf bipartitní => graf není bipartitní (SPOR)
Děkuji za kontrolu.
Offline
1) Lichá kružnice nemusí nutně mít tři vrcholy. Může jich mít pět. Může jich mít 45008483.
Šel bych na to tak, že bych tu lichou kružnici vzal, a házel vrcholy střídavě do první nebo druhé partity – první vrchol bude patřit do první partity a poslední bude patřit do druhé – jenže poslední a první vrchol jsou spojené hranou.
2) Máš dokázat ekvivalenci. Pokusil ses dokázat ale jenom jednu implikaci – pokud G je bipartitní, pak neobsahuje lichou kružnici – to je jedna půlka toho, co potřebuješ dokázat. Navíc ale ještě musíš dokázat, že pokud G neobsahuje lichou kružnici, pak je G bipartitní.
Offline