Accoppiamento (teoria dei grafi)

Da Wikipedia, l'enciclopedia libera.

Nella disciplina matematica della teoria dei grafi, un accoppiamento o abbinamento (in inglese matching) o insieme degli spigoli indipendenti in un grafo è un insieme di spigoli senza vertici comuni. Può trattarsi anche di un intero grafo composto da spigoli senza vertici comuni.

Definizione[modifica | modifica wikitesto]

Dato un grafo G = (V,E), un accoppiamento M in G è un insieme di spigoli a coppie non adiacenti; cioè, non ci sono due spigoli che condividono un vertice comune.

Un vertice è accoppiato (o saturato) se è un estremo di uno degli spigoli nell'abbinamento. Altrimenti il vertice è non accoppiato.

Un accoppiamento massimale è un accoppiamento M di un grafo G con la proprietà che se un qualsiasi spigolo non in M è aggiunto a M, non è più un accoppiamento, cioè, M è massimale se non è un sottoinsieme proprio di qualsiasi altro accoppiamento nel grafo G. In altre parole, un accoppiamento M di un grafo G è massimale se ogni spigolo in G ha un'intersezione non vuota con almeno uno spigolo in M. La figura seguente mostra esempi di accoppiamenti massimali (rossi) in tre grafi.

Maximal-matching.svg

Un accoppiamento massimo (noto anche come accoppiamento con cardinalità massima[1]) è un accoppiamento che contiene il massimo numero possibile di spigoli. Ci possono essere molti accoppiamenti massimi. Il numero di accoppiamenti \nu(G) di un grafo G è la dimensione di un accoppiamento massimo. Si noti che ogni accoppiamento massimo è massimale, ma non ogni accoppiamento massimale è un accoppiamento massimo. La figura seguente mostra esempi di accoppiamenti massimi negli stessi tre grafi.

Maximum-matching-labels.svg

Un accoppiamento perfetto (conosciuto anche come 1-fattore) è un accoppiamento che accoppia tutti i vertici del grafo. Cioè, ogni vertice del grafo è incidente esattamente a uno spigolo dell'accoppiamento. La Figura (b) sopra è un esempio di un accoppiamento perfetto. Ogni accoppiamento perfetto è massimo e quindi massimale. In una parte della letteratura, si usa il termine accoppiamento completo. Nella figura sopra, solo la parte (b) mostra un accoppiamento perfetto. Un accoppiamento perfetto è anche una copertura degli spigoli di dimensione minima. Perciò, \nu(G) \le \rho(G), cioè, la dimensione di un accoppiamento massimo non è maggiore della dimensione di una copertura minima dei vertici.

Un accoppiamento quasi perfetto è quello in cui esattamente un vertice non è accoppiato. Questo può avvenire soltanto quando il grafo ha un numero dispari di vertici, e tale accoppiamento deve essere massimo. Nella figura sopra, la parte (c) mostra un accoppiamento quasi perfetto. Se, per ogni vertice in un grafo, c'è un accoppiamento quasi perfetto che omette soltanto quel vertice, il grafo è chiamato anche critico rispetto ai fattori.

Dato un accoppiamento M,

  • un cammino alternante è un cammino in cui gli spigoli appartengono alternativamente all'accoppiamento e non all'accoppiamento.
  • un cammino aumentante è un cammino alternante che inizia da e finisce sui vertici liberi (non accoppiati).

Si può dimostrare che un accoppiamento è massimo se e solo se non ha alcun cammino aumentante. (Questo risultato è chiamato a volte lemma di Berge.)

Proprietà[modifica | modifica wikitesto]

In qualsiasi grafo senza vertici isolati, la somma del numero di accoppiamenti e del numero delle coperture degli spigoli uguaglia il numero dei vertici.[2] Se c'è un abbinamento perfetto, allora sia il numero degli accoppiamenti che il numero delle coperture degli spigoli sono |V| / 2.

Se A e B somo due accoppiamenti massimali, allora |A| ≤ 2|B| e |B| ≤ 2|A|. Per vedere questo, si osservi che ciascuno spigolo in B \ A può essere adiacente al massimo a due spigoli in A \ B perché A è un accoppiamento; inoltre ogni spigolo in A \ B è adiacente a uno spigolo B \ A per massimalità di B, quindi

|A \setminus B| \le 2|B \setminus A|.

Inoltre otteniamo che

|A| = |A \cap B| + |A \setminus B| \le 2|B \cap A| + 2|B \setminus A| = 2|B|.

In particolare, questo mostra che qualsiasi accoppiamento massimale è una 2-approssimazione di un accoppiamento massimo e anche una 2-approssimazione di un accoppiamento massimale minimo. Questa disuguaglianza è stretta: ad esempio, se G è un cammino con 3 spigoli e 4 nodi, la dimensione di un accoppiamento massimale minimo è 1 e la dimensione di un accoppiamento massimo è 2.

