Nella disciplina matematica della teoria dei grafi il teorema di Tutte, che prende nome da William Thomas Tutte, è una caratterizzazione dei grafi con accoppiamenti perfetti. È una generalizzazione del teorema dei matrimoni ed è un caso particolare della formula di Tutte-Berge.
Teorema di Tutte
Un grafo,
, ha un accoppiamento perfetto se e solo se per ogni sottoinsieme
di
, il sottografo indotto da
ha al massimo
componenti connesse con un numero dispari di vertici.[1]
Dimostrazione
Per prima cosa scriviamo la condizione:
![{\displaystyle (*)\qquad \forall U\subseteq V,\quad o(G-U)\leq |U|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ed1ef44444c7917da08f330689bf69acad742e7)
Necessità di (∗): Si consideri un grafo
, con un accoppiamento perfetto. Sia
un sottoinsieme arbitrario di
. Si elimini
. Sia
una componente dispari arbitraria in
. Poiché
aveva un accoppiamento perfetto, almeno un vertice in
deve essere accoppiato a un vertice in
. Quindi ciascuna componente dispari ha almeno un vertice accoppiato con un vertice in
. Poiché ciascun vertice in
può essere in questa relazione con al massimo una componente connessa (in quanto essa viene accoppiata al massimo una sola volta in un accoppiamento perfetto),
.
Sufficienza di (∗): Sia
un grafo arbitrario che soddisfa (∗). Si consideri l'espansione di
a
, un grafo massimamente imperfetto, nel senso che
è un sottografo ricoprente di
, ma aggiungere uno spigolo a
darà come risultato un accoppiamento perfetto. Osserviamo che
soddisfa anche la condizione (∗) poiché
è
con spigoli aggiuntivi. Sia
l'insieme dei vertici di grado
. Eliminando
, otteniamo un'unione disgiunta di grafi completi (ciascuna componente è un grafo completo). Si può ora definire un accoppiamento perfetto accoppiando indipendentemente ogni componente pari, e accoppiando un vertice di una componente dispari
a un vertice in
e i vertici rimanenti in
tra loro stessi (dal momento che rimane un numero pari di essi questo è possibile). I vertici rimanenti in
possono essere accoppiati in modo simile, in quanto
è completo.
Questa dimostrazione non è completa. Eliminare
può creare un'unione disgiunta di grafi completi, ma il caso in cui ciò non accade è la parte più interessante e difficile della dimostrazione.
Note
Bibliografia
- J. A. Bondy e U. S. R. Murty, Graph theory with applications, New York, American Elsevier Pub. Co., 1976, ISBN 0-444-19451-7.
- László Lovász e M. D. Plummer, Matching theory, Amsterdam, North-Holland, 1986, ISBN 0-444-87916-1.
Voci correlate