9. diel - Párovanie v grafoch

Popis problému

Predstavte si tradičný problém každého učiteľa. Je zadané skupinová práca a študenti majú pracovať po dvojiciach. Učiteľ však nechce, aby spolu spolupracovali deti, ktoré sa nemajú rady, pretože takáto práca je väčšinou z jednej či druhej strany úmyselne sabotovaný. Preto si z pedagogických dôvodov vydal graf, kde V = množina žiakov a E = množina kamarátskych vzťahov medzi žiakmi V_i a V_j. Hrana v E (V_i - V_j) bude práve vtedy, ak sa majú žiaci V_i a V_j radi.

P je párovanie z E, čiže výber určitých hrán z E, ak platí, že ak je vrchol (žiak) V_i v množine párovanie P, je tam práve raz a to s vrcholom V_j, ktorý je v množine E spojený iba k vrcholu V_i.

Učiteľ je skúsený programátor a tak než aby problém riešil konkrétne, skúsi si ho abstrahovať, keby mu náhodou do triedy pribudli traja noví žiaci alebo naopak dva ochoreli. A vzhľadom k tomu, že si kreslil obrázky, môžeme jeho myšlienkové pochody sledovať spolu s ním.

Analýza problému

Pokiaľ by učiteľ chcel nájsť ľubovoľné párovanie, úloha je riešiteľná vždy. Pre každé V nájdete množinu E takú, že je párovaním. Tu na obrázku sú ukázaná všetky možné párovanie na grafe C4 (kružnica o veľkosti 4). Prázdna množina je tiež párovaním. Proste keď žiadneho žiaka do dvojice nepridelí, problém nenastane:

Čo keby učiteľ chcel nájsť párovanie maximálnu? Aké najväčšie párovanie môže dostať? Z obrázkov vidíme, že maximálna párovanie nie je jednoznačne určené čo do výberu vrcholov, ale je určené počtom hrán. V C4 môžeme najviac napárovať 2 hrany.

Z obrázkov je však tiež zrejmé, že žiadny vrchol nezostal osamotený. Takže pokiaľ sú v triede 4 žiaci, je možné ich rozdeliť do dvojíc tak, aby žiadny neostal. Tomu sa hovorí tzv. perfektní párování. Definícia perfektného párovanie je preto: Pre každý vrchol z V musí platiť, že je mu priradený práve jeden ďalší vrchol z V, tj. V_i != V_j, ak i != j.

Ak máme teda n vrcholov, určite platí, že ak n je nepárne, perfektný párovanie nemožno vytvoriť. Ak by sme mali 5 žiakov, nerozdelíme je tak, aby každý bol s niekým vo dvojici as nikým iným.

Definícia

Párovanie P v grafe G je podmnožina hrán E taká, že každý vrchol z V je incidentní (tj. Na jednej strane hrany) s najviac raz hranou z P.

Párovanie je maximálna, ak neexistuje hrana z E, o ktorú by išlo zväčšiť párovanie P.

Párovanie nazveme perfektným, práve vtedy, keď je každý vrchol z V incidentní s práve jednou hranou z P.

Párovanie nemôže byť väčšia ako |V|/2, kde |V| značí počet vrcholov grafu G.

Úloha maximálneho párovanie v C_n

Učiteľ by teda chcel skúsiť zistiť, ako rozdeliť žiakov podľa zadaných kritérií. V jednej triede zistil, že každý žiak má rád práve dvoch svojich spolužiakov a každý žiak má rád inú dvojicu. Učiteľ si graf nakreslil na papier a radosťou spadol zo stoličky. Trieda tvorila kružnicu. Riešenie je teda jasné. Bude postupne prechádzať jednotlivé hrany tzv. "Cik-cak", jednu hranu vloží do párovania, jednu nie, jednu áno, jednu nie. Ak narazí na hranu, ktorú už nie je možné vložiť do párovania, algoritmus skončí. Je to vlastne obdoba hladného algoritmu. Kým môžeš, ber. Ak je n párne, je párovanie perfektné, inak je len maximálna. Otázka na zamyslenie, môže byť párovanie perfektné a zároveň nebyť maximálnu?

