Potrivire de maximă cardinalitateEdit
O problemă fundamentală în optimizarea combinatorie este găsirea unei potriviri maxime. Această problemă are diverși algoritmi pentru diferite clase de grafuri.
Într-un graf bipartit neponderat, problema de optimizare este de a găsi o potrivire de cardinalitate maximă. Problema este rezolvată de algoritmul Hopcroft-Karp în timp O(√VE) timp, și există algoritmi randomizați mai eficienți, algoritmi de aproximare și algoritmi pentru clase speciale de grafuri, cum ar fi grafurile plane bipartite, așa cum sunt descrise în articolul principal.
Potrivire cu greutate maximăEdit
Într-un graf bipartit ponderat, problema de optimizare este de a găsi o potrivire cu greutate maximă; o problemă duală este de a găsi o potrivire cu greutate minimă. Această problemă se numește adesea potrivire bipartită ponderată maximă, sau problema de atribuire. Algoritmul maghiar rezolvă problema de atribuire și a reprezentat unul dintre începuturile algoritmilor de optimizare combinatorială. Acesta utilizează o căutare modificată a celei mai scurte căi în algoritmul de creștere a căii. Dacă se utilizează algoritmul Bellman-Ford pentru această etapă, timpul de execuție al algoritmului maghiar devine O ( V 2 E ) {\displaystyle O(V^{2}E)}.
, sau costul muchiei poate fi decalat cu un potențial pentru a obține O ( V 2 log V + V E ) {\displaystyle O(V^{2}\log {V}+VE)}
timp de rulare cu algoritmul Dijkstra și grămada Fibonacci.
Într-un graf ponderat nebipartit, problema de potrivire a greutății maxime poate fi rezolvată în timp O ( V 2 E ) {\displaystyle O(V^{2}E)}
folosind algoritmul blossom al lui Edmonds.
Potriviri maximeEdit
O potrivire maximă poate fi găsită cu un algoritm greedy simplu. O potrivire maximă este, de asemenea, o potrivire maximă și, prin urmare, este posibil să se găsească cea mai mare potrivire maximă în timp polinomial. Cu toate acestea, nu se cunoaște nici un algoritm în timp polinomial pentru a găsi o potrivire maximă minimă, adică o potrivire maximă care conține cel mai mic număr posibil de muchii.
O potrivire maximă cu k muchii este un set dominat de muchii cu k muchii. Invers, dacă ne este dat un set dominant minim de muchii cu k muchii, putem construi o potrivire maximă cu k muchii în timp polinomial. Prin urmare, problema găsirii unei corespondențe maxime minime este, în esență, egală cu problema găsirii unui set dominant minim de muchii. Se știe că ambele probleme de optimizare sunt NP- dificile; versiunile de decizie ale acestor probleme sunt exemple clasice de probleme NP-complete. Ambele probleme pot fi aproximate în termen de factor 2 în timp polinomial: pur și simplu găsiți o potrivire maximă arbitrară M.
Probleme de numărareEdit
Numărul de potriviri dintr-un graf este cunoscut sub numele de indicele Hosoya al grafului. Este #P-complet să se calculeze această cantitate, chiar și pentru grafurile bipartite. Este, de asemenea, #P-complet să se numere potrivirile perfecte, chiar și în grafurile bipartite, deoarece calcularea permanentei unei matrice arbitrare 0-1 (o altă problemă #P-completă) este aceeași cu calcularea numărului de potriviri perfecte în graful bipartit care are matricea dată ca matrice de biadjacență. Cu toate acestea, există o schemă de aproximare randomizată în timp complet polinomial pentru numărarea numărului de potriviri bipartite. O teoremă remarcabilă a lui Kasteleyn afirmă că numărul de potriviri perfecte într-un graf planar poate fi calculat exact în timp polinomial prin intermediul algoritmului FKT.
Numărul de potriviri perfecte într-un graf complet Kn (cu n par) este dat de factorialul dublu (n – 1)!!!. Numerele de potriviri în grafuri complete, fără a constrânge ca potrivirile să fie perfecte, sunt date de numerele de telefon.
Găsirea tuturor marginilor cu potrivire maximăEdit
Una dintre problemele de bază în teoria potrivirii este de a găsi într-un graf dat toate marginile care pot fi extinse la o potrivire maximă în graf (astfel de margini se numesc margini maximale compatibilizabile, sau margini permise). Algoritmii pentru această problemă includ:
- Pentru grafuri generale, un algoritm determinist în timp O ( V E ) {\displaystyle O(VE)}
și un algoritm randomizat în timp O ~ ( V 2.376 ) {\displaystyle {\tilde {O}}(V^{2.376})}
.
- Pentru grafurile bipartite, dacă se găsește o singură potrivire maximă, un algoritm determinist rulează în timp O ( V + E ) {\displaystyle O(V+E)}.
.
Potrivire bipartită onlineEdit
Problema dezvoltării unui algoritm online pentru potrivire a fost luată în considerare pentru prima dată de Richard M. Karp, Umesh Vazirani și Vijay Vazirani în 1990.
În cadrul online, nodurile de pe o parte a grafului bipartit sosesc unul câte unul și trebuie fie să se potrivească imediat cu cealaltă parte a grafului, fie să fie înlăturate. Aceasta este o generalizare naturală a problemei secretarului și are aplicații la licitațiile publicitare online. Cel mai bun algoritm online, pentru cazul maximizării neponderate cu un model de sosire aleatorie, atinge un raport de competitivitate de 0,696.
.