Matematické Fórum

Makrofág · 21. 11. 2013 21:16

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 $G(V, E)$ 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ý: $G_{p}(V_{p}, E_{p}) ; |V_{p}| = |E_{p}| = 3$

Tento podgraf není bipartitní, protože se jeho vrcholy nedají rozdělit na disjunktní podmnožiny, tj.:

$V_{p} = X_{p} \cup Y_{p} : \text{neexistuje }a, b \in X_{p}\text{ tak, že } \{a, b\}\in E$

^

$\text{neexistuje }a, b \in Y_{p}\text{ tak, že } \{a, b\}\in E$

A proto tento podgraf znemožňuje, aby byl celý graf bipartitní => graf není bipartitní (SPOR)

Děkuji za kontrolu.

Oxyd · 22. 11. 2013 00:57

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í.

Matematické Fórum

#1 21. 11. 2013 21:16

Bipartitní graf

#2 22. 11. 2013 00:57

Re: Bipartitní graf

Zápatí