Accoppiamento (teoria dei grafi)

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

Definizione

Dato un grafo G = (V,E), un accoppiamento M in G è un insieme di archi a coppie non adiacenti; cioè, non ci sono due archi 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 arco 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 arco in G ha un'intersezione non vuota con almeno uno arco in M. La figura seguente mostra esempi di accoppiamenti massimali (rossi) in tre grafi.

Un accoppiamento massimo (noto anche come accoppiamento con cardinalità massima) è 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.

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)\leq \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à

In qualsiasi grafo senza vertici isolati, la somma del numero di accoppiamenti e del numero delle coperture degli spigoli uguaglia il numero dei vertici. 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|\leq 2|B\setminus A|.$

Inoltre otteniamo che

$|A|=|A\cap B|+|A\setminus B|\leq 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

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

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

Un'altra definizione dà il polinomio corrispondente come

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

dove 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

Nei grafi bipartiti non ponderati

I problemi di accoppiamento riguardano spesso i grafi bipartiti. Trovare un accoppiamento bipartito massimo (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(VE)$. 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})$, che in teoria è migliore per grafi sufficientemente densi, ma in pratica l'algoritmo è più lento.

Nei grafi bipartiti ponderati

In un grafo bipartito ponderato, ciascuno spigolo ha un valore associato. Un accoppiamento massimo di grafi bipartiti è 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'algoritmo 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 esecuzione$O(V^{2}\log {V}+VE)$ con l'algoritmo di Dijkstra e l'ammasso di Fibonacci.

Nei grafi generali

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.

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

Accoppiamenti massimali

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. È noto che ambedue questi problemi di ottimizzazione sono NP-difficili; le versioni di decisione di questi problemi sono esempi classici di problemi NP-completi. Entrambi i problemi possono essere approssimati entro un fattore 2 in tempo polinomiale: si trovi semplicemente un accoppiamento massimale M arbitrario.

Problemi di conteggio

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. 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 K_n (con n pari) è dato dal doppio fattoriale (n − 1)!!. I numeri di accoppiamenti nei grafi completi, senza costringere gli accoppiamenti a essere perfetti, sono dati dai numeri telefonici.

Trovare tutti gli spigoli massimamente accoppiabili

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 risolvere questo problema nei grafi generali si esegue nel tempo $O(VE)$ . Esiste un algoritmo randomizzato che risolve questo problema nel tempo ${\tilde {O}}(V^{2.376})$ . Nel caso di grafi bipartiti, è possibile trovare un unico accoppiamento massimo e poi usarlo per trovare tutti gli spigoli massimamente accoppiabili in tempo lineare; 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, il tempo totale di esecuzione dell'algoritmo è $O(V+E)$.

Caratterizzazioni e note

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 perfetto è un sottografo 1-regolare ricoprente, conosciuto anche come 1-fattore. In generale, un sottografo k-regolare ricoprente è un k-fattore.

Applicazioni

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

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.

Ulteriori letture

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 (PDF) (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.

Altri progetti

Altri progetti

• Wikizionario
• Wikimedia Commons

• Wikizionario contiene il lemma di dizionario «accoppiamento»
• Wikimedia Commons contiene immagini o altri file su accoppiamento

Collegamenti esterni

• (EN) Una libreria di grafi con l'implementazione di accoppiamenti di massima cardinalità basati su Hopcroft–Karp e Push–Relabel, su lemon.cs.elte.hu.
• Appunti sui grafi (PDF), su setticarraro.gov.it (archiviato dall'url originale il 23 giugno 2016).