Maximum-cardinality matchingEdit
Kombinatorisen optimoinnin perusongelma on maksimaalisen matchingin löytäminen. Tähän ongelmaan on olemassa erilaisia algoritmeja eri graafiluokille.
Painottamattomassa kaksiosaisessa graafissa optimointiongelmana on löytää maksimaalisen kardinaalisuuden mukainen matching. Ongelma ratkaistaan Hopcroft-Karpin algoritmilla ajassa O(√VE), ja on olemassa tehokkaampia satunnaistettuja algoritmeja, approksimaatioalgoritmeja ja algoritmeja erityisille graafiluokille, kuten kaksijakoisille tasograafeille, kuten pääartikkelissa on kuvattu.
Maksimipainotteinen täsmäytys Muokkaa
Painotetussa kaksiosaisessa graafissa optimointiongelmana on löytää maksimipainoinen matching; kaksoisongelmana on löytää minimipainoinen matching. Tätä ongelmaa kutsutaan usein nimellä maksimipainotettu kaksiosaisen graafin yhteensovittaminen (maximum weighted bipartite matching) tai osoitusongelma (assignment problem). Unkarilainen algoritmi ratkaisee assignment-ongelman, ja se oli yksi kombinatoristen optimointialgoritmien alkuajoista. Se käyttää modifioitua lyhimmän polun hakua augmenting path -algoritmissa. Jos tähän vaiheeseen käytetään Bellman-Fordin algoritmia, unkarilaisen algoritmin suoritusajaksi tulee O ( V 2 E ) {\displaystyle O(V^{2}E)}
, tai reunakustannuksia voidaan siirtää potentiaalilla, jolloin saavutetaan O ( V 2 log V + V E ) {\displaystyle O(V^{2}\log {V}+VE)}
juoksuaika Dijkstra-algoritmilla ja Fibonacci-kuopalla.
Ei-bipartisessa painotetussa graafissa suurimman painon yhteensovittamisen ongelma voidaan ratkaista ajassa O ( V 2 E ) {\displaystyle O(V^{2}E)}
käyttäen Edmondsin blossom-algoritmia.
Maksimaaliset yhteensovituksetEdit
Maksimaalinen yhteensovitus voidaan löytää yksinkertaisella ahneella algoritmilla. Maksimaalinen yhteensovitus on myös maksimaalinen yhteensovitus, ja näin ollen on mahdollista löytää suurin maksimaalinen yhteensovitus polynomiajassa. Ei kuitenkaan tunneta polynomia-aikaista algoritmia pienimmän maksimaalisen yhteensovituksen löytämiseksi, eli sellaisen maksimaalisen yhteensovituksen löytämiseksi, joka sisältää pienimmän mahdollisen määrän särmiä.
Maksimaalinen yhteensovitus, jossa on k särmää, on särmää hallitseva joukko, jossa on k särmää. Kääntäen, jos meille annetaan minimaalinen reunadominoiva joukko, jossa on k reunaa, voimme konstruoida maksimaalisen sovituksen, jossa on k reunaa, polynomiajassa. Näin ollen pienimmän maksimaalisen sovituksen löytämisen ongelma on olennaisesti sama kuin pienimmän reunoja hallitsevan joukon löytämisen ongelma. Molempien optimointiongelmien tiedetään olevan NP-kovia; näiden ongelmien päätösversiot ovat klassisia esimerkkejä NP-täydellisistä ongelmista. Molemmat ongelmat voidaan approksimoida kertoimen 2 sisällä polynomiajassa: yksinkertaisesti löydetään mielivaltainen maksimaalinen yhteensovitus M.
LaskentaongelmatEdit
Graafin vastaavuuksien lukumäärää kutsutaan graafin Hosoya-indeksiksi. Tämän määrän laskeminen on #P-täydellinen, jopa kaksiosaisille graafeille. On myös #P-täydellistä laskea täydelliset täsmäämiset, jopa kaksijakoisissa graafeissa, koska mielivaltaisen 0-1-matriisin permanentin laskeminen (toinen #P-täydellinen ongelma) on sama kuin täydellisten täsmäämisien lukumäärän laskeminen kaksijakoisessa graafissa, jonka kaksijakoisuusmatriisina on kyseinen matriisi. On kuitenkin olemassa täysin polynomisessa ajassa satunnaistettu approksimaatiojärjestelmä, jolla voidaan laskea kaksijakoisten vastaavuuksien lukumäärä. Kasteleynin huomattavan teoreeman mukaan täydellisten matchingien lukumäärä tasograafissa voidaan laskea täsmälleen polynomiajassa FKT-algoritmin avulla.
Täydellisten matchingien lukumäärä täydellisessä graafissa Kn (jossa n on parillinen) saadaan kaksinkertaisella faktoriaalilla (n – 1)!!!. Täydellisten graafien täsmäämisten lukumäärät ilman, että täsmäämisten on oltava täydellisiä, saadaan puhelinluvuilla.
Kaikkien maksimaalisesti täsmäävien särmien löytäminenEdit
Yksi sovitusteorian perusongelmista on löytää tietystä graafista kaikki sellaiset särmät, jotka voidaan ulottaa graafin maksimaaliseen sovitukseen (tällaisia särmiä kutsutaan maksimaalisesti sovitettaviksi särmiksi tai sallituiksi särmiksi). Algoritmeja tähän ongelmaan ovat:
- Yleisille graafeille deterministinen algoritmi ajassa O ( V E ) {\displaystyle O(VE)}.
ja satunnaistettu algoritmi ajassa O ~ ( V 2.376 ) {\displaystyle {\tilde {O}}(V^{2.376})}
.
- Kaksiosaisille graafeille, jos löydetään yksi maksimaalinen matching, deterministinen algoritmi toimii ajassa O ( V + E ) {\displaystyle O(V+E)} {\displaystyle O(V+E)}
.
Online bipartite matchingEdit
Online-algoritmin kehittämisongelmaa yhteensovittamista varten pohtivat ensimmäisen kerran Richard M. Karp, Umesh Vazirani ja Vijay Vazirani vuonna 1990.
Online-asetelmassa bipartite-graafin toiselle puolelle saapuvat solmut saapuvat yksitellen, ja ne on joko sovitettava välittömästi graafin toiselle puolelle tai hylättävä. Tämä on luonnollinen yleistys sihteeriongelmasta, ja sillä on sovelluksia verkkomainoshuutokauppoihin. Paras online-algoritmi painottamattomassa maksimointitapauksessa satunnaisen saapumisen mallilla saavuttaa kilpailukykyisen suhdeluvun 0,696.