Shoda s maximální kardinalitouUpravit
Základním problémem kombinatorické optimalizace je nalezení maximální shody. Tento problém má různé algoritmy pro různé třídy grafů.
V neváženém bipartitním grafu je optimalizačním problémem nalezení maximální kardinality shody. Problém se řeší Hopcroftovým-Karpovým algoritmem v čase O(√VE) a existují efektivnější randomizované algoritmy, aproximační algoritmy a algoritmy pro speciální třídy grafů, jako jsou bipartitní planární grafy, jak je popsáno v hlavním článku.
Maximálně vážená shodaUpravit
Ve váženém bipartitním grafu je optimalizačním problémem nalezení shody s maximální váhou; duálním problémem je nalezení shody s minimální váhou. Tento problém se často nazývá maximálně vážené bipartitní párování nebo problém přiřazení. Maďarský algoritmus řeší přiřazovací problém a byl jedním z počátků kombinatorických optimalizačních algoritmů. Používá modifikované hledání nejkratší cesty v algoritmu rozšiřující cesty. Pokud se pro tento krok použije Bellmanův-Fordův algoritmus, doba běhu maďarského algoritmu se stane O ( V 2 E ) {\displaystyle O(V^{2}E)}
, nebo lze náklady na hrany posunout s potenciálem a dosáhnout O ( V 2 log V + V E ) {\displaystyle O(V^{2}\log {V}+VE)}
běhového času s Dijkstrovým algoritmem a Fibonacciho hromadou.
V nebipartitním váženém grafu lze problém maximální váhové shody vyřešit v čase O ( V 2 E ) {\displaystyle O(V^{2}E)}
pomocí Edmondsova blossom algoritmu.
Maximální shodyEdit
Maximální shodu lze nalézt pomocí jednoduchého chamtivého algoritmu. Maximální shoda je také maximální shoda, a proto je možné najít největší maximální shodu v polynomiálním čase. Není však znám žádný algoritmus v polynomiálním čase pro nalezení minimální maximální shody, tj. maximální shody, která obsahuje nejmenší možný počet hran.
Maximální shoda s k hranami je hranově dominantní množina s k hranami. A naopak, je-li dána minimální hranově dominantní množina s k hranami, můžeme zkonstruovat maximální shodu s k hranami v polynomiálním čase. Problém nalezení minimální maximální shody se tedy v podstatě rovná problému nalezení minimální množiny dominujících hran. Je známo, že oba tyto dva optimalizační problémy jsou NP-těžké; rozhodovací verze těchto problémů jsou klasickými příklady NP-úplných problémů. Oba problémy lze aproximovat v polynomiálním čase s faktorem 2: stačí najít libovolnou maximální shodu M.
Problémy počítáníUpravit
Počet shod v grafu se nazývá Hosoya index grafu. Výpočet této veličiny je #P-úplný, a to i pro bipartitní grafy. Je také #P-úplné spočítat dokonalé shody, a to i u bipartitních grafů, protože výpočet permanentní libovolné matice 0-1 (další #P-úplný problém) je stejný jako výpočet počtu dokonalých shod v bipartitním grafu, který má danou matici jako svou biadiacenční matici. Existuje však plně polynomiální časově náhodné aproximační schéma pro počítání počtu bipartitních shod. Pozoruhodná Kasteleynova věta říká, že počet dokonalých shod v rovinném grafu lze spočítat přesně v polynomiálním čase pomocí algoritmu FKT.
Počet dokonalých shod v úplném grafu Kn (se sudým n) je dán dvojnásobkem faktoriálu (n – 1)!!!. Počty shod v úplných grafech, bez omezení, aby shody byly dokonalé, jsou dány telefonními čísly.
Nalezení všech maximálně shodných hranUpravit
Jedním ze základních problémů teorie přiřazování je najít v daném grafu všechny hrany, které lze v grafu rozšířit na maximální přiřazení (takové hrany se nazývají maximálně přiřazené hrany nebo povolené hrany). Mezi algoritmy pro tento problém patří:
- Pro obecné grafy je deterministický algoritmus v čase O ( V E ) {\displayystyle O(VE)}.
a randomizovaný algoritmus v čase O ~ ( V 2,376 ) {\displaystyle {\tilde {O}}(V^{2,376})} }.
.
- Pro bipartitní grafy, pokud je nalezena jediná maximální shoda, běží deterministický algoritmus v čase O ( V + E ) {\displaystyle O(V+E)}.
.
Online bipartitní párováníEdit
Problémem vývoje online algoritmu pro párování se poprvé zabývali Richard M. Karp, Umesh Vazirani a Vijay Vazirani v roce 1990.
V online nastavení přicházejí uzly na jedné straně bipartitního grafu po jednom a musí být buď okamžitě přiřazeny k druhé straně grafu, nebo vyřazeny. Jedná se o přirozené zobecnění problému sekretářky a má své uplatnění v online reklamních aukcích. Nejlepší online algoritmus pro případ nevážené maximalizace s modelem náhodného příchodu dosahuje konkurenčního poměru 0,696.
.