Párosítás

A matematika, azon belül a gráfelmélet területén egy párosítás (angolul: matching) vagy független élhalmaz adott gráfon belül közös csúccsal nem rendelkező élek halmaza – tehát olyan élek halmaza, melyek páronként csúcsdiszjunktak. Ha a párosítás a gráf összes csúcsát lefedi, neve teljes párosítás vagy feszítő párosítás. A G gráf párosítási száma – jelölése α'(G) – a legnagyobb párosításának elemszáma.

A páros gráfok párosítása a folyamprobléma speciális esete.

Definíció

Adott G = (V,E) gráfban egy M párosítás páronként nem szomszédos élek egy halmaza; tehát nincs a halmazban két olyan él, amelyeknek bármely csúcsa közös.

Egy csúcs párosított (matched, saturated) ha adott párosítás valamely élének végpontja. Egyébként a csúcs párosítatlan (unmatched).

Egy maximális párosítás a G gráfnak olyan M párosítása, melyre igaz, hogy a gráf bármely M-en kívüli élét hozzávéve M-hez az már nem párosítás; más megfogalmazásban M maximális, ha nem valódi részhalmaza a G gráf egyetlen párosításának sem. Ami ezzel ekvivalens, egy G gráf M párosítása pontosan akkor maximális, ha minden G-beli élnek legalább egy M-beli éllel van nem üres metszete. A következő ábra három gráfban mutat példát maximális párosításokra (pirossal).

A maximális elemszámú párosítás (angolul: maximum matching vagy maximal cardinality matching) olyan párosítás, ami a lehető legnagyobb számú élet tartalmazza. Egy gráfban több ilyen is lehet. A $G$ gráfhoz tartozó $\nu (G)$ vagy α'(G) párosítási szám (matching number) a maximális elemszámú párosítás nagysága. Nem minden maximális párosítás maximális elemszámú, de minden maximális elemszámú párosítás szükségszerűen maximális párosítás. A következő ábra az előbbi három gráfban mutat példát maximális elemszámú párosításokra (pirossal).

A teljes párosítás (perfect matching, complete matching) vagy 1-faktor olyan párosítás, ami a gráf minden csúcsát tartalmazza. Tehát a gráf minden csúcsa a párosítás pontosan egy élében szerepel. A fenti példák közül egyedül a (b) ábrán látható teljes párosítás. Minden teljes párosítás maximális elemszámú párosítás, így egyben maximális párosítás is. Egy teljes párosítás egyben minimális éllefogás. Így, ν(G) ≤ ρ(G) , tehát a maximális elemszámú párosítás nem nagyobb a minimális éllefogásnál.

A majdnem teljes párosítás (near-perfect matching) olyan párosítás, ahol pontosan egy csúcs marad párosítatlan. Ez akkor történik, ha a gráf csúcsainak száma páratlan; az ilyen párosítás maximális elemszámú. A fenti ábrán a (c) mutat majdnem teljes párosítást. Ha egy gráf minden csúcsához tartozik azt az egy csúcsot kihagyó teljes párosítás, a gráf faktorkritikus.

Adott M párosítást tekintve,

• Egy alternáló út vagy majdnem javító út (alternating path) olyan út, ami párosítatlan csúcson kezdődik és az egymást követő élek váltakozva a párosításhoz tartoznak, illetve nem tartoznak a párosításhoz.
• Egy javító út vagy bővítő út (augmenting path) olyan alternáló út, ami párosítatlan csúcson kezdődik és azon is végződik.

Bizonyítható, hogy egy párosítás pontosan akkor maximális elemszámú, ha nem tartozik hozzá javító út (ez az eredmény Berge-lemma néven is ismert).

Tulajdonságok

Bármely izolált csúcsok nélküli gráfban a párosítási szám és az éllefogási szám (a minimális elemszámú éllefogás elemszáma) összesen a gráf csúcsainak számát adja ki. Ha létezik teljes párosítás, akkor a párosítási szám és az éllefogási szám is |V| / 2.

Ha A és B is maximális párosítás, akkor igaz, hogy |A| ≤ 2|B| és |B| ≤ 2|A|. Ennek belátásához vegyük észre, hogy a B \ A bármelyik éle az A \ B legfeljebb két élével lehet szomszédos, hiszen A párosítás; továbbá minden A \ B-beli él szomszédos B \ A egy élével B maximális volta miatt, ezért

$|A\setminus B|\leq 2|B\setminus A|.$

Ebből tovább következtetve:

$|A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.$

A fentiekből az is látszik, hogy bármely maximális párosítás tekinthető a maximális elemszámú párosítás 2-approximációjának, továbbá egy minimális elemszámú maximális párosítás 2-approximációjának is. Az egyenlőtlenség éles: például ha G egy 3 élből és 4 csúcsból álló útgráf, akkor a min-max párosítás 1, míg a maximális elemszámú párosítás 2 méretű.

Párosítási polinomok

Az adott gráf k-élű párosításait előállító generátorfüggvényt párosítási polinomnak nevezzük. Legyen G gráf és m_k pedig a k-élű párosítások száma. G egyik párosítási polinomja:

$\sum _{k\geq 0}m_{k}x^{k}.$

A párosítási polinom egy másik definíciója:

$\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},$

ahol n a gráf csúcsainak számát jelöli. Mindkét polinomnak más-más felhasználási területe van.

Algoritmusok és számítási bonyolultság

Súlyozatlan páros gráfokban

A párosítási problémákat gyakran páros gráfokban vizsgálják. Egy páros gráf maximális elemszámú párosítása a $G=(V=(X,Y),E)$ páros gráfban az egyszerű problémák közé tartozik.

A Ford–Fulkerson-algoritmus úgy találja meg ezt a párosítást, hogy újra és újra javított utat keres valamely x ∈ X-ből valamely y ∈ Y-ba, és az M párosítást frissíti az adott út (ha az létezik) és az M szimmetrikus differenciájával. Mivel az összes út $\ O(E)$ időben megtalálható, az algoritmus futási ideje $\ O(VE)$. Ez a megoldás ekvivalens azzal, hogy hozzáadunk a gráfhoz egy $s$ „szuperforrást”, amiből $\ X$ minden csúcsába vezet él, és egy $\ t$ „szupernyelőt”, amibe $\ Y$ minden csúcsából vezet él, majd megoldjuk a maximális folyam-problémát $\ s$-ből $\ t$-be. Ekkor az $\ X$-ből $\ Y$-ba folyó élek maximális párosítást fognak alkotni.

Ennek a módszernek a továbbfejlesztése a Hopcroft–Karp-algoritmus, aminek $O({\sqrt {V}}E)$ a futásideje. Egy randomizált, a gyors mátrixszorzáson alapuló alternatíva $O(V^{2,376})$ komplexitású, ami a megfelelően sűrű gráfokra elméletben gyorsabb lenne, a gyakorlatban azonban lassabbnak bizonyult. Végül pedig ritka gráfokban ${\tilde {O}}(E^{10/7})$ is elérhető Madry algoritmusával, ami az elektromos folyamokon alapul.

Említésre méltó még Chandran és Hochbaum algoritmusa, ami a $k$ maximális párosítás méretétől függő időben fut, ami $|X|<|Y|$ esetén $O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right)$. $\lambda$ méretű szavakon Boole-algebrai műveleteket végezve a komplexitás tovább javítható: $O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2.5}}{\lambda }}\right)$.

Súlyozott páros gráfokban

Egy súlyozott páros gráfban minden élhez tartozik egy számérték. Egy páros gráf maximális súlyozású párosítása (maximum weighted bipartite matching) azt a párosítást jelenti, ahol a párosításban szereplő élekhez tartozó értékek összege maximális. Ha nem teljes páros gráfról van szó, a hiányzó éleket 0 értékkel beillesztjük. Az ilyen párosítás előállításának feladata úgy is ismert, mint a hozzárendelési probléma. A hozzárendelési problémát megoldó magyar módszer a kombinatorikus optimalizálási algoritmusok egyik első példája volt. A javító út-algoritmusban módosított legrövidebb út-keresés egy változatát használja. Ha ebben a lépésben a Bellman–Ford-algoritmust használják, a magyar módszer futási ideje $O(V^{2}E)$-re változik, vagy az élek költsége elcsúsztatható és így akár $O(V^{2}\log {V}+VE)$ futási idő is elérhető a Dijkstra-algoritmus és a Fibonacci-kupac használatával.