Úloha maximálneho párovanie v K_n

Teraz učiteľ prišiel do triedy, kde bola banda hipíkov. Títo žiaci mali radi každého. V tomto prípade je úloha síce o trochu zložitejšie, ale učiteľ sa len potmehúdsky usmial, zobral si ceruzku a papier a začal si čmárať. Máme teda úplný graf. Môžeme si vybrať ľubovoľnú hranu. Vrcholy, ktoré táto hrana spája odstránime, rovnako aj všetky hrany, ktoré k nim vedú. Ak máme v triede 8 hipíkov, po prvej iterácii zostalo 6 hipíkov a úlohu sme si zjednodušili o dvoch žiakov. Pri druhej iterácii už máme len 4 hipikom, pri tretej už máme len jednu dvojicu, po 4. iterácii už máme 4 dvojice žiakov a môžeme začať s výučbou:

Úloha v úplnom bipartitním grafe K_m, n

Učiteľ prišiel do poslednej triedy, ktorú učí a zistil, že existujú dve skupiny, ktoré sa vo vnútri medzi sebou neznáša, ale inak sa majú všetci radi. Divná banda pankáčov, pokrčil ramenami učiteľ, ale začal rozbaľovať papier a brúsiť ceruzku. Toto je úloha na párny graf. Máme skupinu o veľkosti m a n. B ez ú UJMY n a o becnosti (Skrátene Buno) predpokladajme, že m > n. Potom vieme, že nemôžeme mať ani perfektné párovanie, ani párovanie o väčšej veľkosti než n. Je jednoduché si rozmyslieť prečo. Použijeme rovnaký postup ako v minulom príklade. Budeme postupne odoberať vrcholy, len musíme z menšej množiny:

Triviálne úloha párovanie v nesúvislá grafe

Učiteľ si potom skúsil len tak zo srandy vyriešiť úlohu, či by na triednej schôdzke bola možnosť, že by rodičia boli vo dvojiciach tiež. Zistil však, že rodičia sa medzi sebou nepoznajú a nemá koho párovať. Je asi nemožné, aby oboznámil všetkých rodičov medzi sebou, preto premýšľal, či by sa dala úloha riešiť tak, že by zoznámil iba niektoré skupinky a tak utvoril akési oddelené spojité grafmi. Keď sa však na tie jednotlivé grafy pozrel, zmačkal je a zahodil. Je predsa jasné, že by potom riešil každý graf zvlášť a úloha nie je o nič zaujímavejšie, len zdĺhavejšie.

Záverečná aplikácia riešenie

Náš učiteľ sa zaradoval, že sa mu podarilo problém vyriešiť a doma si pripravil prácu pre svojich študentov. V pondelok ráno prišiel do 4.B, kde však už pri dverách malý Tonda žaloval na Otík, že mu ukradol desiatu a že už ho nemá rád. Otík žaloval na Lindu, Linda zase na Marušku s Verčou, ktoré všetko popreli, ale žalovali na zvyšok triedy. Učiteľ v trasúcich rukách roztrhal svoje grafy na cucky a autoritatívne roztriedil dvojice podľa toho, ako žiaci sedeli v triede. Aneb niekedy je hold potrebná "Brute-force". Riešenie nie je možno najlepší, ale je aspoň nejaké.

Dodatok k párovanie v všeobecných grafoch

Algoritmus tu popísaný je jednoduchý a priamočiary. Vyžaduje však špeciálne triedu grafov. V praxi je však oveľa pravdepodobnejšie, že sa stretnete s grafom, ktorý je nepravidelný a párovanie sa v ňom bude hľadať oveľa ťažšie. Na to existujú oveľa zložitejšie a sofistikovanejšie algoritmy, napríklad Edmondsův kvetinkový algoritmus. Ak by vás táto téma ďalej zaujímalo, kľudne napíšte do komentárov.