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

Per prima cosa scriviamo la condizione:

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

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

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