Teorema di Tutte

Da Wikipedia, l'enciclopedia libera.

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[modifica | modifica wikitesto]

Un grafo, \scriptstyle G = (V,E), ha un accoppiamento perfetto se e solo se per ogni sottoinsieme \scriptstyle U di \scriptstyle V, il sottografo indotto da \scriptstyle V - U ha al massimo \scriptstyle|U| componenti connesse con un numero dispari di vertici.[1]

Dimostrazione[modifica | modifica wikitesto]

Per prima cosa scriviamo la condizione:

(*) \qquad \forall U \subseteq V, \quad o(G-U)\le|U|

Necessità di (∗): Si consideri un grafo \scriptstyle G, con un accoppiamento perfetto. Sia \scriptstyle U un sottoinsieme arbitrario di \scriptstyle V. Si elimini \scriptstyle U. Sia \scriptstyle C una componente dispari arbitraria in \scriptstyle G - U. Poiché \scriptstyle G aveva un accoppiamento perfetto, almeno un vertice in \scriptstyle C deve essere accoppiato a un vertice in \scriptstyle U. Quindi ciascuna componente dispari ha almeno un vertice accoppiato con un vertice in \scriptstyle U. Poiché ciascun vertice in \scriptstyle U 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), \scriptstyle o(G - U) \le |U|.

Sufficienza di (∗): Sia \scriptstyle G un grafo arbitrario che soddisfa (∗). Si consideri l'espansione di \scriptstyle G a \scriptstyle G *\ , un grafo massimamente imperfetto, nel senso che \scriptstyle G è un sottografo ricoprente di \scriptstyle G *\ , ma aggiungere uno spigolo a \scriptstyle G *\ darà come risultato un accoppiamento perfetto. Osserviamo che \scriptstyle G *\ soddisfa anche la condizione (∗) poiché \scriptstyle G *\ è \scriptstyle G con spigoli aggiuntivi. Sia \scriptstyle U l'insieme dei vertici di grado \scriptstyle |V| - 1. Eliminando \scriptstyle U, 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 \scriptstyle C a un vertice in \scriptstyle U e i vertici rimanenti in \scriptstyle C tra loro stessi (dal momento che rimane un numero pari di essi questo è possibile). I vertici rimanenti in \scriptstyle U possono essere accoppiati in modo simile, in quanto \scriptstyle U è completo.

Questa dimostrazione non è completa. Eliminare \scriptstyle U 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[modifica | modifica wikitesto]

  1. ^ Lovász & Plummer (1986), p. 84

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica