Corrispondenza di massima cardinalitàModifica
Un problema fondamentale nell’ottimizzazione combinatoria è trovare una corrispondenza massima. Questo problema ha vari algoritmi per diverse classi di grafi.
In un grafo bipartito non pesato, il problema di ottimizzazione è trovare una corrispondenza di massima cardinalità. Il problema è risolto dall’algoritmo di Hopcroft-Karp in tempo O(√VE), ed esistono algoritmi randomizzati più efficienti, algoritmi di approssimazione e algoritmi per classi speciali di grafi come i grafi planari bipartiti, come descritto nell’articolo principale.
Maximum-weight matchingEdit
In un grafo bipartito pesato, il problema di ottimizzazione è quello di trovare una corrispondenza di peso massimo; un problema duale è quello di trovare una corrispondenza di peso minimo. Questo problema è spesso chiamato corrispondenza massima ponderata bipartita, o problema di assegnazione. L’algoritmo ungherese risolve il problema di assegnazione ed è stato uno degli inizi degli algoritmi di ottimizzazione combinatoria. Utilizza una ricerca modificata del percorso più breve nell’algoritmo di incremento del percorso. Se l’algoritmo di Bellman-Ford viene utilizzato per questo passo, il tempo di esecuzione dell’algoritmo ungherese diventa O ( V 2 E ) {displaystyle O(V^{2}E)}
, o il costo del bordo può essere spostato con un potenziale per ottenere O ( V 2 log V + V E ) {displaystyle O(V^{2}\log {V}+VE)}
tempo di esecuzione con l’algoritmo di Dijkstra e l’heap di Fibonacci.
In un grafo pesato non bipartito, il problema dell’accoppiamento del peso massimo può essere risolto in tempo O ( V 2 E ) {\displaystyle O(V^{2}E)}
utilizzando l’algoritmo blossom di Edmonds.
Abbinamenti massimiModifica
Un abbinamento massimo può essere trovato con un semplice algoritmo greedy. Una corrispondenza massima è anche una corrispondenza massima, e quindi è possibile trovare una corrispondenza massima più grande in tempo polinomiale. Tuttavia, non è noto alcun algoritmo in tempo polinomiale per trovare una corrispondenza massima minima, cioè una corrispondenza massima che contiene il minor numero possibile di bordi.
Una corrispondenza massima con k bordi è un insieme dominante con k bordi. Viceversa, se ci viene dato un insieme minimo di dominanza di bordi con k bordi, possiamo costruire una corrispondenza massima con k bordi in tempo polinomiale. Pertanto, il problema di trovare una corrispondenza massima minima è essenzialmente uguale al problema di trovare un insieme minimo di dominanti di bordo. Entrambi questi due problemi di ottimizzazione sono noti per essere NP-hard; le versioni decisionali di questi problemi sono esempi classici di problemi NP-completi. Entrambi i problemi possono essere approssimati entro il fattore 2 in tempo polinomiale: basta trovare una corrispondenza massima arbitraria M.
Problemi di conteggioModifica
Il numero di corrispondenze in un grafico è noto come indice di Hosoya del grafico. È #P-completo calcolare questa quantità, anche per i grafi bipartiti. È anche #P-completo contare le corrispondenze perfette, anche nei grafi bipartiti, perché calcolare la permanente di una matrice arbitraria 0-1 (un altro problema #P-completo) è lo stesso che calcolare il numero di corrispondenze perfette nel grafico bipartito che ha la matrice data come matrice di biadiacenza. Tuttavia, esiste uno schema di approssimazione randomizzato in tempo completamente polinomiale per contare il numero di corrispondenze bipartite. Un notevole teorema di Kasteleyn afferma che il numero di corrispondenze perfette in un grafo planare può essere calcolato esattamente in tempo polinomiale tramite l’algoritmo FKT.
Il numero di corrispondenze perfette in un grafico completo Kn (con n pari) è dato dal doppio fattoriale (n – 1)! I numeri di corrispondenze in grafi completi, senza costringere le corrispondenze ad essere perfette, sono dati dai numeri telefonici.
Trovare tutti i bordi massimamente abbinabiliModifica
Uno dei problemi di base nella teoria della corrispondenza è quello di trovare in un dato grafico tutti i bordi che possono essere estesi ad una corrispondenza massima nel grafico (tali bordi sono chiamati bordi maximally-matchable, o bordi permessi). Gli algoritmi per questo problema includono:
- Per i grafi generali, un algoritmo deterministico in tempo O ( V E ) {\displaystyle O(VE)}
e un algoritmo randomizzato in tempo O ~ ( V 2.376 ) {displaystyle {\tilde {O}}(V^{2.376})}
.
- Per i grafi bipartiti, se viene trovata una singola corrispondenza massima, un algoritmo deterministico gira in tempo O ( V + E ) {\displaystyle O(V+E)}
.
Corrispondenza bipartita onlineModifica
Il problema di sviluppare un algoritmo online per la corrispondenza è stato considerato per la prima volta da Richard M. Karp, Umesh Vazirani e Vijay Vazirani nel 1990.
Nell’impostazione online, i nodi su un lato del grafico bipartito arrivano uno alla volta e devono essere immediatamente abbinati all’altro lato del grafico o scartati. Questa è una generalizzazione naturale del problema del segretario e ha applicazioni alle aste di annunci online. Il miglior algoritmo online, per il caso di massimizzazione non pesata con un modello di arrivo casuale, raggiunge un rapporto competitivo di 0,696.