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
#1 22. 04. 2010 21:27
Perfektní párování v bipartitním grafu
Zdravím, už delší dobu si lámu hlavu nad tímto:
Mějme bipartitní graf s 2n vrcholy, kde každá partita je velikosti n.
a) Dokažte, že pokud minimální stupeň G je alespoň n/2, pak G obsahuje perfektní párování.
b) Stačilo by, kdyby minimální stupeň G byl alespoň n/2 − 1?
Nějak mi nejde na rozum, když při perfektním párování je stupeň každého vrcholu = 1, jak by potom mohlo platit, že minimální stupeň grafu je >= n/2 ?
Offline
#2 22. 04. 2010 21:55
Re: Perfektní párování v bipartitním grafu
↑ nordec:Nezaměňovat předpoklad a tvrzení!
Podle zadání KDYŽ tento specifický bipartitní graf má dostatečně vysoký nejmenší stupeň, tak najdeme perfektní párování.
Pokud graf má perfektní párování, tak nic nevím o jeho nejmenším stupni.
Offline
#3 22. 04. 2010 22:01
Re: Perfektní párování v bipartitním grafu
↑ nordec:Mimochodem: a) tvrzení platí a pěkně se dá dokázat sporem a s využitím Hallovy věty.
b) nestačilo by. Nejmenší protipříklad jsou dva izolované vrcholy.
Offline
#4 23. 04. 2010 20:15
Re: Perfektní párování v bipartitním grafu
↑ petrkovar:
Hallova věta říká, že množinový systém má SRR (systém různých reprezentantů) právě tehdy, když pro každý jeho podsystém platí, že velikost sjednocení množin podsystému >= počtu množin podsystému.
Za množinu by šlo vzít vrcholy pravé partity, do kterých vede hrana ze stejného vrcholu levé partity. SRR jsou vrcholy pravé p., každý z jiné množiny. Ale sestavit důkaz pomocí té věty se mi nějak nedaří, proto se pokusím o alternativní důkaz (napadl mě z tvého protipříkladu na b) :
- Počet vrcholů je v každém grafu přirozené číslo, tzn. n >= 1.
- Bipartitní graf (2n vrcholů) s perfektním párováním určitě obsahuje podgraf takový, že z každého vrcholu 1. partity vede hrana do jednoho vrcholu 2. partity (podgraf má n hran, všechny vrcholy stupně 1 => graf má vrcholy stupně alespoň 1).
=> aby libovolný bipartitní graf obsahoval perfektní párování, minimální stupeň G musí být >= 1.
- Zbývá ověřit, zda pro požadovaný minimální stupeň G (zde n/2) je to skutečně >= 1 :
n/2 >= 1 pro n >= 2 platí,
n/2 >= 1 pro n = 1 také platí (min. stupeň vyjde 1/2, ale protože je přirozené číslo, bude to nejméně 1).
Dá se to i takhle dokázat?
Offline
#5 26. 04. 2010 21:29
Re: Perfektní párování v bipartitním grafu
↑ nordec:Ne, bohužel opět došlo k záměně tvrzení a předpokladu.
Má se ukázat, že za jistých předpokladů o stupni vrcholů v grafu najdeme perfektní párování. Tak nemůžeme vycházet z toho, že máme graf s perfektním párováním, ale jen z toho, že nejmenší stupeň v grafu je alespoň n/2.
Navrhuji jiný postup: Sporem. Pokud by graf neměl úplné párování tak najdeme v jedné partitě takovou množinu vrcholů A, že její okolí B v druhé partitě je menší.
Jak velká je množina B? Může být menší než n/2? A co zbývající vrcholy v první partitě, které nepatří do A. Podobně prozkoumáme počet zbývajících vrcholů v druhé partitě, které nepatří do B. Kolik je kterých? S čím dostaneme spor?
Offline
#6 28. 04. 2010 22:45
Re: Perfektní párování v bipartitním grafu
↑ petrkovar:
Množina B bude velká alespoň n/2, protože kdyby A byla nejmenší (tj. 1 vrchol), musí mít alespoň n/2 sousedů.
Množinu A lze vybrat buď tak, že velikost A i jejího doplňku je n/2, nebo jedno z nich bude menší než n/2. Potom k A nebo doplňku A, podle předpokladu pro spor, vychází okolí B menší než n/2. Spor, protože množina B musí být alespoň n/2. Je to tak správně?
Offline
#7 29. 04. 2010 11:59 — Editoval petrkovar (29. 04. 2010 12:05)
Re: Perfektní párování v bipartitním grafu
↑ nordec:To by bylo v případě, že A i doplněk A (kde je doplněk konstruovaný?) mají okolí menší než samotná množina. Ono to ale může platit jen pro jednu množinu. Navrhuji se ještě podívat na vrchol z doplňku B (který neleží v okolí množiny A). Kolik má sousedů a kde jsou?
Offline
#8 01. 05. 2010 16:27 — Editoval nordec (01. 05. 2010 16:29)
Re: Perfektní párování v bipartitním grafu
↑ petrkovar:
Doplněk A jsou vrcholy ve stejné partitě jako A a zároveň nepatřící do A. Vrchol z doplňku B má nejméně n/2 sousedů ležících v doplňku A, takže A by musela být <= n/2, ale pro vrchol z B platí to samé, tedy A = n/2. Totéž platí i pro zaměněné A s B. Z toho vyplývá, že A, B a jejich doplňky jsou velké n/2 => okolí žádné z uvedených množin není menší, než samotná množina, a proto graf obsahuje perfektní párování?
Offline