Aparellament (teoria de grafs)

De Viquipèdia
Jump to navigation Jump to search
Un aparellament d'un graf, representat en vermell

En la disciplina matemàtica de la teoria de grafs, un aparellament d'un graf és un conjunt d'arestes sense vèrtexs en comú. També pot ser un graf en la seva totalitat que consisteixi d'arestes sense vèrtexs comuns. L'aparellament bipartit és un cas especial d'un problema sobre una xarxa de flux.

Definicions[modifica]

Donat un graf G = (V,E), un aparellament M de G és un conjunt d'arestes no adjacents dues a dues; és a dir no existeix cap parell d'arestes que posseeixin un vèrtex en comú.

Hom diu que un vèrtex està aparellat (o saturat) si és un extrem d'una de les arestes de l'aparellament. En qualsevol altre cas, hom diu que el vèrtex està desaparellat.

Un aparellament maximal és un aparellament M d'un graf G amb la propietat de què, si una aresta que no pertany a M s'afegeix a M, llavors ja no és un aparellament; és a dir, M és maximal si no és un subconjunt propi de cap altre aparellament de G. En altres paraules, un aparellament M d'un graf G és maximal si tota aresta de G té intersecció no buida amb almenys una aresta de G. La següent figura mostra alguns exemples d'aparellaments (en vermell) sobre tres grafs.

Maximal-matching.svg

Un aparellament màxim (també conegut com a aparellament de cardinalitat màxima)[1] és un aparellament que conté el nombre d'arestes més gran possible. Pot haver múltiples aparellaments màxims. El nombre d'aparellament d'un graf és la grandària d'un aparellament màxim. Cal notar que tot aparellament màxim és maximal, però no tot aparellament maximal és un aparellament màxim. La següent figura il·lustra alguns exemples d'aparellaments màxims en els mateixos tres grafs.

Maximum-matching-labels.svg

Un aparellament perfecte (també conegut com a 1-factor) és un aparellament que conté tots els vèrtexs del graf. És a dir, tot vèrtex del graf és incident a exactament una aredta de l'aparellament. La figura (b) anterior és un exemple d'aparellament perfecte. Tot aparellament perfecte és màxim i per tant maximal. Alguns autors utilitzen el terme aparellament complet.[2][3] Un aparellament perfecte és també una cobertura d'arestes de cardinalitat mínima. Així, ν(G) ≤ ρ(G) , és a dir, la grandària d'un aparellament màxim és més petita o igual a la grandària d'una cobertura d'arestes mínima.

Un aparellament quasiperfecte és aquell on exactament un vèrtex queda sense aparellar. Això només pot succeir quan el graf té un nombre senar de vèrtexs, i en tal cas l'aparellament ha de ser màxim. En la figura anterior, la part (c) mostra un aparellament quasiperfecte.

Donat un aparellament M,

  • un camí alternat és un camí que comença per un vèrtex desaparellat i en el qual les arestes pertanyen alternativament a l'aparellament i a la resta del graf.
  • un camí augmentatiu és un camí alternat que comença i acaba en vèrtexs desaparellats.

Es pot demostrar que un aparellament és màxim si i només si no té cap camí augmentatiu (aquest resultat es coneix també amb el nom de lema de Berge).

Propietats[modifica]

En un graf qualsevol sense vèrtexs aïllats, la suma del nombre d'aparellament i el nombre de cobertura per arestes és igual al nombre de vèrtexs del graf.[4] Si existeix un aparellamen perfecte, llavors tant el nombre d'aparellament com el nombre de cobertura per arestes són iguals a |V| / 2.

Si A i B són dos aparellaments maximals, llavors |A| ≤ 2|B| i |B| ≤ 2|A|. Per veure això, cal observar que tota aresta de B \ A pot ser adjacent, com a màxim, a dues arestes de A \ B perquè A és un aparellament; a més, tota aresta de A \ B és adjacent a una aresta de B \ A per maximalitat de B, d'on

.

Addicionalment, tenim que

.

