Aparellament (teoria de grafs)

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 complet que consisteixi d'arestes sense vèrtexs comuns. L'aparellament bipartit és un cas especial d'un problema sobre una xarxa de flux.

Definicions

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.

Un aparellament màxim (també conegut com a aparellament de cardinalitat màxima) és un aparellament que conté el nombre d'arestes més gran possible. Pot haver múltiples aparellaments màxims. El nombre d'aparellament $\nu (G)$ d'un graf $G$ é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.

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. 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

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. 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

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

Addicionalment, tenim que

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

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

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

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

Una altra definició proporciona el polinomi d'aparellaments com

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

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

Algorismes i complexitat computacional

En grafs bipartits sense pesos

Els problemes d'aparellaments sovint tenen a veure amb grafs bipartits. El problema de trobar un aparellament bipartit màxim (sovint anomenat aparellament bipartit amb cardinalitat màxima) en un graf bipartit $G=(V=(X,Y),E)$ é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 x ∈ X a un vèrtex y ∈ Y, 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 $O(E)$, la complexitat en temps de l'algorisme és $O(VE)$. Aquesta solució és equivalent a afegir una super-font $s$ connectada amb tots els vèrtexs de $X$, i un super-pou $t$ connectada a tots els vèrtexs de $Y$, i després trobar un flux màxim des de $s$ fins a $t$. Totes les arestes amb flux des de $X$ fins a $Y$ constitueixen un aparellament màxim.

Una aproximació millorada a aquest enfocament és l'algorisme de Hopcroft-Karp, que té complexitat en temps $O({\sqrt {V}}E)$. Una altra alternativa aleatòria es basa en l'algorisme de multiplicació de matrius ràpida, que té una complexitat de $O(V^{2{,}376})$, que, en teoria, és millor per a grafs suficientment densos, però a la pràctica aquest algorisme és més lent. Finalment, per a grafs dispersos, es pot aconseguir un temps ${\tilde {O}}(E^{10/7})$, amb l'algorisme de Madry basat en fluxos elèctrics.

Addicionalment l'algorisme de Chandran i Hochbaum triga un temps que depèn de la grandària de l'aparellament màxim $k$, que per a $|X|<|Y|$ és $O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right)$. Emprant operacions booleanes sobre paraules de longitud $\lambda$, hom pot millorar encara més la complexitat a $O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2{,}5}}{\lambda }}\right)$.

En grafs bipartits ponderats

En un graf bipartit ponderat, cada aresta té un valor associat. Un aparellament bipartit de pes màxim 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é $O(V^{2}E)$, que fins i tot pot arribar a $O(V^{2}\log {V}+VE)$ amb la utilització de l'algorisme de Dijkstra i el monticle de Fibonacci.

En grafs en general

Existeix un algorisme amb temps $O(V^{2}E)$ 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).

Un altre algorisme (aleatoritzat) de Mucha i Sankowski, basat en la multiplicació de matrius ràpida, dona una complexitat $O(V^{2{,}376})$.

Aparellaments maximals

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. 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. Tots dos problemes es poden aproximar amb factor 2 en temps polinòmic: només cal trobar un aparellament maximal M arbitrari.

Problemes sobre recomptes

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. 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. 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 K_n (amb n parell) ve donat pel doble factorial (n − 1)!!. Els nombres d'aparellaments en grafs complets, sense necessitat que siguin perfectes, venen donats pels nombres de telèfons.

Trobar totes les arestes d'un aparellament màxim

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 $O(VE)$. Existeix un algorisme aleatori que resol aquest problema en temps ${\tilde {O}}(V^{2{,}376})$ . 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; el temps total resultant és $O(V^{1/2}E)$ per a grafs bipartits en general, i $O((V/\log V)^{1/2}E)$ per a grafs bipartits densos amb $E=\Theta (V^{2})$. En els casos on es coneix prèviament un dels aparellaments màxims, els temps total que necessita l'algorisme és $O(V+E)$.

Aplicacions

Aparellaments en grafs en general

• Una estructura de Kekulé d'un compost aromàtic consisteix d'un aparellament perfecte del seu esquelet de carboni, mostrant els emplaçaments dels enllaços dobles a la seva estructura química. Aquestes estructures reben aquest nom per Friedrich August Kekulé von Stradonitz, qui va descobrir que hom pot dotat d'aquesta estructura al benzè (en termes de teoria de grafs, un cicle de 6 vèrtexs).
• L'índex de Hosoya és el nombre d'aparellaments no buits més 1; s'utilitza en investigacions de química computacional i química matemàtica per a compostos orgànics.

Bibliografia

• Lovász, László; Plummer, M. D.. Matching Theory. North-Holland, 1986. ISBN 0-444-87916-1. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. «Chapter 26». A: Introduction to Algorithms. 2a edició. MIT Press and McGraw–Hill, 2001, p. 643-700. ISBN 0-262-53196-8. 
• Frank, András «On Kuhn's Hungarian Method – A tribute from Hungary». Egerváry Research Group, 2004.
• Fredman, Michael L.; Tarjan, Robert E. «Fibonacci heaps and their uses in improved network optimization algorithms». Journal of the ACM, 34, 3, 1987, pàg. 595–615. DOI: 10.1145/28869.28874.
• Cyvin, S. J.; Gutman, Ivan. Kekule Structures in Benzenoid Hydrocarbons. 46. Springer-Verlag, 1988 (Lecture Notes in Chemistry). DOI 10.1007/978-3-662-00892-8. ISBN 978-3-540-18801-8. 
• Karpinski, Marek; Rytter, Wojciech. Fast Parallel Algorithms for Graph Matching Problems. Oxford University Press, 1998. ISBN 978-0-19-850162-6. 

Enllaços externs

• Llibreria C++ de grafs amb implementacions d'aparellaments de cardinalitat màxima