Matching su grafi e alcune varianti del problema del matrimonio stabile

uomini e donne per far riferimento a matching stabili su grafi bipartiti.
In generale gli elementi da abbinare possono avere delle preferenze con-
trastanti, dunque e` importante ricercare un abbinamento che pur tenendo in
considerazione queste preferenze costituisca comunque un sistema di coppie
stabile.
Un esempio di problema di ricerca di matching stabile puo` essere l’asse-
gnazione di medici tirocinanti a strutture ospedaliere che offrono corsi di
specializzazione ad un numero limitato di candidati, un problema la cui
risoluzione, in paesi come Stati Uniti, Scozia, Canada e Giappone, si av-
vale del supporto di servizi centralizzati a livello nazionale (NRMP, CaRMS,
SPA) che hanno l’obiettivo di generare abbinamenti stabili considerando le
esigenze degli ospedali e dei medici. Tali sistemi di matching utilizzano una
procedura basata sull’algoritmo di Gale e Shapley che analizzeremo in questa
trattazione.
Il primo capitolo e` suddiviso in due parti, nella prima, dopo una breve
panoramica delle proprieta` dei grafi che utilizzeremo nel seguito, illustrere-
mo dei risultati relativi alla teoria del matching su grafi bipartiti come il
Teorema di Hall ed il Teorema del “matrimonio” di Frobenius che indivi-
duano le proprieta` caratteristiche dei grafi bipartiti fattorizzabili, cioe` per
i quali e` possibile costruire un matching rispetto al quale tutti i nodi del
grafo sono abbinati. Nella seconda parte ci occuperemo invece dei problemi
di ottimizzazione che comportano la divisione di un insieme di elementi in
coppie distinte rispettando determinati vincoli e classificati percio` come prob-
lemi di matching. Suddivideremo questi problemi in tre categorie: matching
massimo, matching pesato e matching stabile, fornendo degli esempi per
ciascuno e sottolineando la differenza tra il caso bipartito e quello non bi-
partito. Successivamente prenderemo in esame il problema del matching
massimo, descrivendo una procedura algoritmica risolutiva, ed il problema
del matching pesato, presentando la relativa formulazione come problema di
2
programmazione lineare intera.
Nel secondo capitolo affronteremo dettagliatamente il problema del matri-
monio stabile. Dopo aver formalizzato il concetto di stabilita` e di preferenza
enunceremo e dimostreremo il Teorema del “matrimonio stabile”, degli stessi
Gale e Shapley, che prova l’esistenza di matching stabili per qualsiasi istanza
del problema dando vita ad un algoritmo in grado di costruire in tempo
polinomiale un particolare matching stabile. Illustreremo poi due algoritmi
che migliorano il primo pur mantenendo la stessa complessita` asintotica nel
caso peggiore. Infine daremo una dimostrazione non costruttiva dell’esistenza
di matching stabili.
Nel terzo capitolo affronteremo le varianti del problema del matrimonio
stabile ottenute rilassando le limitazioni poste nella versione classica. Analiz-
zeremo lo stable marriage problem con insiemi di cardinalita` diversa e succes-
sivamente il problema in cui le liste di preferenza possono essere incomplete.
Per entrambi forniremo algoritmi che in tempo polinomiale costruiscono un
matching stabile per qualsiasi istanza. Considereremo poi liste di preferenza
non strettamente ordinate e descriveremo le tre possibili nozioni di stabilita`
che emergono in tal caso (debole, super e forte) fornendo poi per ognuna un
algoritmo che risolve il problema in tempo polinomiale. Lo stesso faremo
per l’ultima delle varianti affrontate, quella in cui le liste di preferenza pos-
sono essere incomplete e non strettamente ordinate, con la differenza che, per
quanto riguarda la stabilita` debole, proveremo la NP-completezza del pro-
blema di ricerca di matching stabili di cardinalita` massima e descriveremo
un algoritmo approssimante che costruisce una soluzione con scostamento
garantito dall’ottimo pari a 2.
In appendice sono riportati i programmi che codificano in linguaggio C
gli algoritmi analizzati.
3
Capitolo 1
Teoria del matching e
applicazioni
1.1 Matching su grafi
Ricordiamo che un grafo G e` una coppia di insiemi finiti (V,E) dove V e`
l’insieme dei nodi o vertici di G mentre E ⊆ V × V e` l’insieme degli archi o
spigoli di G.
|V | definisce l’ordine del grafo mentre |E| la dimensione del grafo.
Consideriamo un grafo G = (V,E), se e = (u, v) ∈ E allora u e v si dicono
estremi di e, u e v sono adiacenti e l’arco e e` incidente in u e v.
Se due archi distinti hanno un estremo in comune allora sono incidenti,
altrimenti sono indipendenti.
Sia S ⊆ V , definiamo N(S) := {v ∈ V |(u, v) ∈ E per qualche u ∈ S}.
Se S = {v} allora N(v) e` l’insieme dei nodi adiacenti a v e |N(v)| definisce
il grado di v.
Una sequenza di nodi p = [v1, . . . vk] di un grafo G, si dice cammino; E(p)
e` l’insieme degli archi di p, |E(p)| definisce la lunghezza del cammino. I nodi
v1 e vk costituiscono rispettivamente il nodo di partenza e di arrivo di p, se
4
coincidono allora p e` un ciclo. Se i nodi di p sono a due a due distinti allora
p si dice semplice.
Il vertice u e` raggiungibile da v se esiste un cammino da u in v. Se per
ogni coppia di nodi di G esiste un cammino che li congiunge allora G si dice
connesso.
Il grafo G′ = (V ′, E ′) e` un sottografo di G (G′ ⊂ G) se V ′ ⊂ V e E ′ ⊂ E.
Se E ′ ⊂ E allora G′ = (V,E ′) e` un sottografo ricoprente o sottografo di
supporto di G.
Se l’insieme dei vertici di un grafo G puo` essere partizionato in due insiemi
disgiunti, V = A∪B, in modo tale che ogni arco di G sia del tipo (u, v) con
u ∈ A e v ∈ B o u ∈ B e v ∈ A, allora G e` un grafo bipartito con partizione
(A,B).
Vediamo una caratterizzazione dei grafi bipartiti:
Lemma 1.1.1. Un grafo G e` bipartito se e soltanto se non ammette cicli di
lunghezza dispari.
Dimostrazione. (⇒) Sia (A,B) la partizione di G. Supponiamo che in
G esista un ciclo dispari c = [u1, . . . , u2k] (u1 = u2k) e u1 ∈ A. Essendo G
bipartito, se u1 ∈ A ⇒ u2 ∈ B ⇒ u3 ∈ A ⇒ u4 ∈ B ⇒ . . ., ossia tutti i nodi
in c con indice dispari appartengono ad A mentre quelli con indice pari a B,
ma questo implica u2k ∈ B che e` assurdo. Possiamo concludere che G non
puo` ammetere cicli dispari.
(⇐) Per ogni componente connessa Ci di G fissiamo un vertice u di Ci
e consideriamo tutti i possibili cammini semplici in Ci che partono da u.
Definiamo Pi l’insieme dei nodi che hanno indice pari in qualche cammino da
u, cioe` l’insieme dei nodi v per i quali esiste un cammino c = [u1, . . . , un] tale
che u1 = u e u2k = v per qualche 1 ≤ k ≤
⌊n
2
⌋
. Definiamo invece Di l’insieme
dei nodi v per i quali esiste c = [u1, . . . , un] con u1 = u e u2k+1 = v per qualche
1 ≤ k ≤
⌊n−1
2
⌋
. Vogliamo dimostrare che (Pi, Di) e` una partizione di Ci.
5
(a) (b)
Figura 1.1: (a) Grafo completo (b) Grafo bipartito completo
Sicuramente Pi ∩ Di = ∅ infatti se v ∈ Pi ∩ Di allora v ha indice dis-
pari in un cammino da u e indice pari in un altro e quindi il ciclo ottenuto
percorrendo il primo cammino fino a v e tornando a u sull’altro cammino e`
dispari.
Rimane da dimostrare che non esistono archi che congiungono due vertici
dello stesso insieme. Supponiamo esista un arco e = (p, p′) che connette due
nodi di Pi. Poiche´ p, p′ ∈ Pi allora esiste un cammino c = [u1, . . . , un] tale che
u1 = u e u2k = p e un cammino c′ = [u′1, . . . , u′m] tale che u′1 = u e u′2h = p′.
Consideriamo il ciclo [u1, . . . , u2k, u′2h, . . . , u′1], ottenuto percorrendo: c fino
al nodo p poi l’arco e e infine gli archi del cammino c′ a ritroso a partire da
p′. E` un ciclo di G di lunghezza (2k− 1) + 1 + (2h− 1) = 2(k + h)− 1. Ma,
per ipotesi, il grafo non ammette cicli dispari percio` un tale arco e non puo`
esistere. Per lo stesso motivo non esistono archi che connettono due nodi di
Di e questo ci permette di concludere che (Pi, Di) e` una partizione di Ci. La
partizione (P,D) := (∪iPi,∪iDi) e` una partizione di G. 
G e` completo se ogni nodo e` adiacente ad ogni altro nodo del grafo.
Un grafo bipartito, con partizione (A,B), e` completo se tutti i vertici di A
sono adiacenti a tutti i vertici di B. Indicheremo con Kn un grafo completo
di ordine n mentre con Km,n un grafo bipartito completo di ordine m + n
(fig. 1.1). G e` regolare se tutti i vertici hanno lo stesso grado. Un sottografo
6
(a) (b) (c) (d)
Figura 1.2: (a)Matching massimale (b)Matching massimo (c)Trasversale
minimale (d)Trasversale minimo
ricoprente di G k-regolare si dice k-factor di G. Consideriamo ora un grafo
G = (V,E).
Definizione 1.1.1 (Matching). Un matching del grafo G e` un insieme di
archi a due a due indipendenti di G.
La cardinalita` massima di un matching di G definisce il matching num-
ber (ν(G)). Se M e` un matching di G tale che |M | = ν(G) allora e` un
matching massimo. Osserviamo che c’e` distinzione tra matching massimo
e matching massimale: un matching e` massimale se non esistono matching
del grafo che lo contengano, cioe` qualsiasi altro arco del grafo e` incidente in
almeno uno degli archi di un tale matching. Un matching massimale non e`
necessariamente massimo (vedi figure 1.1 (a) e (b)).
Definizione 1.1.2 (Copertura di nodi o trasversale). T ⊆ V e` una
copertura di nodi di G (o trasversale di G) se ogni arco in E e` incidente in
almeno un nodo v ∈ T .
La cardinalita` minima di una copertura di nodi di G definisce il numero di
copertura di nodi di G (τ(G)). Se T e` un trasversale tale che |T | = τ(G) allora
si dice minimo. Un trasversale T e` invece minimale se non contiene alcun
trasversale. Si deduce che un trasversale minimale non e` necessariamente
minimo (vedi figure 1.1 (c) e (d)).
Siano M e T rispettivamente un matching e un trasversale di un grafo G.
Osserviamo che ogni arco di M deve essere coperto da almeno un nodo di T
7
Figura 1.3: τ(G) > ν(G)
e ogni nodo di T puo` coprire al piu` un arco di M (se ne coprisse piu` di uno
allora sarebbero archi incidenti). Deduciamo allora che |T | ≥ |M |, quindi
vale la relazione
τ(G) ≥ ν(G). (1.1)
Dato un matching M∗, costruiamo un insieme di nodi T ∗ tale che ogni arco
del matching abbia esattamente un estremo in T ∗ (quindi |T ∗| = |M∗|). In
generale un tale insieme T ∗ non e` necessariamente una copertura, visto che
potrebbero esistere archi del grafo non coperti da alcun nodo di T ∗ (vedi
fig. 1.3), ma se lo fosse, non solo T ∗ sarebbe una copertura minima, ma M ∗
sarebbe un matching massimo, dunque ν(G) = τ(G).
Lemma 1.1.2. Siano M e T rispettivamente un matching e un trasversale
di un grafo G. Se |M | = |T | allora M e` un matching massimo e T e` un
trasversale minimo e in particolare ν(G) = τ(G).
Dimostrazione. Se M∗ un matching massimo e T ∗ un trasversale minimo
di G (ν(G) = |M∗| e τ(G) = |T ∗|) allora, dalla relazione 1.1 segue
|M | ≤ |M∗| ≤ |T ∗| ≤ |T |
e, essendo |T | = |M |, si ha |M | = |M∗| = ν(G) e |T | = |T ∗| = τ(G). 
Dato un matching M , diremo che M e` un matching di U ⊆ V se ogni
vertice in U e` estremo di un arco di M . In tal caso i vertici in U si dicono
abbinati in M mentre tutti gli altri vertici del grafo sono esposti.
8
Diremo che un matching e` perfetto se e` un matching di V , in altre parole
se e` un matching che abbina tutti i nodi del grafo. Si deduce che un sottografo
G′ = (V,E ′) e` un 1-factor di G se e solo se E ′ e` un matching perfetto.
Un grafo che ammette un matching perfetto si dice fattorizzabile.
Osserviamo inoltre che affinche´ un matching perfetto esista e` necessario
supporre che |V | sia pari.
1.1.1 Matching su grafi bipartiti e “Teorema del Ma-
trimonio”
Consideriamo un grafo bipartito G = ((A,B), E). Diremo che un matching
M su G e` completo se e` un matching di A o di B. In particolare se M e` un
matching di A allora lo definiremo matching completo da A a B.
Affinche´ G ammetta un matching completo da A a B deve essere neces-
sariamente |A| ≤ |B|. Se |A| = |B| allora un matching completo da A a B e`
ovviamente un matching perfetto.
Se M e` completo o perfetto allora vale:
|S| ≤ |N(S)| ∀S ⊆ A (marriage condition) (1.2)
infatti se S e` un sottoinsieme di A allora tutti i suoi elementi devono essere
abbinati in M ad altrettanti elementi di N(S) e cio` e` possibile soltanto se
vale (1.2), vedi figura 1.4.
Frobenius (1917) e Hall (1935) mostrarono che la marriage condition
e |A| = |B| sono condizioni non solo necessarie, ma anche sufficienti per
l’esistenza di un matching completo o perfetto in un grafo bipartito.
Teorema 1.1.1 (Teorema di Hall). Un grafo bipartito G = ((A,B), E)
ammette un matching completo da A a B ⇔ vale la marriage condition.
9
(a) (b)
Figura 1.4: Grafi bipartiti che non soddisfano la marriage condition: (a) non
ammette matching completo da A a B (b) non ammette matching perfetto
Dimostrazione. Dimostriamo che la condizione e` sufficiente, ossia, sup-
ponendo che per G valga la marriage condition, cerchiamo un matching di A
sul grafo G.
Procediamo per induzione su |A|: se |A| = 1 l’asserto e` ovvio, consideri-
amo allora |A| ≥ 2 e supponiamo vero l’asserto per ogni grafo bipartito con
partizione (A′, B′) tale che |A′| < |A|.
Analizziamo separatamente i due casi possibili.
1. ∀S ⊂ A, S 6= ∅, |S| < |N(S)|.
Consideriamo due nodi a ∈ A e b ∈ B adiacenti di G. Definiamo G′ il
sottografo indotto da V \{a, b} e A′ := A\{a}. Notiamo che ogni S ⊆ A′
ha in G′ al piu` un nodo adiacente in meno, b, rispetto a quelli che ha in
G, quindi |NG′(S)| ≥ |NG(S)| − 1. Dalle assunzioni fatte |NG(S)| − 1 ≥ |S|
quindi |S| ≤ |NG′(S)|. Vale cioe` la (1.2) per il grafo G′. Dall’ipotesi induttiva
segue l’esistenza di un matching M ′ di A′ in G′ e aggiungendo l’arco (a, b) al
matching M ′ si ottiene un matching completo da A a B in G.
2. ∃S ⊂ A, S 6= ∅, tale che |S| = |N(S)|.
Sia A′ ⊂ A tale che |A′| = |N(A′)|. Definiamo G1 il sottografo di G indotto da
10
A′∪N(A′) e G2 il sottografo di G indotto da V \(A′∪N(A′)). Mostriamo che
G1 e G2 soddisfano l’ipotesi induttiva. Se S ⊆ A′ allora NG(S) ⊆ NG(A′)
e quindi |NG1(S)| = |NG(S)| ≥ |S|. Se S ⊆ A\A′ allora NG(S ∪ A′) =
NG2(S) ∪ NG(A′). Essendo poi S ∪ A′ = ∅ e NG2(S) ∩ NG(A′) = ∅ si ha
|NG2(S)| = |NG(A∪A′)|−|NG(A′)| ≥ |S∪A′|−|NG(A′)| = |S∪A′|−|A′| = |S|.
Per l’ipotesi induttiva esiste un matching M1 di A′ in G1 e un matching M2
di A\A′ in G2. M := M1 ∪M2 e` un matching completo da A a B sul grafo
G. 
Corollario 1.1.1 (“Teorema del matrimonio”, Frobenius).
Un grafo bipartito G = ((A,B), E) ammette matching perfetto (o equivalen-
temente ammette 1-factor) se e soltanto se:
(i) |A| = |B|;
(ii) |S| ≤ |N(S)| ∀S ⊆ A .
Questo risultato e` noto come teorema del matrimonio perche´ fornisce
una risposta al seguente quesito: considerato un insieme finito di n ragaz-
ze e supponendo che queste ragazze conoscano collettivamente n ragazzi, in
quali condizioni e` possibile combinare dei matrimoni tra ciascuna delle n ra-
gazze e un ragazzo che conosce? La condizione necessaria e sufficiente in
questione e` che, comunque preso un gruppo di k ragazze, queste conoscano
collettivamente almeno k ragazzi.
Tornando ai matching su grafi bipartiti vediamo una diretta conseguenza
del teorema 1.1.1.
Corollario 1.1.2. Se G e` un grafo bipartito regolare allora G ammette
matching perfetto.
Dimostrazione. Sia (A,B) una partizione di G e k il grado di ogni vertice.
Essendo G k-regolare allora |A| = |B|. Sia S ⊆ A e E1, E2 gli insiemi degli
11
archi incidenti in vertici di S e N(S) rispettivamente. Per definizione di
N(S), E1 ⊆ E2 (visto che i vertici di N(S) possono essere adiacenti a nodi
non necessariamente di S) quindi k|S| = |E1| ≤ |E2| = k|N(S)|, ossia vale la
(1.2). Dal teorema 1.1.1 segue l’esistenza di un matching perfetto in G. 
Fin ora abbiamo affrontato il problema dell’esistenza o meno di matching
perfetti o completi su grafi bipartiti, vediamo ora cosa possiamo dire riguar-
do la cardinalita` di matching su grafi bipartiti che non soddisfano la (1.2),
per i quali quindi ν(G) < |A|. Osserviamo che se il grafo G non soddisfa la
marriage condition allora esiste un insieme S ⊂ A (che chiameremo insuf-
ficiente, dall’inglese deficient) tale che |S| > |N(S)|. Definiamo deficiency
di S la quantita` δ(S) := |S| − |N(S)|. La deficiency massima tra tutti i
sottoinsiemi di A definisce la deficiency di G (δ(G)). Ko¨nig e Ore nel 1955
dimostrarono che |A| − δ(G) e` la cardinalita` massima possibile dei matching
su G.
Teorema 1.1.2 (Ko¨nig-Ore, 1955). Se G e` un grafo bipartito con par-
tizione (A,B) allora ν(G) = |A| − δ(G).
Dimostrazione. Se G soddisfa la (1.2) allora δ(G) = 0 e ν(G) = |A| per
il teorema di Hall, in caso contrario aggiungiamo δ(G) nuovi vertici in B e
connettiamo ciascuno di essi a tutti i nodi di A. Dal teorema del matrimonio,
il grafo cos`ı ottenuto contiene un matching di A e al massimo |A|−δ(G) archi
di tale matching sono archi di G. 
Sia G il grafo di figura 1.5, si ha δ(S1) = 1, δ(S2) = 2 e δ(S3) = 1, da cui
deduciamo che δ(G) = 2 e che la cardinalita` di un matching massimo di G
e` |A| − 2 = 3. Tutti gli insiemi X che hanno deficiency massima si dicono
tight o maximally deficient (S2 e` un tight). Una proprieta` di questi insiemi
e` la seguente.
Proposizione 1.1.1. Se X e Y sono due tight per il grafo G allora lo sono
anche X ∩ Y e X ∪ Y .
12
Figura 1.5: Insiemi insufficienti (S1, S2, S3) di un grafo bipartito che non
soddisfa la marriage condition
Dimostrazione. Valgono le seguenti: |X ∪ Y | + |X ∩ Y | = |X| + |Y |,
N(X ∪ Y ) = N(X) ∪N(Y ) e N(X ∩ Y ) ⊆ N(X) ∩N(Y ).
Quindi |N(X ∪ Y )|+ |X ∩ Y | ≤ |N(X)|+ |N(Y )| e δ(X ∪ Y ) + δ(X ∩ Y ) ≥
δ(X) + δ(Y ).
Allora δ(X ∪ Y )+δ(X ∩ Y ) ≥ 2δ(G). D’altra parte δ(X ∪ Y ) + δ(X ∩ Y ) ≤
2δ(G), dato che δ(G) e` la deficiency massima. Dunque δ(X∪Y ) = δ(X∩Y ) =
δ(G). 
Un tight minimale, cioe` non contenente alcun tight, si dice critico. Dalla
proposizione 1.1.1 segue che un insieme critico e` unico ed e` l’intersezione di
tutti i tight del grafo. Nel grafo di figura 1.5 S2 e` l’insieme critico.
1.1.2 Alcune conseguenze dei teoremi per matching
bipartiti
La formulazione originale del teorema di Hall riguarda sistemi di rappresen-
tanti distinti (SDR) o trasversali di una famiglia di sottoinsiemi di un insieme
finito. Dato un insieme finito S, consideriamo una famiglia di m sottoinsiemi
13
di S (non necessariamente distinti), S = {S1, . . . , Sm}. Un sistema di rap-
presentanti distinti per S e` un insieme {x1, . . . , xm} di elementi distinti tali
che xi ∈ Si.
Esempio 1.1.1. Sia S = {1, 2, 3, 4, 5, 6} e S1 = S2 = {1, 2}, S3 = S4 =
{2, 3}, S5 = {1, 4, 5, 6}. In questo caso non e` possibile trovare un sistema
di rappresentanti distinti per la famiglia S ′ = {S1, . . . , S5}. Considerando
invece la famiglia S = {S1, S2, S3, S5}, un SDR di S e` {1, 2, 3, 4}.
E` naturale chiedersi quale condizione debba essere soddisfatta affinche´
una famiglia di sottoinsiemi di un insieme finito ammetta un trasversale.
Teorema 1.1.3 (versione SDR del teorema di Hall).
Sia S un insieme non vuoto e finito, S = {S1, . . . , Sm} una famiglia di
sottoinsiemi di S. Allora S ammette un sistema di rappresentanti distinti se
e soltanto se ogni unione di k, 1 ≤ k ≤ m, sottoinsiemi Si contiene almeno
k elementi, cioe` se
|
k⋃
j=1
Sij | ≥ k ∀{i1, . . . , ik} ⊂ {1, . . . , m}.
Se consideriamo il grafo bipartito G con partizione (S, S) (esempio 1.1.1)
e tale che (Si, j) ∈ E ⇔ j ∈ Si, esiste una corrispondenza biunivoca tra i
matching completi di G e gli insiemi di rappresentanti distinti di S. E` evi-
dente dalla figura 1.6 che il grafo G′ associato a S ′ non ha matching completi
(l’insieme I = {S1, S2, S3, S4} ⊂ S ′ e` tale che |N(I)| = |{1, 2, 3}| < |I|).
Il grafo G associato a S invece ha, ad esempio, il matching completo M =
{(S1, 1), (S2, 2), (S3, 3), (S4, 4)} cui corrisponde il sistema di rappresentanti
distinti {1, 2, 3, 4}.
Osserviamo che il sistema di rappresentanti distinti di figura 1.6 (b) e` proprio
un trasversale di G′ avente cardinalita` pari a quella del matching completo
M . Dal lemma 1.1.2 segue che in tal caso vale l’identita`
ν(G) = τ(G) (1.3)
14
(a) (b)
Figura 1.6: (a) Grafo G′ associato alla famiglia S ′ = {S1, S2, S3, S4, S5}
di sottoinsiemi di S = {1, 2, 3, 4, 5, 6} (b) Grafo G associato alla famiglia
S = {S1, S2, S3, S5} di S
In quale caso possiamo affermare con certezza che ν(G) = τ(G)? La
risposta ci viene dal seguente teorema.
Teorema 1.1.4 (“Teorema minimax”, Ko¨nig-Egerva´ry 1931).
Se G e` un grafo bipartito allora la cardinalita` massima di un matching di G
e` pari alla cardinalita` minima di un trasversale di G. (ν(G) = τ(G)).
La dimostrazione di questo Teorema, che omettiamo per brevita`, e` ripor-
tata in [12].
Nel 1936 Ko¨nig mostro` che il teorema del matrimonio di Frobenius ed il
teorema dei rappresentanti distinti di Hall sono conseguenza diretta del teo-
rema minimax e successivamente e` stato provato che questi risultati assieme
al teorema di Dilworth sugli insiemi parzialmente ordinati (1950) ed al teore-
ma del flusso massimo taglio minimo di Ford e Fulkerson (1956) sono tutti
equivalenti. Procediamo illustrando questi risultati
Il teorema di Hall si deduce considerando il fatto che, in base al teore-
ma minimax, un grafo bipartito G di partizione (A,B) ammette matching
completo da A a B se e soltanto se τ(G) = |A|. Ma questo e` possibile se e
15