Maximum-kardinalitású párosításSzerkesztés
A kombinatorikus optimalizálás egyik alapvető problémája a maximális illesztés megtalálása. Erre a problémára különböző algoritmusok léteznek a gráfok különböző osztályaira.
Egy súlyozatlan kétrészes gráfban az optimalizálási probléma a maximális kardinalitású illeszkedés megtalálása. A problémát a Hopcroft-Karp algoritmus O(√VE) idő alatt oldja meg, és léteznek hatékonyabb randomizált algoritmusok, közelítő algoritmusok, valamint a gráfok speciális osztályaira, például a kétrészes sík gráfokra vonatkozó algoritmusok, amelyeket a főcikkben ismertetünk.
Maximális súlyú illesztésSzerkesztés
Egy súlyozott kétrészes gráfban az optimalizálási probléma a maximum-weight matching megtalálása; a kettős probléma a minimum-weight matching megtalálása. Ezt a problémát gyakran maximális súlyú bipartit illesztésnek vagy hozzárendelési problémának nevezik. A magyar algoritmus a hozzárendelési problémát oldja meg, és ez volt a kombinatorikus optimalizációs algoritmusok egyik kezdete. Módosított legrövidebb út keresést használ a bővülő út algoritmusban. Ha ehhez a lépéshez a Bellman-Ford algoritmust használjuk, akkor a magyar algoritmus futási ideje O ( V 2 E ) {\displaystyle O(V^{2}E)} lesz.
, vagy az élköltséget potenciállal eltolva O ( V 2 log V + V E ) {\displaystyle O(V^{2}\log {V}+VE)} érhető el.
futási időt a Dijkstra-algoritmussal és a Fibonacci-halommal.
Nem kétrészes súlyozott gráfban a maximális súlyillesztés problémája O ( V 2 E ) {\displaystyle O(V^{2}E)} idő alatt megoldható.
az Edmonds-féle blossom algoritmus segítségével.
Maximális egyezésekSzerkesztés
A maximális egyezést egy egyszerű mohó algoritmussal lehet megtalálni. A maximális illeszkedés egyben maximális illeszkedés is, és így polinomiális idő alatt meg lehet találni a legnagyobb maximális illeszkedést. Azonban nem ismert polinomiális idejű algoritmus a minimális maximális illeszkedés megtalálására, azaz olyan maximális illeszkedésre, amely a lehető legkisebb számú élt tartalmazza.
A maximális illeszkedés k éllel egy éldomináns halmaz k éllel. Megfordítva, ha adott egy minimális éldomináns halmaz k éllel, akkor polinomiális idő alatt konstruálhatunk egy maximális illeszkedést k éllel. Ezért a minimális maximális illeszkedés megtalálásának problémája lényegében megegyezik a minimális éldomináns halmaz megtalálásának problémájával. Mindkét optimalizálási problémáról ismert, hogy NP-nehezek; e problémák döntési változatai az NP-teljes problémák klasszikus példái. Mindkét probléma 2 faktoron belül polinomiális idővel közelíthető: egyszerűen találjunk egy tetszőleges M maximális illeszkedést.
Számolási problémákSzerkesztés
A gráfban található egyezések számát a gráf Hosoya-indexének nevezzük. Ennek a mennyiségnek a kiszámítása #P-teljes, még kétrészes gráfok esetén is. Ugyancsak #P-teljes a tökéletes egyezések számolása, még kétrészes gráfokban is, mert egy tetszőleges 0-1 mátrix permanensének kiszámítása (egy másik #P-teljes probléma) ugyanaz, mint a tökéletes egyezések számának kiszámítása abban a kétrészes gráfban, amelynek biadjacencia-mátrixa az adott mátrix. Létezik azonban egy teljesen polinomiális idejű, véletlenszerű közelítő séma a bipartit egyezések számítására. Kasteleyn egy figyelemre méltó tétele szerint a tökéletes egyezések száma egy sík gráfban pontosan kiszámítható polinomiális időben az FKT algoritmus segítségével.
A tökéletes egyezések száma egy Kn teljes gráfban (n páros n-nel) a (n – 1)!!! kettős faktoriálisával adódik. Az illeszkedések számát teljes gráfokban, anélkül, hogy az illeszkedések tökéletesek lennének, a telefonszámok adják.
Az összes maximálisan illeszthető él megtalálásaSzerkesztés
Az illeszkedéselmélet egyik alapvető problémája, hogy egy adott gráfban megtaláljuk az összes olyan élt, amely a gráfban maximálisan illeszthetőre bővíthető (az ilyen éleket nevezzük maximálisan illeszthető éleknek vagy megengedett éleknek). Erre a problémára a következő algoritmusok léteznek:
- Általános gráfok esetén egy determinisztikus algoritmus O ( V E ) idő alatt {\displaystyle O(VE)}
és egy randomizált algoritmus O ~ ( V 2.376 ) {\displaystyle {\tilde {O}}(V^{2.376})} időben.
.
- Kétrészes gráfok esetén, ha egyetlen maximális egyezést találunk, egy determinisztikus algoritmus O ( V + E ) {\displaystyle O(V+E)} időben fut.
.
Online bipartit illesztésSzerkesztés
Az online illesztési algoritmus kifejlesztésének problémájával először Richard M. Karp, Umesh Vazirani és Vijay Vazirani foglalkozott 1990-ben.
Az online környezetben a bipartit gráf egyik oldalára egyesével érkeznek csomópontok, amelyeket vagy azonnal illeszteni kell a gráf másik oldalára, vagy el kell vetni őket. Ez a titkárnői probléma természetes általánosítása, és az online hirdetési aukciókra is alkalmazható. A legjobb online algoritmus a súlyozatlan maximalizálás esetére, véletlenszerű érkezési modellel, 0,696-os versenyképességi arányt ér el.