Primo Teorema di König: una guida completa al legame tra massima abbinamento e copertura minima nei grafi bipartiti

23. Aprile 2026 TeamWeb

Il primo teorema di König è uno dei pilastri della teoria dei grafi combinatori. Inquadrato nel contesto dei grafi bipartiti, stabilisce un’uguaglianza sorprendente tra due nozioni fondamentali: la dimensione della massima abbinatura (matching) e la dimensione della copertura minima di vertici (vertex cover). In poche parole, per ogni grafo bipartito G = (X ∪ Y, E) vale che la massima dimensione di un abbinamento non orientato agli archi è uguale alla minima dimensione di un insieme di vertici che copre tutti gli archi. Questo risultato non è solo di alto valore teorico: dà strumenti pratici e algoritmi efficienti per risolvere problemi di assegnazione, pianificazione e gestione delle risorse in contesti reali, dall’informatica all’economia, dalla logistica alle reti sociali. In questo articolo esploreremo il primo teorema di König in modo esaustivo, partendo dalle definizioni chiave e giungendo a dimostrazioni intuitive, versioni equivalenti, estensioni e casi concreti d’applicazione.

Contesto storico e definizioni chiave

Prima di addentrarci nel primo teorema di König, è utile fissare alcuni concetti di base sul tipo di grafo considerato: un grafo bipartito, pingato tra due insiemi disgiunti di vertici X e Y, con archi che possono collegare solo elementi di X a elementi di Y. Una situazione tipica è quella di una serie di candidati e una serie di posti disponibili: un abbinamento è una scelta di coppie (x, y) tali che ogni vertice compare in al massimo una coppia; una copertura di vertici è invece un insieme di vertici che tocca ogni arco del grafo.

Nella formulazione classica:

Massima abbinatura (nuovo simbolo nu(G)): la dimensione della più grande collezione di archi che non si incontrano tra loro su nessun vertice. In breve, quante coppie disgiunte è possibile formare?
Copertura minima di vertici (tau(G) o κ(G)): la dimensione più piccola di un insieme di vertici che tocca tutti gli archi del grafo.

Il primo teorema di König si concentra proprio su grafi bipartiti: in tali grafi, la massima abbinatura e la copertura minima hanno la stessa dimensione. In notazione, se G è bipartito, allora nu(G) = tau(G).

Questo risultato si collega a idee di dualità e ottimizzazione, fornendo una base solida per algoritmi pratici di calcolo della copertura minima a partire da un abbinamento massimo e, viceversa, per la costruzione di un abbinamento massimo a partire da una copertura minima.

Enunciato del Primo Teorema di König

Versione formale

Sia G = (X ∪ Y, E) un grafo bipartito. Allora la dimensione della massima abbinatura di G è uguale alla dimensione della copertura minima di vertici di G:

nu(G) = tau(G).

In pratica: se si trova una coppia massima di archi disgiunti, la quantità di tali archi coincide con la dimensione minima di un insieme di vertici che tocca ogni arco di G.

Interpretazione intuitiva

Immagina di dover assegnare risorse a compiti: ogni abbinatura rappresenta una selezione di coppie senza conflitti. La copertura minima di vertici, d’altra parte, rappresenta il minor numero di elementi (vertici) da rimuovere o da coinvolgere per catturare ogni relazione tra risorse e compiti. Il primo teorema di König afferma che questi due modi di misurare “quanto è grande” un sistema bipartito coincidono esattamente in termini di grandezza. Questa corrispondenza è una forma elegante di dualità: non serve cercare combinazioni più grandi o coperture più piccole separatamente—una volta che si conosce una di esse, si conosce immediatamente l’altra.

Idea di dimostrazione: intuitive e rigore

La dimostrazione del primo teorema di König può essere resa accessibile senza rinunciare al rigore. Una delle prove più comuni è costruita a partire da un abbinamento massimo M e dall’analisi di cammini alternati. Ecco una versione “costruttiva” che offre anche un procedimento pratico per ottenere una copertura minima a partire da un abbinamento massimo.

Passi chiave della dimostrazione

Partiamo da una massima abbinatura M in G = (X ∪ Y, E).
Orientiamo gli archi di E per formare un grafo orientato D: orientiamo in X → Y gli archi non presenti in M e in Y → X gli archi che fanno parte di M.
Individuiamo X_unmatched, cioè i vertici non accoppiati in M nell’insieme X.
Esploriamo con una visita in ampiezza o depth-first i vertici raggiungibili partendo da X_unmatched seguendo i cammini orientati di D. Siano R l’insieme di vertici di X ∪ Y raggiungibili.
Definiamo la copertura C come C = (X \ R) ∪ (Y ∩ R).
Dimostriamo che C è una copertura di G: ogni arco deve toccare almeno uno dei vertici in C. Questo nasce dal modo in cui sono stati orientati gli archi e dall’assunzione che M sia massimo.
Mostriamo che la dimensione di C è uguale alla dimensione di M. In particolare, ogni arco di M è coperto da un unico vertice di C, e non possono esistere vertici in M non coperti da C senza violare la massima cardinalità di M.