Általános gráfokban

Létezik egy nem csak páros gráfokra vonatkozó, $O(V^{2}E)$ idejű algoritmus maximális elemszámú párosítás vagy maximális súlyú párosítás keresésére; ez a Jack Edmondsnak köszönhető utak, fák, virágok-módszer vagy egyszerűen Edmonds-algoritmus, aminek egyik fő ismérve, hogy a páratlan köröket (virágokat) egy-egy csúcsba húzza össze. Az Edmonds-algoritmus technikájának általánosítása alkalmas maximális elemszámú független halmazok megtalálására karommentes gráfokban. Az Edmonds-algoritmus futásidejét feljavították O(√VE)-ra, ami a páros gráfok maximális elemszámú párosításával egyezik meg.

A Mucha–Sankowski-féle randomizált algoritmus, ami a gyors mátrixszorzás-algoritmuson alapul, $O(V^{2,376})$ komplexitást képes elérni.

Maximális párosítások

Egy maximális párosítás egyszerű mohó algoritmussal megtalálható. Egy maximális elemszámú párosítás egyben maximális párosítás is, ezért a legnagyobb maximális párosítás polinomiális időben megtalálható. Nem ismert azonban polinomiális idejű algoritmus a minimális értékű maximális párosítás előállítására; tehát olyan maximális párosításról van szó, ami a lehető legkisebb számú élet tartalmazza.

Vegyük észre, hogy egy k élet tartalmazó maximális párosítás egyben egy k élet tartalmazó domináló élhalmaz. Fordítva, ha adott egy k élet tartalmazó minimális domináló élhalmaz, abból polinomiális időben konstruálható k élet tartalmazó maximális párosítás. Épp ezért a minimális értékű maximális párosítás problémája egyenértékű a minimális domináló élhalmaz megkeresésének problémájával. Mindkét optimalizálási probléma NP-nehéz; ezen problémák eldöntési verziói az NP-teljes problémák klasszikus példái. Mindkét probléma 2-approximálható polinomiális időben: egyszerűen meg kell keresni egy tetszőleges maximális párosítást.

Leszámlálási problémák

A gráfban lévő összes párosítás száma egy gráftulajdonság, amit a gráf Hosoya-indexének neveznek. Kiszámítása #P-teljes probléma, még páros gráfokra is. A teljes párosítások leszámlálása is #P-teljes, még páros gráfokban is, mivel egy tetszőleges 0–1 mátrix permanensének kiszámítása (egy másik #P-teljes probléma) megegyezik egy olyan páros gráf teljes párosításainak leszámlálásával, melynek adott mátrix a páros-szomszédsági mátrixa (biadjacency matrix). Létezik azonban a páros gráfok párosításainak megszámlálására polinomiális idejű randomizált approximációs megoldás. Kasteleyn egy tétele szerint egy síkgráf teljes párosításainak száma polinomiális időben megszámolható az FKT-algoritmussal.

A K_n (n páros) teljes gráf teljes párosításainak számát az (n − 1)!! dupla faktoriális adja meg. A teljes gráfok összes párosításának a számát a telefonszámok adják meg.

A maximálisan párosítható élek megtalálása

A párosításelmélet egyik alapvető problémája adott gráfban az összes olyan él megtalálása, amelyek részét képezhetik egy maximális elemszámú párosításnak. (Az ilyen élek a maximálisan párosítható élek vagy megengedett élek – maximally-matchable/allowed edges.) Általános gráfokban a legjobb determinisztikus algoritmusok $O(VE)$ idő alatt oldják meg ezt a problémát. Létezik randomizált algoritmus, ami ugyanezt a problémát ${\tilde {O}}(V^{2,376})$ idő alatt oldja meg. Páros gráfok esetében járható út egyetlen maximális elemszámú párosítás megkeresése után lineáris időben megkeresni az összes maximálisan párosítható éleket; a futási idő $O(V^{1/2}E)$ általános páros gráfokra és $O((V/\log V)^{1/2}E)$ sűrű páros gráfokra, ahol $E=\Theta (V^{2})$. Abban az esetben, ha egy maximális elemszámú párosítás előre ismert, az algoritmus futásideje mindössze $O(V+E)$.