En particular, això demostra que tot aparellament maximal és una 2-aproximació d'un aparellament màxim, així cim una 2-aproximació d'un aparellament maximal mínim. Aquesta desigualtat no es pot refinar: per exemple, si G és un camí amb 3 arestes i 4 vèrtexs, la grandària d'un aparellament maximal mínim és 1 i la grandària d'un aparellament màxim és 2.

Polinomis d'aparellaments[modifica]

Un polinomi d'aparellaments és una funció generatriu del nombre d'aparellaments amb k arestes en un graf. Sigui G un graf, i sigui mk el nombre d'aparellaments amb k arestes. Un polinomi d'aparellaments de G és

.

Una altra definició proporciona el polinomi d'aparellaments com

,

on n és el nombre de vèrtexs del graf.

Algorismes i complexitat computacional[modifica]

En grafs bipartits sense pesos[modifica]

Els problemes d'aparellaments sovint tenen a veure amb grafs bipartits. El problema de trobar un aparellament bipartit màxim[5] (sovint anomenat aparellament bipartit amb cardinalitat màxima) en un graf bipartit és un dels problemes més simples.

L'algorisme de Ford-Fulkerson pot trobar un tal aparellament a base de trobar un camí augmentatiu des d'un vèrtex xX a un vèrtex yY, i actualitzant l'aparellament M prenent la diferència simètrica d'aquest camí amb M (suposant que existeixi un tal camí). Com que cada camí es pot calcular en temps ,[nota 1] la complexitat en temps de l'algorisme és . Aquesta solució és equivalent a afegir una super-font connectada amb tots els vèrtexs de , i un super-pou connectada a tots els vèrtexs de , i després trobar un flux màxim des de fins a . Totes les arestes amb flux des de fins a constitueixen un aparellament màxim.

Una aproximació millorada a aquest enfocament és l'algorisme de Hopcroft-Karp, que té complexitat en temps . Una altra alternativa aleatòria es basa en l'algorisme de multiplicació de matrius ràpida, que té una complexitat de ,[6] que, en teoria, és millor per a grafs suficientment densos, però a la pràctica aquest algorisme és més lent.[7] Finalment, per a grafs dispersos, es pot aconseguir un temps , amb l'algorisme de Madry basat en fluxos elèctrics.[8]

Addicionalment l'algorisme de Chandran i Hochbaum[7] triga un temps que depèn de la grandària de l'aparellament màxim , que per a és . Emprant operacions booleanes sobre paraules de longitud , hom pot millorar encara més la complexitat a .

En grafs bipartits ponderats[modifica]

En un graf bipartit ponderat, cada aresta té un valor associat. Un aparellament bipartit de pes màxim[5] es defineix com un aparellament on la suma dels valors de l'aparellament tenen un valor màxim. Si el graf no és bipartit complet, hom hi afegeix arestes addicionals amb pes 0. El problema de trobar un tal aparellament es coneix com el problema de l'assignació. L'algorisme hongarès resol el problema de l'assignació i fou un dels primers algorismes d'optimització combinatòria. Utilitza una variant de la cerca del camí més curt en l'algorisme del camí augmentatiu. Si s'utilitza l'algorisme de Bellman-Ford en aquest pas, ell temps d'execució de l'algorisme hongarès esdevé , que fins i tot pot arribar a amb la utilització de l'algorisme de Dijkstra i el monticle de Fibonacci.[9]

En grafs en general[modifica]

Existeix un algorisme amb temps per trobar un aparellament màxim o un aparellament amb pes màxim sobre un graf no bipartit; aquest algorisme, degut a Jack Edmonds, s'anomena mètode de camins, arbres i flors o simplement algorisme d'Edmonds, i utilitza arestes bidirigides. També es pot emprar una generalització d'aquesta tècnica per trobar conjunts independents maximals en grafs sense garres. L'algorisme d'Edmonds ha sofert diverses millores, per tal de trigar un temps O(VE).[10]

Un altre algorisme (aleatoritzat) de Mucha i Sankowski,[6] basat en la multiplicació de matrius ràpida, dóna una complexitat .

Aparellaments maximals[modifica]