Questa costruzione fornisce non solo una dimostrazione di esistenza, ma anche una procedura pratica per ottenere una copertura minima a partire da un abbinamento massimo, testimoniando la dualità intrinseca del primo teorema di König.

Un esempio numerico semplice

Considera un grafo bipartito con X = {x1, x2} e Y = {y1, y2}, e archi E = { (x1, y1), (x1, y2), (x2, y2) }. Un abbinamento massimo M potrebbe essere {(x1, y1), (x2, y2)}, ha dimensione 2. Applicando la procedura sopra descritta, otteniamo una copertura minima C di dimensione 2, adatta a toccare ogni arco. Così, nu(G) = tau(G) = 2, in accordo con il primo teorema di König.

Relazioni e varianti: König e Hall

Il primo teorema di König si inserisce in una cornice più ampia di dualità tra problemi di abbinamento e problemi di copertura. Una delle pietre miliari è il teorema di Hall, noto come condizione necessaria e sufficiente per l’esistenza di una corrispondenza perfetta in grafi bipartiti: se per ogni sottoinsieme S di X, il numero di vicini di S in Y è almeno quanto la dimensione di S, allora esiste una corrispondenza che copre interamente X. Il primo teorema di König completa questa storia fornendo una misura quantitativa: la massima dimensione di una abbinatura è uguale alla minima dimensione di una copertura. Insieme, Hall e König descrivono due facce della stessa moneta: la capacità di abbinare risorse e compiti in modo ottimale e la capacità di “fotografare” le potenziali interferenze tramite coperture di vertici.

Un’altra estensione importante è il teorema di König-Egérváry, che esplicita la stessa proprietà per grafi bipartiti, spesso citato come in letteratura anglos.ass} In contesti meno netti, si osserva che, in grafi non bipartiti, la relazione tra massima abbinatura e copertura minima si allontana: esiste un gap, e in generale non vale l’uguaglianza. Questo rende l’ipotesi bipartita essenziale per l’applicazione pratica e per la dualità di cui il primo teorema di König è portatore.

Applicazioni pratiche del Primo Teorema di König

Le applicazioni del primo teorema di König sono ampie e riportano a contesti reali dove è necessario distribuire risorse o gestire vincoli. Ecco alcuni ambiti significativi:

Job matching e assegnazioni: in modelli bipartiti tra lavoratori e compiti, la conoscenza che nu(G) = tau(G) aiuta a dimensionare al meglio la copertura minima necessaria per controllare tutte le assegnazioni. Questo si traduce in algoritmi efficienti per trovare soluzioni ottimali.
Pianificazione delle risorse: nel caso di sistemi con due lati bipartiti, come fornitori e richieste, è possibile calcolare rapidamente quante risorse sono indispensabili per coprire tutte le richieste, grazie alla relazione duale tra abbinamenti e coperture.
Reti e flussi: la riduzione di problemi di flusso massimo-minimo taglio in grafi bipartiti è un classico utilizzo del primo teorema di König. Trasformando il problema in una rete di flusso, si ottiene un algoritmo efficiente per determinare sia l’abbinamento massimo sia la copertura minima.
Ottimizzazione combinatoria e programmazione lineare: grazie alla proprietà di integrità della relaxation LP per grafi bipartiti, il primo teorema di König garantisce soluzioni intere ottimali, semplificando notevolmente la risoluzione di problemi di ottimizzazione.

Estensioni e dualità: dal primal al dual

Una prospettiva particolarmente utile è quella di vedere l’abbinamento come problema di massimizzazione e la copertura come problema di minimizzazione, interpretando entrambi come istanze di programmazione lineare (LP) con dualità forte. Nel caso dei grafi bipartiti, l’LP associata al problema di abbinamento ha una soluzione ottimale integrale, il che implica che l’ottimo della versione continua coincide con l’ottimo intero. Questo è precisamente l’ingrediente chiave del primo teorema di König operativo anche dal punto di vista algoritmico.

Formalmente, la formulazione è la seguente:

