Maximum-cardinality matchingEdit
Podstawowym problemem w optymalizacji kombinatorycznej jest znalezienie maksymalnego dopasowania. Problem ten ma różne algorytmy dla różnych klas grafów.
W nieważonym grafie dwudzielnym, problemem optymalizacyjnym jest znalezienie maksymalnego dopasowania kardynalności. Problem ten jest rozwiązywany przez algorytm Hopcrofta-Karpa w czasie O(√VE) time, przy czym istnieją wydajniejsze algorytmy randomizowane, algorytmy przybliżone oraz algorytmy dla specjalnych klas grafów, takich jak dwudzielne grafy planarne, opisane w głównym artykule.
Dopasowanie maksymalnej wagiEdit
W ważonym grafie dwudzielnym problemem optymalizacyjnym jest znalezienie dopasowania o maksymalnej wadze; problemem dualnym jest znalezienie dopasowania o minimalnej wadze. Problem ten jest często nazywany maksymalnym ważonym dopasowaniem dwudzielnym, lub problemem przypisania. Algorytm węgierski rozwiązuje problem przyporządkowania i był jednym z początków algorytmów optymalizacji kombinatorycznej. Wykorzystuje on zmodyfikowane wyszukiwanie najkrótszej ścieżki w algorytmie ścieżki rozszerzonej. Jeśli do tego kroku użyjemy algorytmu Bellmana-Forda, to czas działania algorytmu węgierskiego staje się O ( V 2 E ){ O(V^{2}E)}
, lub koszt krawędzi może być przesunięty z potencjałem, aby osiągnąć O ( V 2 log V + V E ) {displaystyle O(V^{2}log {V}+VE)}
czas działania z algorytmem Dijkstry i stertą Fibonacciego.
W nie dwudzielnym grafie ważonym problem maksymalnego dopasowania wagowego można rozwiązać w czasie O ( V 2 E )}
za pomocą algorytmu Blossom Edmondsa.
Maksymalne dopasowaniaEdit
Maksymalne dopasowanie można znaleźć za pomocą prostego algorytmu zachłannego. Maksymalne dopasowanie jest również maksymalnym dopasowaniem, a zatem możliwe jest znalezienie największego maksymalnego dopasowania w czasie wielomianowym. Jednakże, nie jest znany algorytm czasu wielomianowego dla znalezienia minimalnego maksymalnego dopasowania, to jest, maksymalnego dopasowania, które zawiera najmniejszą możliwą liczbę krawędzi.
Maksymalne dopasowanie z k krawędziami jest zbiorem dominującym krawędzi z k krawędziami. I odwrotnie, jeśli mamy minimalny zbiór dominujący z k krawędziami, to możemy skonstruować maksymalne dopasowanie z k krawędziami w czasie wielomianowym. Zatem problem znalezienia minimalnego maksymalnego dopasowania jest w zasadzie równy problemowi znalezienia minimalnego zbioru dominującego na krawędziach. Oba te problemy optymalizacyjne są znane jako NP-hard; wersje decyzyjne tych problemów są klasycznymi przykładami NP-complete problemów. Oba problemy mogą być przybliżone w czynniku 2 w czasie wielomianowym: po prostu znajdź arbitralne maksymalne dopasowanie M.
Problemy liczeniaEdit
Liczba dopasowań w grafie jest znana jako indeks Hosoya tego grafu. Obliczenie tej liczby jest #P-zupełne, nawet dla grafów dwudzielnych. Obliczanie idealnych dopasowań, nawet w grafach dwudzielnych, jest również #P-zupełne, ponieważ obliczanie stałej dowolnej macierzy 0-1 (kolejny problem #P-zupełny) jest takie samo jak obliczanie liczby idealnych dopasowań w grafie dwudzielnym mającym daną macierz jako swoją macierz biadacjencji. Istnieje jednak w pełni wielomianowy, randomizowany w czasie schemat przybliżonego liczenia liczby dopasowań w grafie dwudzielnym. Godne uwagi twierdzenie Kasteleyna mówi, że liczba idealnych dopasowań w grafie planarnym może być obliczona dokładnie w czasie wielomianowym za pomocą algorytmu FKT.
Liczba idealnych dopasowań w grafie zupełnym Kn (z n parzystym) jest dana przez podwójny czynnik (n – 1)!!!. Liczby dopasowań w grafach zupełnych, bez ograniczenia, że dopasowania muszą być doskonałe, są dane przez numery telefonów.
Znajdowanie wszystkich maksymalnie dopasowalnych krawędziEdit
Jednym z podstawowych problemów w teorii dopasowania jest znalezienie w danym grafie wszystkich krawędzi, które mogą być rozszerzone do maksymalnego dopasowania w grafie (takie krawędzie nazywane są krawędziami maksymalnie dopasowanymi, lub krawędziami dozwolonymi). Algorytmy dla tego problemu obejmują:
- Dla grafów ogólnych, deterministyczny algorytm w czasie O ( V E ) {{displaystyle O(VE)}
oraz algorytm randomizowany w czasie O ~ ( V 2.376 ) {displaystyle {O}}(V^{2.376})}
.
- Dla grafów dwudzielnych, jeśli znalezione jest jedno maksymalne dopasowanie, deterministyczny algorytm działa w czasie O ( V + E ) {displaystyle O(V+E)}
.
Dopasowanie dwudzielne onlineEdit
Problem opracowania algorytmu online dla dopasowania został po raz pierwszy rozważony przez Richarda M. Karpa, Umesha Vaziraniego i Vijaya Vaziraniego w 1990 roku.
W ustawieniu online węzły po jednej stronie grafu dwudzielnego przybywają pojedynczo i muszą być albo natychmiast dopasowane do drugiej strony grafu, albo odrzucone. Jest to naturalne uogólnienie problemu sekretarza i ma zastosowanie w internetowych aukcjach reklamowych. Najlepszy algorytm online, dla nieważonego przypadku maksymalizacji z losowym modelem przybycia, osiąga współczynnik konkurencyjności 0.696.
.