Karakterizáció és jegyzetek

A Kőnig-tétel kimondja, hogy páros gráfokban a maximális elemszámú párosítás mérete a minimális csúcslefedés méretével egyezik meg. Ennek az eredménynek az ismeretében a minimális csúcslefedés, a maximális elemszámú független halmaz és a maximális csúcsszámú teljes páros részgráf keresése mind polinomiális időben oldhatók meg páros gráfok esetében.

A Hall-tétel jellemzi azokat a páros gráfokat, melyeknek van teljes párosításuk, míg a Tutte-tétel általános gráfokra terjeszti ki ezt a jellemzést.

Egy teljes párosítás egyben feszítő 1-regulár részgráf, más néven 1-faktor. Általában egy feszítő k-reguláris részgráf k-faktor.

Alkalmazásai

Párosítás általános gráfokban

• Egy aromás vegyület Kekulé-szerkezete a szénvázának teljes párosításából áll, ami megmutatja a kémiai szerkezetében a kettős kötéseket. Ezeket a szerkezeteket August Kekuléról nevezték el, aki megmutatta, hogy a benzol (gráfelméletileg egy 6 csúcsból álló kör) rendelkezik ilyen párosítással.
• A Hosoya-index a nem üres párosítások száma plusz 1; a matematikai kémia és a számítási kémia területén használják szerves vegyületek vizsgálatára.

Páros gráfok párosítása

• A szállítási feladat alproblémaként tartalmazza a páros gráfok párosítását.
• A részfaizomorfizmus-probléma alproblémaként tartalmazza a páros gráfok párosítását.

Kapcsolódó szócikkek

• Dulmage–Mendelsohn-felbontás, egy páros gráf csúcsainak particionálása olyan részhalmazokra, hogy egy él pontosan akkor tartozzon teljes párosításba, ha mindkét végpontja ugyanabba a részhalmazba tartozik
• Élszínezés, egy gráf éleinek particionálása párosításokba
• Párosítás-kizárási szám, a legkevesebb él, melynek törlésére szükség van egy teljes párosítás kizárásához
• Szivárványpárosítás, olyan párosítás egy élszínezett páros gráfban, amiben nincsenek ismétlődő színek.
• Ferdeszimmetrikus gráf, jól használható a párosítások alternáló útkeresésének modellezéséhez
• Stabil párosítás (stabil házasság probléma), olyan párosítás, ahol semelyik két elem sem preferál más partnert, mint amihez párosítva van
• Független csúcshalmaz, olyan csúcsok (tehát nem élek) halmaza, melyek közül semelyik kettő sem szomszédos egymással

Fordítás

Ez a szócikk részben vagy egészben a Matching (graph theory) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Irodalom

1. László Lovász & M. D. Plummer (1986), Matching Theory, North-Holland, ISBN 0-444-87916-1
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001), Introduction to Algorithms (second ed.), MIT Press and McGraw–Hill, Chapter 26, pp. 643–700, ISBN 0-262-53196-8
3. Frank András: On Kuhn's Hungarian Method – A tribute from Hungary Archiválva 2017. augusztus 9-i dátummal a Wayback Machine-ben

1. Michael L. Fredman and Robert E. Tarjan (1987), "Fibonacci heaps and their uses in improved network optimization algorithms", Journal of the ACM 34 (3): 595–615, DOI 10.1145/28869.28874
2. S. J. Cyvin & Ivan Gutman (1988), Kekule Structures in Benzenoid Hydrocarbons, Springer-Verlag
3. Marek Karpinski and Wojciech Rytter (1998), Fast Parallel Algorithms for Graph Matching Problems, Oxford University Press, ISBN 978-0-19-850162-6

További információk

• Németh Kinga: Párosítások (BSc szakdolgozat)
• A graph library with Hopcroft–Karp and Push–Relabel-based maximum cardinality matching implementation