Lekce 9 - Párování v grafech

V minulé lekci, Hledání kostry grafu, jsme se podívali na kombinatorický problém - hledání kostry grafu.

Popis problému

Představte si tradiční problém každého učitele. Je zadaná skupinová práce a studenti mají pracovat po dvojicích. Učitel však nechce, aby spolu spolupracovaly děti, které se nemají rády, protože taková práce je většinou z jedné či druhé strany úmyslně sabotovaná. Proto si z pedagogických důvodů pořídil graf, kde V = množina žáků a E = množina kamarádských vztahů mezi žáky V_i a V_j. Hrana v E (V_i - V_j) bude právě tehdy, pokud se mají žáci V_i a V_j rádi.

P je párování z E, neboli výběr určitých hran z E, pokud platí, že je-li vrchol (žák) V_i v množině párování P, je tam právě jednou a to s vrcholem V_j, který je v množině E spojen pouze k vrcholu V_i.

Učitel je zkušený programátor a tak než aby problém řešil konkrétně, zkusí si ho abstrahovat, kdyby mu náhodou do třídy přibyli tři noví žáci nebo naopak dva onemocněli. A vzhledem k tomu, že si kreslil obrázky, můžeme jeho myšlenkové pochody sledovat spolu s ním.

Analýza problému

Pokud by učitel chtěl najít libovolné párování, úloha je řešitelná vždy. Pro každé V najdete množinu E takovou, že je párováním. Zde na obrázku jsou ukázána všechna možná párování na grafu C4 (kružnice o velikosti 4). Prázdná množina je také párováním. Prostě když žádného žáka do dvojice nepřidělí, problém nenastane:

Co kdyby učitel chtěl najít párování maximální? Jaké největší párování může dostat? Z obrázků vidíme, že maximální párování není jednoznačně určeno co do výběru vrcholů, ale je určeno počtem hran. V C4 můžeme nejvýše napárovat 2 hrany.

Z obrázků je však také patrné, že žádný vrchol nezůstal osamocen. Jsou-li tedy ve třídě 4 žáci, je možné je rozdělit do dvojic tak, aby žádný nezbyl. Tomu se říká tzv. perfektní párování. Definice perfektního párování je tedy tato: Pro každý vrchol z V musí platit, že je mu přiřazen právě jeden další vrchol z V, tj. V_i != V_j, pokud i != j.

Pokud máme tedy n vrcholů, určitě platí, že pokud n je liché, perfektní párování nelze vytvořit. Pokud bychom měli 5 žáků, nerozdělíme je tak, aby každý byl s někým ve dvojici a s nikým jiným.

Definice

Párování P v grafu G je podmnožina hran E taková, že každý vrchol z V je incidentní (tj. na jedné straně hrany) s nejvýše jednou hranou z P.

Párování je maximální, pokud neexistuje hrana z E, o kterou by šlo zvětšit párování P.

Párování nazveme perfektním, právě tehdy, pokud je každý vrchol z V incidentní s právě jednou hranou z P.

Párování nemůže být větší než |V|/2, kde |V| značí počet vrcholů grafu G.

Úloha maximálního párování v C_n

Učitel by tedy chtěl zkusit zjistit, jak rozdělit žáky podle zadaných kritérií. V jedné třídě zjistil, že každý žák má rád právě dva své spolužáky a každý žák má rád jinou dvojici. Učitel si graf nakreslil na papír a radostí spadl ze židle. Třída tvořila kružnici. Řešení je tedy nasnadě. Bude postupně procházet jednotlivé hrany tzv. "cik-cak", jednu hranu vloží do párování, jednu ne, jednu ano, jednu ne. Pokud narazí na hranu, kterou už nelze vložit do párování, algoritmus skončí. Je to vlastně obdoba Hladového algoritmu. Dokud můžeš, ber. Pokud je n sudé, je párování perfektní, jinak je pouze maximální. Otázka k zamyšlení, může být párování perfektní a zároveň nebýt maximální?

Úloha maximálního párování v K_n

Nyní učitel přišel do třídy, kde byla banda hipíků. Tito žáci měli rádi každého. V tomto případě je úloha sice o trochu složitější, ale učitel se jen potutelně usmál, vzal si tužku a papír a začal si čmárat. Máme tedy úplný graf. Můžeme si vybrat libovolnou hranu. Vrcholy, které tato hrana spojuje odstraníme, stejně tak i všechny hrany, které k nim vedou. Pokud máme ve třídě 8 hipíků, po první iteraci zbylo 6 hipíků a úlohu jsme si zjednodušili o dva žáky. Při druhé iteraci už máme jen 4 hipíky, při třetí už máme jen jednu dvojici, po 4. iteraci už máme 4 dvojice žáků a můžeme začít s výukou:

Úloha v úplném bipartitním grafu K_m,n

Učitel přišel do poslední třídy, kterou učí a zjistil, že existují dvě skupiny, které se uvnitř mezi sebou nesnáší, ale jinak se mají všichni rádi. Divná banda pankáčů, pokrčil rameny učitel, ale začal rozbalovat papír a brousit tužku. Toto je úloha na bipartitní graf. Máme skupinu o velikosti m a n. Bez újmy na obecnosti (Zkráceně BÚNO) předpokládejme, že m > n. Potom víme, že nemůžeme mít ani perfektní párování, ani párování o větší velikosti než n. Je jednoduché si rozmyslet proč. Použijeme stejný postup jako v minulém příkladu. Budeme postupně odebírat vrcholy, jen musíme z menší množiny:

Triviální úloha párování v nesouvislém grafu

Učitel si pak zkusil jen tak ze srandy vyřešit úlohu, zda by na třídní schůzce byla možnost, že by rodiče byli ve dvojicích také. Zjistil však, že rodiče se mezi sebou neznají a nemá koho párovat. Je asi nemožné, aby seznámil všechny rodiče mezi sebou, proto přemýšlel, zda by se dala úloha řešit tak, že by seznámil pouze některé skupinky a tak utvořil jakési oddělené spojité grafy. Když se však na ty jednotlivé grafy podíval, zmačkal je a zahodil. Je přeci jasné, že by potom řešil každý graf zvlášť a úloha není o nic zajímavější, jen zdlouhavější.

Závěrečná aplikace řešení

Náš učitel se zaradoval, že se mu podařilo problém vyřešit a doma si připravil práci pro své studenty. V pondělí ráno přišel do 4.B, kde však už u dveří malý Tonda žaloval na Otíka, že mu ukradl svačinu a že už ho nemá rád. Otík žaloval na Lindu, Linda zase na Marušku s Verčou, které vše popřely, ale žalovaly na zbytek třídy. Učitel v třesoucích rukách roztrhal své grafy na cucky a autoritativně roztřídil dvojice podle toho, jak žáci seděli ve třídě. Aneb někdy je hold zapotřebí "Brute-force". Řešení není možná nejlepší, ale je aspoň nějaké.

Dodatek k párování v obecných grafech

Algoritmus zde popsaný je jednoduchý a přímočarý. Vyžaduje však speciální třídu grafů. V praxi je však mnohem pravděpodobnější, že se potkáte s grafem, který je nepravidelný a párování se v něm bude hledat mnohem obtížněji. Na to existují mnohem složitější a sofistikovanější algoritmy, například Edmondsův kytičkový algoritmus. Pokud by vás toto téma dále zajímalo, klidně napište do komentářů.