Polinomi degli accoppiamenti[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Polinomio degli accoppiamenti.

Una funzione generatrice del numero di accoppiamenti di k spigoli in un grafo si chiama polinomio degli accoppiamenti. Sia G un grafo e mk il numero di accoppiamenti di k spigoli. Un polinomio degli accoppiamenti di G è

\sum_{k\geq0} m_k x^k.

Un'altra definizione dà il polinomio corrispondente come

\sum_{k\geq0} (-1)^k m_k x^{n-2k},

dve n è il numero dei vertici nel grafo. Ogni tipo ha i suoi usi; per altre informazioni vedi l'articolo sui polinomi degli accoppiamenti.

Algoritmi e complessità computazionale[modifica | modifica wikitesto]

Nei grafi bipartiti non ponderati[modifica | modifica wikitesto]

I problemi di accoppiamento riguardano spesso i grafi biparitit. Trovare un accoppiamento bipartito massimo[3] (spesso chiamato accoppiamento bipartito con cardinalità massima) in un grafo bipartito G=(V=(X,Y),E) è forse il problema più semplice.

L'algoritmo dei cammini aumentanti lo trova ricavando un cammino aumentante da ogni x \in X a \ Y e aggiungendolo all'accoppiamento se esiste. Poiché ciascun cammino può essere trovato nel tempo \ O(E), il tempo di esecuzione è \ O(V E). Questa soluzione è equivalente ad aggiungere una super sorgente s con gli spigoli a tutti i vertici in \ X, e un super sink \ t con gli spigoli a tutti i vertici in \ Y, e a trovare un flusso massimale da \ s a \ t. Tutti gli spigoli con flusso da \ X a \ Y costituiscono allora un accoppiamento massimo.

Un miglioramento in questo procedimento è l'algoritmo di Hopcroft–Karp, che si svolge nel tempo O(\sqrt{V}E). Un altro approccio si basa sull'algoritmo veloce della moltiplicazione di matrici e dà complessità O(V^{2,376}),[4] che in teoria è migliore per grafi sufficientemente densi, ma in pratica l'algoritmo è più lento.[5]

Nei grafi bipartiti ponderati[modifica | modifica wikitesto]

In un grafo bipartito ponderato, ciascuno spigolo ha un valore associato. Un accoppiamento massimo di grafi bipartiti[3] è definito come un accoppiamento dove la somma dei valori degli spigoli nell'accoppiamento ha un valore massimale. Se il grafo non è bipartito completo, si inseriscono spigoli mancanti con valore zero. Trovare tale accoppiamento è noto come problema dell'assegnazione. Il celebre algoritmo ungherese risolve il problema dell'assegnazione e fu uno degli inizi degli algoritmi di ottimizzazione combinatoria. Esso usa una ricerca modificata del percorso più breve nell'algorimo dei cammini aumentanti. Se si usa l'algoritmo di Bellman-Ford per questo stadio, il tempo di esecuzione dell'algoritmo ungherese diventa O(V^2 E), ovvero il costo degli spigoli può essere variato con un potenziale per ottenere il tempo di esecuzioneO(V^2 \log{V} + V E) con l'algoritmo di Dijkstra e l'ammasso di Fibonacci.[6]

Nei grafi generali[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Algoritmo di accoppiamento di Edmonds.

C'è un algoritmo in tempo polinomiale per trovare un accoppiamento massimo o un accoppiamento di peso massimo in un grafo che non è bipartito; si deve a Jack Edmonds, è chiamato metodo dei cammini, alberi e fiori o semplicemente algoritmo di Edmonds, e usa grafi bidiretti. Una generalizzazione della stessa tecnica si può usare anche per trovare i massimi insiemi indipendenti nei grafi senza stella. L'algoritmo di Edmonds è stato successivamente migliorato per funzionare nel tempo O(\sqrt{V}E), uguagliando il tempo per l'accoppiamento massimo bipartito.[7]

Un altro algoritmo (randomizzato) di Mucha e Sankowski,[4] basato sull'algoritmo veloce per la moltiplicazione di matrici, dà una la complessità O(V^{2,376}).

Accoppiamenti massimali[modifica | modifica wikitesto]

Un accoppiamento massimale si può trovare con un semplice algoritmo goloso. Un accoppiamento massimo è anche un accoppiamento massimale, e quindi è possibile trovare un accoppiamento massimale più grande in tempo polinomiale. Tuttavia, non si conosce nessun algoritmo in tempo polinomiale per trovare un accoppiamento massimale minimo, cioè, un accoppiamento massimale che contiene il più piccolo numero possibile di spigoli.

Si noti che un accoppiamento massimale con k spigoli è un insieme dominante di spigoli con k spigoli. Per converso, se abbiamo un minimo insieme dominante di spigoli con k spigoli, possiamo costruire un accoppiamento massimale con k spigoli in tempo polinomiale. Perciò il problema di trovare un accoppiamento massimale minimo è essenzialmente uguale al problema di trovare un minimo insieme dominante di spigoli.[8] È noto che ambedue questi problemi di ottimizzazione sono NP-difficili; le versioni di decisione di questi problemi sono esempi classici di problemi NP-completi.[9] Entrambi i problemi possono essere approssimati entro un fattore 2 in tempo polinomiale: si trovi semplicemente un accoppiamento massimale M arbitrario.[10]

Problemi di conteggio[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Indice di Hosoya.

Il numero di accoppiamenti in un grafo è noto come l'indice di Hosoya del grafo. Computare questa quantità è #P-completo. Rimane #P-completo nel caso speciale del conteggio del numero di accoppiamenti perfetti in un dato grafo bipartito, perché computare il permanente di un'arbitraria matrice 0–1 (un altro problema #P-completo) è lo stesso che computare il numero di accoppiamenti perfetti nel grafo bipartito avente la matrice data come sua matrice delle biadiacenze. Tuttavia, esiste uno schema di approssimazione randomizzato completamente in tempo polinomiale per contare il numero di accoppiamenti bipartiti.[11] Un notevole teorema di Kasteleyn afferma che il numero di accoppiamenti perfetti in un grafo planare può essere computato esattamente in tempo polinomiale attraverso l'algoritmo FKT.

Il numero di accoppiamenti perfetti in un grafo completo Kn (con n pari) è dato dal doppio fattoriale (n − 1)!!.[12] I numeri di accoppiamenti nei grafi completi, senza costringere gli accoppiamenti a essere perfetti, sono dati dai numeri telefonici.[13]

Trovare tutti gli spigoli massimamente accoppiabili[modifica | modifica wikitesto]

Uno dei problemi basilari della teoria degli accoppiamenti è trovare in un dato grafo tutti gli spigoli che possono essere estesi a un accoppiamento massimo del grafo. (Tali spigoli sono chiamati spigoli massimamente accoppiabili, o spigoli consentiti.) Il miglior algoritmo deterministico per risovere questo problema nei grafi generali si esegue nel tempo O(VE) .[14] Esiste un algoritmo randomizzato che risolve questo problema nel tempo \tilde{O}(V^{2.376}) .[15] Nel caso di grafi bipartiti, è possibile trovare un unico accoppiamento massimo e poi usarlo per trovare tutti gli spigoli massimamente accoppiabili in tempo lineare;[16] il tempo totale di esecuzione risultante è O(V^{1/2}E) per i grafi bipartiti generali e O((V/\log V)^{1/2}E) per i grafi bipartiti densi con E=\Theta(V^2). Nei casi in cui uno degli accoppiamenti massimi si conosce in anticipo,[17] il tempo totale di esecuzione dell'algoritmo è O(V+E).

Caratterizzazioni e note[modifica | modifica wikitesto]

Il teorema di König afferma che, nei grafi bipartiti, l'accoppiamento massimo è uguale come dimensione alla copertura minima dei vertici. Attraverso questo risultato, i problemi della copertura minima dei vertici, del massimo insieme indipendente e della massima biciclica dei vertici per i grafi bipartiti possono essere risolti in tempo polinomiale.

Il teorema dei matrimoni (o teorema di Hall) fornisce una caratterizzazione per i grafi bipartiti che hanno un accoppiamento perfetto e il teorema di Tutte fornisce una caratterizzazione per i grafi arbitrari.

Un accoppiamento pefetto è un sottografo 1-regolare ricoprente, conosciuto anche come 1-fattore. In generale, un sottografo k-regolare ricoprente è un k-fattore.

Applicazioni[modifica | modifica wikitesto]

Una struttura di Kekulé di un composto aromatico consiste in un accoppiamento perfetto del suo scheletro di carbonio, che mostra le localizzazioni dei legami doppi della struttura chimica. queste strutture prendono il nome da Friedrich August Kekulé von Stradonitz, il quale dimostrò che al benzene (in termini di teoria dei grafi, un ciclo con 6 vertici) può essere attribuita tale struttura.[18]

L'indice di Hosoya è il numero di accoppiamenti non vuoti più uno; si usa nelle indagini di chimica computazionale e di chimica matematica sui composti organici.

Note[modifica | modifica wikitesto]

  1. ^ Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Capitolo 5.
  2. ^ Tibor Gallai, Über extreme Punkt- und Kantenmengen in Ann. Univ. Sci. Budapest. Eötvös Sect. Math., vol. 2, 1959, pp. 133–138..
  3. ^ a b Douglas Brent West, Capitolo 3 in Introduction to Graph Theory, 2ª ed., Prentice Hall, 1999, ISBN 0-13-014400-2.
  4. ^ a b M. Mucha, Sankowski, P., Maximum Matchings via Gaussian Elimination in Proc. 45th IEEE Symp. Foundations of Computer Science, 2004, pp. 248–255.
  5. ^ Bala G. Chandran e Dorit S. Hochbaum, Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm, 2011, arXiv:1105.1569.
    «gli algoritmi teoricamente efficienti elencati sopra in pratica tendono a funzionare male».
  6. ^ Michael L. Fredman, Tarjan, Robert Endre, Fibonacci heaps and their uses in improved network optimization algorithms in Journal of the ACM, vol. 34, nº 3, 1987, pp. 596–615, DOI:10.1145/28869.28874.
  7. ^ S. Micali, Vazirani, V. V., An \scriptstyle O(\sqrt{|V|}\cdot|E|) algorithm for finding maximum matching in general graphs in Proc. 21st IEEE Symp. Foundations of Computer Science, 1980, pp. 17–27, DOI:10.1109/SFCS.1980.12.
  8. ^ Mihalis Yannakakis, Fanica, Gavril, Edge dominating sets in graphs in SIAM Journal on Applied Mathematics, vol. 38, nº 3, 1980, pp. 364–372, DOI:10.1137/0138030.
  9. ^ Michael R. Garey e David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5. L'insieme dominante di spigoli (versione di decisione) è discusso sotto il problema dell'insieme dominante, che è il problema GT2 nell'Appendice A1.1. Il problema dell'accoppiamento massimale minimo (versione di decisione) è il problema GT10 nell'Appendice A1.1.
  10. ^ Giorgio Ausiello, Crescenzi Pierluigi, Gambosi Giorgio, Kann Viggo, Marchetti-Spaccamela Alberto, Protasi Marco, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, 2003.. Il minimo insieme dominante di spigoli (versione di ottimizzazione) è il problema GT3 nell'Appendice B (pagina 370). L'accoppiamento massimale minimo (versione di ottimizzazione) è il problema GT10 nell'Appendice B (pagina 374). Vedi anche Minimum Edge Dominating Set e Minimum Maximal Matching nel compendio in rete.
  11. ^ Ivona Bezáková, Štefankovič Daniel, Vazirani Vijay V., Vigoda Eric, Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems in SIAM Journal on Computing, vol. 37, nº 5, 2008, pp. 1429–1454, DOI:10.1137/050644033.
  12. ^ David Callan, A combinatorial survey of identities for the double factorial, 2009..
  13. ^ Robert F. Tichy, Wagner Stephan, Extremal problems for topological indices in combinatorial chemistry in Journal of Computational Biology, vol. 12, nº 7, 2005, pp. 1004–1013, DOI:10.1089/cmb.2005.12.1004..
  14. ^ Marcelo H. de Carvalho e Joseph Cheriyan, An O(VE) algorithm for ear decompositions of matching-covered graphs in Proc. ACM/SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 415–423.
  15. ^ Michael O. Rabin e Vijay V. Vazirani, Maximum matchings in general graphs through randomization in J. of Algorithms, vol. 10, 1989, pp. 557–567.
  16. ^ Tamir Tassa, Finding all maximally-matchable edges in a bipartite graph in Theoretical Computer Science, vol. 423, 2012, pp. 50–58, DOI:10.1016/j.tcs.2011.12.071.
  17. ^ Aris Gionis, Arnon Mazza e Tamir Tassa, k-Anonymization revisited in International Conference on Data Engineering (ICDE), 2008, pp. 744–753.
  18. ^ Vedi, ad es., Nenad Trinajstić, Douglas J. Klein e Milan Randić, On some solved and unsolved problems of chemical graph theory in International Journal of Quantum Chemistry, vol. 30, S20, 1986, pp. 699–742, DOI:10.1002/qua.560300762..

Ulteriori letture[modifica | modifica wikitesto]

  1. László Lovász e M. D. Plummer, Matching Theory, North-Holland, 1986, ISBN 0-444-87916-1.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduzione agli algoritmi, 2ª ed., MIT Press e McGraw–Hill, 2001, Capitolo 26, pp. 643–700, ISBN 0-262-53196-8.
  3. András Frank, On Kuhn's Hungarian Method – A tribute from Hungary (rapporto tecnico), Egerváry Research Group, 2004.
  4. Michael L. Fredman e Robert E. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms in Journal of the ACM, vol. 34, nº 3, 1987, pp. 595–615, DOI:10.1145/28869.28874.
  5. S. J. Cyvin e Ivan Gutman, Kekule Structures in Benzenoid Hydrocarbons, Springer-Verlag, 1988.
  6. Marek Karpinski e Wojciech Rytter, Fast Parallel Algorithms for Graph Matching Problems, Oxford University Press, 1998, ISBN 978-0-19-850162-6.


Collegamenti esterni[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica