Don't take life too seriously: it's just a temporary situation

Tutte (congettura di)

Congetture  Teoria dei grafi 

Nel 1971 William Thomas Tutte (Newmarket, UK, 14/5/1917 – Kitchener, Canada, 2/5/2002) avanzò la congettura che ogni grafo trivalente (ossia tale che ogni nodo sia l’estremo di esattamente 3 archi), 3-connesso (ossia che non si divida in parti separate rimuovendo due nodi qualsiasi) e bipartito (ossia tale che i nodi siano suddivisi in due insiemi e ciascuno sia connesso solo ai nodi dell’altro insieme) abbia un circuito hamiltoniano, ossia un percorso chiuso che passa esattamente una volta da ogni nodo.

 

Nel 1946 Tutte aveva trovato un controesempio alla congettura di Tait e la sua congettura è un tentativo di riabilitarla, sostituendo la condizione che il grafo sia planare (ossia disegnabile sul piano senza incroci), con quella che sia bipartito.

 

Nel 1976 J.D. Horton trovò un controesempio alla congettura, il grafo con 96 nodi mostrato nella figura seguente.

 

Grafo di Horton

 

 

Altri trovarono poi controesempi con meno nodi:

  • Horton stesso trovò un grafo con 92 nodi nel 1982;

  • P.J. Owens trovò un grafo con 78 nodi nel 1983;

  • M.N. Ellingham and J.D. Horton trovarono un grafo con 78 nodi nel 1981 e uno con 54 nel 1983;

  • John P. Georges trovò un grafo con 50 nodi nel 1989.

 

La figura seguente mostra il grafo di Georges, a tutt’oggi il minimo controesempio noto.

 

Grafo di Georges

 

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.