Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Množinové systémy, párování, párování v bipartitních grafech (systémy různých reprezentantů)

Definice

Nechť a jsou množiny. Množinovým systémem nad nazveme -tici , kde

Je tedy možné, aby se tam táž množina objevila víckrát.

Definice (systém různých reprezentantů)

Systém různých reprezentantů (SRR) je funkce taková, že a je prostá.

Jinými slovy, SRR je výběr jednoho prvku z každé množiny tak, že všechny vybrané prvky jsou navzájem různé. Obecně se tedy neuvažují nekonečné systémy.

Definice (párování)

Párování v grafu je množina hran taková, že každý vrchol grafu patří nejvýše do jedné hrany z .

Ekvivalentní definice jsou přes stupeň vrcholu (každý vrchol má stupeň nejvýše 1) nebo přes disjunktnost hran (každé dvě jsou disjunktní - žádné dvě nemají společný vrchol).

Definice (bipartitní graf)

Bipartitní graf je takový graf , kde množinu vrcholů můžeme rozdělit na dvě disjunktní podmnožiny a takové, že každá hrana z spojuje vždy vrchol z s vrcholem z .

Definice

Incidenčním grafem množinového systému nad množinou nazveme bipartitní graf

V podstatě si každý prvek z i každý index označíme vrcholem a spojíme každý index s prvky , které náleží do . Z incidenčního grafu pak lze nahlédnout existenci SRR - ten existuje, právě když v incidenčním grafu existuje párování velikosti .

Věta (Hallova)

Systém různých reprezentantů v existuje, právě když pro každou je

Definice (perfektní párování)

Perfektním párováním nazveme párování v grafu , pro které platí

Tedy perfektní párování je takové, kde je každý vrchol spárovaný s nějakým jiným vrcholem. Dalším důležitým pojmem je maximální párování, což je v podstatě nejlepší možné párování (pokrývá největší možný počet vrcholů), jakého jsme v daném grafu schopni dosáhnout.

Věta (O párování v bipartitním grafu)

Buď graf se dvěma partitami a a neprázdná množina hran. Jestliže platí , potom existuje párování velikosti . Díky tomu pokud má bipartitní graf všechny vrcholy stejného stupně, pak má perfektní párování.

Důkaz

Převede se na Hallovu větu s použitím okolí vrcholů (tj. bodů přímo spojených s vrcholem hranou).

Věta (Tutteova)

Graf má perfektní párování, právě když pro každou množinu vrcholů platí:

(tj. počet komponent souvislosti s lichých počtem vrcholů v indukovaném podgrafu je menší než velikost množiny vrcholů). Této vlastnosti se také někdy říká Tutteova podmínka.

Algoritmus (Edmondsův algoritmus na perfektní párování)

Vstupem algoritmu je graf a libovolné párování (i prázdné). Výstupem je párování , které alespoň o 1 větší než , pokud je něčeho takového možné dosáhnout. Postup výpočtu:

1. Vybudujeme maximální možný Edmondsův les párování - do nulté hladiny umístíme volné vrcholy a prohledáváním do šířky sestrojíme max. strom takový, že se střídají párovací a nepárovací hrany (mezi sudou a lichou hladinou jen nepárovací, mezi lichou a sudou jen párovací).

   Některé vrcholy se v lese vůbec neobjeví - nazveme je kompost. Ty jsou už nějak spárovány mezi sebou a nebudeme je potřebovat.

2. Pokud existuje hrana mezi sudými hladinami různých stromů, máme volnou střídavou cestu (tj. cestu liché délky mezi 2 volnými vrcholy, na které se střídají nepárovací a párovací hrany), na níž můžeme zalternovat hrany párování a to tak zvětšit o 1 a skončit.
3. Pokud existuje hrana mezi sudými hladinami téhož stromu, máme květ (tj. kružnici liché délky, na které se střídají párovací a nepárovací hrany). Květ můžeme zkontrahovat a algoritmus rekurzivně pustit na takto získaný graf. Pokud dostaneme
   1. staré párování beze změny, vrátíme
   2. jiné (větší) párování , prohodíme párování na cestě v od vrcholu květu v nejvyšší hladině (kam jsme květ zkontrahovali) k volnému vrcholu a přidáme květ zpátky (a párování sedí a je větší než )
4. Není-li žádná hrana mezi sudými hladinami, vydej .

Hlavní algoritmus jen opakuje výše popsaný krok, dokud vrací větší párování než bylo předchozí. Celková složitost jednoho kroku je a pro celý algoritmus .