Matchning med maximal kardinalitetRedigera
Ett grundläggande problem inom kombinatorisk optimering är att hitta en maximal matchning. Detta problem har olika algoritmer för olika klasser av grafer.
I en oviktad tvådelad graf är optimeringsproblemet att hitta en matchning med maximal kardinalitet. Problemet löses av Hopcroft-Karp-algoritmen på O(√VE)-tid, och det finns effektivare randomiserade algoritmer, approximationsalgoritmer och algoritmer för speciella klasser av grafer, t.ex. bipartita plana grafer, som beskrivs i huvudartikeln.
Maximalt viktad matchningRedigera
I en viktad tvådelad graf är optimeringsproblemet att hitta en matchning med maximal vikt; ett dubbelt problem är att hitta en matchning med minimal vikt. Detta problem kallas ofta maximal viktad bipartite matchning, eller tilldelningsfrågan. Den ungerska algoritmen löser tilldelningsproblemet och var en av de första kombinatoriska optimeringsalgoritmerna. Den använder en modifierad sökning efter kortaste vägen i augmenting path-algoritmen. Om Bellman-Ford-algoritmen används för detta steg blir den ungerska algoritmens körtid O ( V 2 E ) {\displaystyle O(V^{2}E)}
, eller så kan kantkostnaden förskjutas med en potential för att uppnå O ( V 2 log V + V E ) {\displaystyle O(V^{2}\log {V}+VE)}
med Dijkstra-algoritmen och Fibonacci-heap.
I en icke-bipartitisk vägd graf kan problemet med matchning med maximal vikt lösas på tiden O ( V 2 E ) {\displaystyle O(V^{2}E)}
med hjälp av Edmonds blossom-algoritm.
Maximala matchningarRedigera
En maximal matchning kan hittas med en enkel greedy-algoritm. En maximal matchning är också en maximal matchning, och därför är det möjligt att hitta den största maximala matchningen på polynomiell tid. Det finns dock ingen algoritm med polynomiell tid för att hitta en minimal maximal matchning, det vill säga en maximal matchning som innehåller minsta möjliga antal kanter.
En maximal matchning med k kanter är en kantdominerande mängd med k kanter. Omvänt kan vi, om vi får en minsta kantdominerande mängd med k kanter, konstruera en maximal matchning med k kanter på polynomiell tid. Därför är problemet med att hitta en minimal maximal matchning i stort sett lika med problemet med att hitta en minimal kantdominerande uppsättning. Båda dessa två optimeringsproblem är kända för att vara NP-hårda. Beslutsversionerna av dessa problem är klassiska exempel på NP-kompletta problem. Båda problemen kan approximeras inom faktor 2 på polynomiell tid: hitta helt enkelt en godtycklig maximal matchning M.
RäkneproblemRedigera
Antalet matchningar i en graf är känt som gravens Hosoya-index. Det är #P-komplett att beräkna denna kvantitet, även för tvådelade grafer. Det är också #P-komplett att räkna perfekta matchningar, även i tvådelade grafer, eftersom beräkningen av permanent av en godtycklig 0-1-matris (ett annat #P-komplett problem) är detsamma som att beräkna antalet perfekta matchningar i den tvådelade grafen som har den givna matrisen som sin biadjacency-matris. Det finns dock en helt polynomialtids randomiserad approximationsmetod för att räkna antalet tvådelade matchningar. En anmärkningsvärd sats av Kasteleyn säger att antalet perfekta matchningar i en planär graf kan beräknas exakt i polynomtid via FKT-algoritmen.
Antalet perfekta matchningar i en komplett graf Kn (med n jämnt) ges av den dubbla faktorn (n – 1)!!!. Antalet matchningar i kompletta grafer, utan begränsning av att matchningarna ska vara perfekta, ges av telefonnummer.
Finnande av alla maximalt matchbara kanterRedigera
Ett av de grundläggande problemen inom matchningsteorin är att i en given graf hitta alla kanter som kan förlängas till en maximal matchning i grafen (sådana kanter kallas maximalt matchningsbara kanter, eller tillåtna kanter). Algoritmer för detta problem inkluderar:
- För allmänna grafer finns en deterministisk algoritm på tiden O ( V E ) {\displaystyle O(VE)}
och en randomiserad algoritm på tiden O ~ ( V 2.376 ) {\displaystyle {\tilde {O}}(V^{2.376})}
.
- För tvådelade grafer, om en enda maximal matchning hittas, körs en deterministisk algoritm på tiden O ( V + E ) {\displaystyle O(V+E)}
.
Online bipartite matchingEdit
Problemet med att utveckla en online-algoritm för matchning övervägdes för första gången av Richard M. Karp, Umesh Vazirani och Vijay Vazirani 1990.
I onlinemiljön anländer noderna på den ena sidan av den bipartite grafen en i taget och måste antingen omedelbart matchas med den andra sidan av grafen eller kastas bort. Detta är en naturlig generalisering av sekreterarproblemet och har tillämpningar på annonsauktioner online. Den bästa online-algoritmen, för det oviktade maximeringsfallet med en modell för slumpmässig ankomst, uppnår ett konkurrensförhållande på 0,696.