Teorema di Konig-Egervary
Se la condizione di Hall non è soddisfatta, non posso trovare un insieme di rappresentanti distinti, o di uni indipendenti per ogni riga. Qual è il numero massimo di uni che posso ottenere? A questo risponde il teorema di Konig-Egervary.
E’ un risultato di tipo minmax, dove il massimo di una quantità è uguale al minimo di un’altra. Abbiamo visto due formulazioni per il teorema di Hall, per famiglie di insieme e grafi bipartiti. Dunque anche il teorema di Konig-Egervay avrà due forme analoghe.
Per matrici -
Teorema (Konig-Egervary 1931) In una matrice - rettangolare, il minimo numero di linee che nell’insieme contengono tutti gli è uguale al massimo numero di indipendenti.
Dim Se vi è un numero di indipendenti, poichè due di questi stanno su linee diverse, sono necessarie almeno linee per comprenmdere tutti gli , quindi . Per dimostrare l’altro verso facciamo vedere che possiamo trovare almeno indipendenti. Supponiamo che la nostra matrice sia , e le linee che contengono tutti gli uni siano dove sono le righe ed le colonne. Possiamo permutare righe e colonne in modo tale che siano le prime righe e le prime colonne. Posso dividere in blocchi la matrice, le matrici “diagonali” sono piene di zero, le antidiagonali conengono uni e soddisfano la condizione di Hall. Essendo in blocchi diversi le matrici non contengono elementi in comune, ho quindi uni indipendenti.
Per grafi bipartiti
Teorema In un grafo bipartito , , il massimo numero di archi in un mathing in è uguale al minimo numero di vertici in un edge-cover di .
Dim Segue dal teorema in forma matriciale, consideriamo la matrice di adiacenza di , sulle righe i vertici di e sulle colonne quelli di . Ogni uno rappresenta un arco, quindi il minimo numero di linee che contiene tutti gli uni è un edge-cover che contiene meno vertici possibili. Per il teorema precedente sappiamo che questo è uguale al massimo numero di uni indipendenti, e questo è un matching massimo del grafo in (massimo numero di righe con uni indipendenti).