Matchning med maksimal kardinalitetRediger
Et grundlæggende problem i kombinatorisk optimering er at finde en maksimal matching. Dette problem har forskellige algoritmer for forskellige klasser af grafer.
I en uvægtet bipartite graf er optimeringsproblemet at finde en maksimal cardinality matching. Problemet løses af Hopcroft-Karp-algoritmen på O(√VE)-tid, og der findes mere effektive randomiserede algoritmer, tilnærmelsesalgoritmer og algoritmer for særlige klasser af grafer som f.eks. bipartite plane grafer, som beskrevet i hovedartiklen.
Maximum-weight matchingRediger
I en vægtet bipartite graf er optimeringsproblemet at finde en matchning med maksimal vægt; et dobbeltproblem er at finde en matchning med minimal vægt. Dette problem kaldes ofte maksimalt vægtet bipartite matchning, eller tildelingsproblemet. Den ungarske algoritme løser tildelingsproblemet, og den var en af begyndelsen på kombinatoriske optimeringsalgoritmer. Den anvender en modificeret søgning efter korteste vej i den forstærkende stialgoritme. Hvis Bellman-Ford-algoritmen anvendes til dette trin, bliver løbetiden for den ungarske algoritme O ( V 2 E ) {\displaystyle O(V^{2}E)}
, eller kantomkostningerne kan forskydes med et potentiale for at opnå O ( V 2 log V + V E ) {\displaystyle O(V^{2}\log {V}+VE)}
løbetid med Dijkstra-algoritmen og Fibonacci-heap.
I en ikke-bipartite vægtet graf kan problemet med matchning med maksimal vægt løses på tiden O ( V 2 E ) {\displaystyle O(V^{{2}E)}
ved hjælp af Edmonds’ blossom-algoritme.
Maksimale matchingerRediger
En maksimal matchning kan findes med en simpel greedy-algoritme. En maksimal matchning er også en maksimal matchning, og derfor er det muligt at finde den største maksimale matchning i polynomial tid. Der kendes imidlertid ingen algoritme med polynomial tid til at finde en minimal maksimal matching, dvs. en maksimal matching, der indeholder det mindst mulige antal kanter.
En maksimal matching med k kanter er et kantdominerende sæt med k kanter. Omvendt kan vi, hvis vi får et minimalt kantdominerende sæt med k kanter, konstruere en maksimal matchning med k kanter på polynomial tid. Derfor er problemet med at finde en minimal maksimal matchning stort set lig med problemet med at finde et minimalt kantdominerende sæt. Begge disse to optimeringsproblemer er kendt for at være NP-hårde; beslutningsversionerne af disse problemer er klassiske eksempler på NP-komplette problemer. Begge problemer kan tilnærmes inden for faktor 2 på polynomial tid: man skal blot finde en vilkårlig maksimal matchning M.
OptællingsproblemerRediger
Antallet af matchninger i en graf er kendt som grafen Hosoya-indekset for grafen. Det er #P-komplet at beregne denne mængde, selv for bipartite grafer. Det er også #P-komplet at tælle perfekte matchinger, selv i bipartite grafer, fordi beregning af en vilkårlig 0-1-matrix’ permanent (et andet #P-komplet problem) er det samme som at beregne antallet af perfekte matchinger i den bipartite graf, der har den givne matrix som sin biadjacency-matrix. Der findes imidlertid en randomiseret tilnærmelsesordning til optælling af antallet af bipartite matchings, som er fuldstændig polynomialtid. En bemærkelsesværdig sætning af Kasteleyn fastslår, at antallet af perfekte matchinger i en planar graf kan beregnes nøjagtigt i polynomial tid via FKT-algoritmen.
Tallet af perfekte matchinger i en komplet graf Kn (med n lige) er givet ved den dobbelte faktorial (n – 1)!!!. Antallet af matchinger i komplette grafer, uden at matchingerne er perfekte, er givet ved telefonnumrene.
Finding all maximally-matchable edgesEdit
Hovedartikel: Maximalt matchbare kanter
Et af de grundlæggende problemer i matchningsteori er at finde i en given graf alle kanter, der kan udvides til en maksimal matchning i grafen (sådanne kanter kaldes maksimalt matchbare kanter, eller tilladte kanter). Algoritmer til dette problem omfatter:
- For generelle grafer er der en deterministisk algoritme i tiden O ( V E ) {\displaystyle O(VE)}
og en randomiseret algoritme på tiden O ~ ( V 2.376 ) {\displaystyle {\tilde {O}}(V^{{2.376})}
.
- For bipartite grafer, hvis der findes en enkelt maksimal matchning, kører en deterministisk algoritme på tiden O ( V + E ) {\displaystyle O(V+E)}
.
Online bipartite matchingRediger
Problemet med at udvikle en online-algoritme til matching blev først overvejet af Richard M. Karp, Umesh Vazirani og Vijay Vazirani i 1990.
I online-stillingen ankommer knuder på den ene side af den bipartite graf én ad gangen og skal enten straks matches til den anden side af grafen eller kasseres. Dette er en naturlig generalisering af sekretærproblemet og har anvendelser på online annonceauktioner. Den bedste online-algoritme for det uvægtede maksimeringstilfælde med en tilfældig ankomstmodel opnår et konkurrencedygtigt forhold på 0,696.