Ugrás a tartalomhoz

Párosítás

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

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ó

[szerkesztés]

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 gráfhoz tartozó 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

[szerkesztés]

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.[1] 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

Ebből tovább következtetve:

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

[szerkesztés]

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 mk pedig a k-élű párosítások száma. G egyik párosítási polinomja:

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

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

[szerkesztés]

Súlyozatlan páros gráfokban

[szerkesztés]

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[2] a 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 időben megtalálható, az algoritmus futási ideje . Ez a megoldás ekvivalens azzal, hogy hozzáadunk a gráfhoz egy „szuperforrást”, amiből minden csúcsába vezet él, és egy „szupernyelőt”, amibe minden csúcsából vezet él, majd megoldjuk a maximális folyam-problémát -ből -be. Ekkor az -ből -ba folyó élek maximális párosítást fognak alkotni.

Ennek a módszernek a továbbfejlesztése a Hopcroft–Karp-algoritmus, aminek a futásideje. Egy randomizált, a gyors mátrixszorzáson alapuló alternatíva komplexitású,[3] ami a megfelelően sűrű gráfokra elméletben gyorsabb lenne, a gyakorlatban azonban lassabbnak bizonyult.[4] Végül pedig ritka gráfokban is elérhető Madry algoritmusával, ami az elektromos folyamokon alapul.[5]

Említésre méltó még Chandran és Hochbaum algoritmusa,[4] ami a maximális párosítás méretétől függő időben fut, ami esetén . méretű szavakon Boole-algebrai műveleteket végezve a komplexitás tovább javítható: .

Súlyozott páros gráfokban

[szerkesztés]

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)[2] 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 -re változik, vagy az élek költsége elcsúsztatható és így akár futási idő is elérhető a Dijkstra-algoritmus és a Fibonacci-kupac használatával.[6]

Általános gráfokban

[szerkesztés]

Létezik egy nem csak páros gráfokra vonatkozó, 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.[7]

A Mucha–Sankowski-féle randomizált algoritmus,[3] ami a gyors mátrixszorzás-algoritmuson alapul, komplexitást képes elérni.

Maximális párosítások

[szerkesztés]

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.[8] 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.[9] 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.[10]

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

[szerkesztés]

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.[11] 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.[12] 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 Kn (n páros) teljes gráf teljes párosításainak számát az (n − 1)!! dupla faktoriális adja meg.[13] A teljes gráfok összes párosításának a számát a telefonszámok adják meg.[14]

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

[szerkesztés]

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 idő alatt oldják meg ezt a problémát.[15] Létezik randomizált algoritmus, ami ugyanezt a problémát idő alatt oldja meg.[16] 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;[17] a futási idő általános páros gráfokra és sűrű páros gráfokra, ahol . Abban az esetben, ha egy maximális elemszámú párosítás előre ismert,[18] az algoritmus futásideje mindössze .

Karakterizáció és jegyzetek

[szerkesztés]

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

[szerkesztés]

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

[szerkesztés]

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

[szerkesztés]

Kapcsolódó szócikkek

[szerkesztés]

Fordítás

[szerkeszté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.

Jegyzetek

[szerkesztés]
  1. Gallai, Tibor (1959), "Über extreme Punkt- und Kantenmengen", Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2: 133–138.
  2. a b West, Douglas Brent (1999), Introduction to Graph Theory (2nd ed.), Prentice Hall, Chapter 3, ISBN 0-13-014400-2
  3. a b Mucha, M. & Sankowski, P. (2004), "Maximum Matchings via Gaussian Elimination", Proc. 45th IEEE Symp. Foundations of Computer Science, pp. 248–255
  4. a b Chandran, Bala G. & Hochbaum, Dorit S. (2011), Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm.
  5. Madry, A (2013), "Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back", Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pp. 253–262
  6. Fredman, Michael L. & Tarjan, Robert Endre (1987), "Fibonacci heaps and their uses in improved network optimization algorithms", Journal of the ACM 34 (3): 596–615, DOI 10.1145/28869.28874
  7. Micali, S. & Vazirani, V. V. (1980), "An algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science, pp. 17–27, DOI 10.1109/SFCS.1980.12.
  8. Yannakakis, Mihalis & Gavril, Fanica (1980), "Edge dominating sets in graphs", SIAM Journal on Applied Mathematics 38 (3): 364–372, DOI 10.1137/0138030.
  9. Garey, Michael R. & Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5. Edge dominating set (decision version) is discussed under the dominating set problem, which is the problem GT2 in Appendix A1.1. Minimum maximal matching (decision version) is the problem GT10 in Appendix A1.1.
  10. Ausiello, Giorgio; Crescenzi, Pierluigi & Gambosi, Giorgio et al. (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer. Minimum edge dominating set (optimisation version) is the problem GT3 in Appendix B (page 370). Minimum maximal matching (optimisation version) is the problem GT10 in Appendix B (page 374). See also Minimum Edge Dominating Set and Minimum Maximal Matching in the web compendium.
  11. Leslie Valiant, The Complexity of Enumeration and Reliability Problems, SIAM J. Comput., 8(3), 410–421
  12. (2008) „Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems”. SIAM Journal on Computing 37 (5), 1429–1454. o. DOI:10.1137/050644033. 
  13. Callan, David (2009), A combinatorial survey of identities for the double factorial.
  14. Tichy, Robert F. & Wagner, Stephan (2005), "Extremal problems for topological indices in combinatorial chemistry", Journal of Computational Biology 12 (7): 1004–1013, doi:10.1089/cmb.2005.12.1004, <http://www.math.tugraz.at/fosp/pdfs/tugraz_main_0052.pdf>.
  15. de Carvalho, Marcelo H. & Cheriyan, Joseph (2005), "An algorithm for ear decompositions of matching-covered graphs", Proc. ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 415–423.
  16. Rabin, Michael O. & Vazirani, Vijay V. (1989), "Maximum matchings in general graphs through randomization", J. of Algorithms 10: 557–567, DOI 10.1016/0196-6774(89)90005-9.
  17. Tassa, Tamir (2012), "Finding all maximally-matchable edges in a bipartite graph", Theoretical Computer Science 423: 50–58, DOI 10.1016/j.tcs.2011.12.071.
  18. Gionis, Aris; Mazza, Arnon & Tassa, Tamir (2008), "k-Anonymization revisited", International Conference on Data Engineering (ICDE), pp. 744–753.
  19. Lásd pl. Trinajstić, Nenad; Klein, Douglas J. & Randić, Milan (1986), "On some solved and unsolved problems of chemical graph theory", International Journal of Quantum Chemistry 30 (S20): 699–742, DOI 10.1002/qua.560300762.

Irodalom

[szerkesztés]
  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

[szerkesztés]