Primal (maximizzare abbinamento): massimizza ∑ e∈E x_e soggetto a ∑_{e incidenti a v} x_e ≤ 1 per ogni v ∈ V, x_e ≥ 0. In un contesto integrale, si ottiene che x_e ∈ {0,1}.
Dual (minimizzare copertura): minimizza ∑_{v∈V} y_v soggetto a y_u + y_v ≥ 1 per ogni e = (u,v) ∈ E, y_v ≥ 0.

In grafi bipartiti, la dualità forte garantisce che l’ottimo primal sia equalmente l’ottimo dual e che, contrariamente a contesti generali, la soluzione sarà intera. Questo è l’aspetto che permette di convertire rapidamente una soluzione di abbinamento massimo in una copertura minima efficiente, e viceversa, con grande beneficio computazionale.

Guida pratica all’uso del König in progetti concreti

Se vuoi applicare il primo teorema di König in progetti reali, ecco una guida operativa in pochi passi:

Modella il problema come grafo bipartito: identifica i due insiemi X e Y e la relazione E tra di essi.
Trova un abbinamento massimo M. Un modo comune è utilizzare l’algoritmo di Hopcroft–Karp, che opera in tempo O(E sqrt(V)).
Costruisci l’insieme di vertici per la copertura minima seguendo la procedura basata su cammini alternati: parti X non raggiunte dallo stato iniziale e Y raggiunte, oppure l’opposto se preferisci una costruzione simmetrica.
Verifica che la dimensione di C coincide con la dimensione di M. Se siete interessati a una copertura esplicita, avete ora una copertura minima pronta all’uso.
Trasforma i risultati in implementazioni pratiche: programming di scheduling, assegnazioni di risorse, o ottimizzazione di reti logistiche.

Questo flusso di lavoro è particolarmente robusto perché non dipende dall’input casuale: è valido per ogni grafo bipartito e garantisce una soluzione ottimale in tempi polinomiali.

Esempi concreti e esercizi guidati

Per consolidare il concetto, considera un piccolo caso pratico: una struttura di studenti e progetti, dove ogni studente si può assegnare a un subset di progetti. Se si costruisce un grafo bipartito tra studenti X e progetti Y con un arco tra uno studente e un progetto se lo studente è idoneo a quel progetto, allora la massima abbinatura rappresenta la massima serie di assegnazioni possibili senza conflitti. Dall’altro lato, una copertura minima di vertici indica il minor numero di studenti e di progetti da considerare per coprire tutte le interazioni, ovvero per controllare che ogni relazione studente-progetto venga considerata. Il primo teorema di König assicura che queste due quantità coincidono, facilitando la scelta tra due prospettive di soluzione a seconda del contesto e degli obiettivi.

Proposta di esercizio: data una piccola rete bipartita con X = {a, b, c}, Y = {1, 2, 3}, e un insieme di archi che collega alcune combinazioni, determina una abbinatura massima e costruisci la copertura minima utilizzando la procedura di cammini alternati. Verifica che le dimensioni coincidano e discuti l’interpretazione dell’esito nel contesto del problema reale (ad esempio assegnazioni di progetti).

Domande frequenti sul Primo Teorema di König

Qual è l’esatto enunciato del primo teorema di König?
Risposta sintetica: in grafi bipartiti, la dimensione della massima abbinatura è uguale alla dimensione della copertura minima di vertici.
In quali casi si applica il teorema?
Risposta sintetica: sempre per grafi bipartiti; non è valido in grafi non bipartiti in generale.
Come si costruisce una copertura minima a partire da un abbinamento massimo?
Risposta sintetica: si usa la costruzione a cammini alternati partendo dai vertici non accoppiati in una delle parti, definendo l’insieme C come (X \ R) ∪ (Y ∩ R).
Esistono estensioni utili?
Risposta sintetica: sì, il teorema di König-Egérváry e l’analisi LP duale offrono ulteriori prospettive e generalizzazioni in contesti bipartiti e oltre.

Conclusione

Il primo teorema di König è molto più di una semplice identità numerica tra due grandezze: rappresenta una chiave concettuale per la dualità tra problemi di abbinamento e problemi di copertura nei grafi bipartiti. Fornisce strumenti concreti per trasformare problemi di ottimizzazione in procedure esecutive pratiche e permette di capire come le soluzioni ottimali emergono dall’interazione tra due strutture, l’abbinamento e la copertura, che a prima vista sembrano distinte ma in realtà sono due facce della stessa soluzione ottimale. Se lavori in campi che richiedono assegnazioni, pianificazioni o gestione efficiente delle risorse all’interno di contesti bipartiti, conoscere il Primo Teorema di König ti offre una prospettiva solida, strumenti efficaci e, soprattutto, una base teorica affidabile per affrontare problemi complessi in modo sistematico e ottimale.