Utilitzant un algorisme voraç, hom pot trobar un aparellament maximal. Un aparellament màxim és també un aparellament maximal, i per tant és possible trobar un aparellament maximal més gran en temps polinòmic. Tot i això, no es coneix cap algorisme en temps polinòmic per trobar un aparellament maximal mínim, és a dir, un aparellament maximal que contingui el més petit nombre d'arestes.

Cal observar que un aparellament maximal amb k arestes és un conjunt dominador d'arestes amb k arestes. Recíprocament, si hom té un conjunt dominador d'arestes mínim amb k arestes, hom pot construir un aparellament maximal amb k arestes en temps polinòmic. Per tant, el problema de trobar un aparellament maximal mínim és essencialment igual al problema de trobar un conjunt dominant d'arestes mínim.[11] Se sap que aquests dos problemes d'optimització són NP-difícils; les versions de decisió d'aquests problemes són exemples clàssics de problemes NP-complets.[12] Tots dos problemes es poden aproximar amb factor 2 en temps polinòmic: només cal trobar un aparellament maximal M arbitrari.[13]

Problemes sobre recomptes[modifica]

El nombre d'aparellaments d'un graf es coneix com a índex de Hosoya del graf. El càlcul d'aquesta quantitat és un problema #P-complet, fins i tot per a grafs bipartits.[14] També té complexitat #P-complet el problema de comptar aparellaments perfectes, fins i tot en el cas de grafs bipartits, perquè calcular el permanent d'una matriu arbitrària amb zeros i uns (un altre problema #P-complet) és el mateix que calcular el nombre d'aparellaments perfectes en un graf bipartit, on la matriu donada és la matriu de biadjacència. Tanmateix, existeix una aproximació aleatòria en temps polinòmic per a comptar el nombre d'aparellaments bipartits.[15] Un teorema destacat de Kasteleyn afirma que el nombre d'aparellaments perfectes d'un graf planar es pot calcular exactament en temps polinòmic mitjançant l'algorisme FKT.

El nombre d'aparellaments perfectes d'un graf complet Kn (amb n parell) ve donat pel doble factorial (n − 1)!!.[16] Els nombres d'aparellaments en grafs complets, sense necessitat que siguin perfectes, venen donats pels nombres de telèfons.[17]

Trobar totes les arestes d'un aparellament màxim[modifica]

Un dels problemes bàsics en la teoria d'aparellaments és trobar, en un graf donat, totes les arestes que es poden ampliar a un aparellament màxim sobre el graf (hom diu que aquestes arestes són maximalment aparellables, o permeses). El millor algorisme determinista per resoldre aquest problema necessita un temps .[18] Existeix un algorisme aleatori que resol aquest problema en temps .[19] En el cas de grafs bipartits, és possible trobar un aparellament màxim, i després utilitzar-lo per trobar totes les arestes maximalment aparellables en temps lineal;[20] el temps total resultant és per a grafs bipartits en general, i per a grafs bipartits densos amb . En els casos on es coneix prèviament un dels aparellaments màxims, [21] els temps total que necessita l'algorisme és .

Aplicacions[modifica]

Aparellaments en grafs en general[modifica]

Notes[modifica]

  1. Vegeu l'article Notació de Landau

Referències[modifica]

  1. Gibbons, Alan. «Chapter 5». A: Algorithmic Graph Theory. Cambridge University Press, 1985. ISBN 9780521288811. 
  2. Tseng, Frank S.C.; Wei-Pang, Yang «Finding a complete matching with the maximum product on weighted bipartite graphs». Computers & Mathematics with Applications, 25, 5, març 1993, pàg. 65-71. DOI: 10.1016/0898-1221(93)90199-6.
  3. Hirata, Jonathan. «Notes on matching» (pdf). MIT OpenCourseWare.
  4. Gallai, Tibor Ann. Univ. Sci. Budapest. Eötvös Sect. Math., 2, 1959, pàg. 133–138.
  5. 5,0 5,1 West, Douglas Brent. «Chapter 3». A: Introduction to Graph Theory. 2a edició. Prentice Hall, 1999. ISBN 0-13-014400-2. 
  6. 6,0 6,1 Mucha, M.; Sankowski, P. «Maximum Matchings via Gaussian Elimination». Proc. 45th IEEE Symp. Foundations of Computer Science, 2004, pàg. 248–255.
  7. 7,0 7,1 Chandran, Bala G.; Hochbaum, Dorit S. «Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm». Cornwell University Library, 2011. arXiv: 1105.1569. «the theoretically efficient algorithms listed above tend to perform poorly in practice».
  8. Madry, A. «Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back». Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, 2013, pàg. 253–262. arXiv: 1307.2205.
  9. Fredman, Michael L.; Tarjan, Robert Endre «Fibonacci heaps and their uses in improved network optimization algorithms». Journal of the ACM, 34, 3, 1987, pàg. 596–615. DOI: 10.1145/28869.28874.
  10. Micali, S.; Vazirani, V. V. «An algorithm for finding maximum matching in general graphs». Proc. 21st IEEE Symp. Foundations of Computer Science, 1980, pàg. 17–27. DOI: 10.1109/SFCS.1980.12.
  11. Yannakakis, Mihalis; Gavril, Fanica «Edge dominating sets in graphs». SIAM Journal on Applied Mathematics, 38, 3, 1980, pàg. 364–372. DOI: 10.1137/0138030.
  12. Garey, Michael R.; Johnson, David S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, 1979. ISBN 0-7167-1045-5. . La versió de decisió del conjunt dominant d'arestes es discuteix en l'apartat del problema del conjunt dominant, que és el problema GT2 de l'Apèndix A1.1. La versió de decisió de l'aparellament maximal mínim és el problema GT10 de l'Apèndix A1.1.
  13. Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer. DOI 10.1007/978-3-642-58412-1. ISBN 978-3-642-63581-6. . La versió d'optimització del conjunt dominador d'arestes mínim és el problema GT3 de l'Apèndix B (pàgina 370). La versió d'optimització de l'aparellament maximal mínim és el problema GT10 de l'Apèndix B (pàgina 374).
  14. Valiant, Leslie «The Complexity of Enumeration and Reliability Problems». SIAM J. Comput., 8, 3, pàg. 410–421. DOI: 10.1137/0208032. ISSN: 1095-7111.
  15. Bezáková, Ivona; Štefankovič, Daniel; Vazirani, Vijay V.; Vigoda, Eric «Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems». SIAM Journal on Computing, 37, 5, 2008, pàg. 1429–1454. DOI: 10.1137/050644033.
  16. Callan, David «A combinatorial survey of identities for the double factorial». Cornell University Library, 2009. arXiv: 0906.1317.
  17. Tichy, Robert F.; Wagner, Stephan «Extremal problems for topological indices in combinatorial chemistry». Journal of Computational Biology, 12, 7, 2005, pàg. 1004–1013. DOI: 10.1089/cmb.2005.12.1004.
  18. de Carvalho, Marcelo H.; Cheriyan, Joseph «An algorithm for ear decompositions of matching-covered graphs». Proc. ACM/SIAM Symposium on Discrete Algorithms (SODA), 2005, pàg. 415–423.
  19. Rabin, Michael O.; Vazirani, Vijay V. «Maximum matchings in general graphs through randomization». J. of Algorithms, 10, 1989, pàg. 557–567. DOI: 10.1016/0196-6774(89)90005-9.
  20. Tassa, Tamir «Finding all maximally-matchable edges in a bipartite graph». Theoretical Computer Science, 423, 2012, pàg. 50–58. DOI: 10.1016/j.tcs.2011.12.071.
  21. Gionis, Aris; Mazza, Arnon; Tassa, Tamir «k-Anonymization revisited». International Conference on Data Engineering (ICDE), 2008.
  22. Trinajstić, Nenad; Klein, Douglas J.; Randić, Milan International Journal of Quantum Chemistry, 30, S20, 1986, pàg. 699–742. DOI: 10.1002/qua.560300762..

Bibliografia[modifica]

Enllaços externs[modifica]