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

Barnette (congettura di)

Congetture  Teoria dei grafi 

La congettura avanzata da David W. Barnette nel 1969 afferma che ogni grafo planare (ossia disegnabile sul piano senza incroci), 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.

 

In un certo senso la congettura è la combinazione delle congetture di Tait e di Tutte, per trovare una condizione sufficiente per l’esistenza di un grafo hamiltoniano, dopo che entrambe sono state dimostrate false. Le due congetture, infatti, asseriscono l’esistenza di un grafo hamiltoniano, ma con una condizione in meno: la congettura di Tait non richiede che il grafo sia bipartito, quella di Tutte che sia planare.

 

Un grafo planare trivalente connesso corrisponde agli spigoli di un poliedro convesso (v. congetture di Tait); nel 1994 A.K. Kelmans dimostrò che la congettura di Barnette equivale all’affermazione che fissati due spigoli di una stessa faccia del poliedro corrispondente al grafo, esiste un circuito hamiltoniano che include il primo e non il secondo. L’affermazione sembra più forte di quella di Barnette, ma Kelmans dimostrò che un controesempio per l’una può essere trasformato in un controesempio per l’altra.

 

Nel 2005 Hertel dimostrò che la congettura di Barnette equivale all’affermazione che fissati tre archi consecutivi del grafo (ossia tali che i nodi alle estremità del secondo siano uno un’estremità del primo, l’altro un’estremità del terzo), esiste un circuito hamiltoniano che include il secondo, ma non primo e il terzo.

 

Jens M. Schmidt dimostrò che la congettura di Barnette  equivale all’affermazione che se un grafo trivalente 3-connesso e bipartito è tale che bisogna rimuovere almeno 4 archi per separarlo in due parti, ciascuna delle quali contenente un ciclo, allora fissando due archi qualsiasi esiste un circuito hamiltoniano che include il primo e non il secondo. Un grafo del genere non è necessariamente 4-connesso, perché potrebbe essere possibile rimuovere tre archi, spezzandolo in due componenti, una delle quali non contiene cicli.

 

Nel 1985 D.A. Holton, B. Manvel e Brendan D. McKay dimostrarono che un eventuale controesempio per la congettura deve avere almeno 68 nodi. Nel 2000 R.E.L Aldred, S. Bau, D.A. Holton e Brendan D. McKay portarono il limite a 86 e dimostrarono che fissati due archi qualsiasi in un ogni grafo planare, trivalente, 3-connesso e bipartito con fino a 60 nodi, esiste un circuito hamiltoniano che include il primo, ma non il secondo.

 

Una variante della congettura aggiunge la condizione che tutte le facce del poliedro corrispondente al grafo abbiano al massimo 6 lati; in questo caso R.E.L. Aldred, S. Bau, D.A. Holton, e Brendan D. McKay dimostrarono nel 2000 che un eventuale controesempio deve avere almeno 177 nodi. Il limite fu aumentato a 250 da Brendan D. McKay e Gunnar Brinkmann.

 

Nel 1975 P.R. Goodey dimostrò che la congettura è vera per i grafi corrispondenti a poliedri con facce tutte con 4 o 6 lati, più al massimo una con 8.

 

Nel 1956 Tutte dimostrò che ogni grafo planare e 4-connesso (ossia che non si divida in parti separate rimuovendo tre nodi qualsiasi) ha un circuito hamiltoniano, quindi la congettura di Barnette riguarda i grafi trova sul confine tra quelli che non hanno necessariamente un circuito hamiltoniano, perché sono 3-connessi e non soddisfano abbastanza condizioni (come quelle richieste dalle congetture di Tait e Tutte) e quelli che l’hanno, perché 4 connessi, anche senza soddisfare condisioni aggiuntive (come l’essere trivalenti e bipartiti).

 

Non si può rimuovere la condizione che il grafo sia trivalente, perché si conoscono grafi planari, bipartiti 3-connessi che non hanno circuiti hamiltoniani, come il grafo di Kirkman, mostrato nella figura seguente.

 

Grafo di Kirkman

 

Contattami

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