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

Doppia copertura con cicli (congettura della)

Congetture  Teoria dei grafi 

La congettura della doppia copertura con cicli afferma che per ogni grafo senza ponti (ossia senza archi che se rimossi dividono il grafo in parti separate) esiste un insieme di percorsi chiusi, che insieme attraversano ogni arco esattamente due volte.

L’eccezione per i ponti è ovvia, perché un ponte non può far parte di alcun percorso chiuso.

Non è necessaro che un unico percorso passi per tutti gli archi: si possono utilizzare, se necessario, tanti percorsi chiusi; la condizione vincolante è che ogni arco sia attraversato esattamente due volte.

Un grafo ciclico, costituito da un anello di archi, come i lati di un poligono, ammette un solo percorso chiuso, quindi nella congettura si considera valido utilizzare due volte lo stesso percorso.

 

La congettura è comunemente attribuita a George Szekeres, che la propose nel 1973, e a Paul Seymour, che la propose indipendentemente nel 1979, ma è una conseguenza di una congettura più generale di William Thomas Tutte.

 

Il caso critico è quello degli snark, ossia dei grafi trivalenti, 3-connessi non colorabili con 3 colori in modo che ogni vertice sia comune a tre archi di colori diversi (v. congettura di Tait): se la congettura vale per essi, vale per tutti i grafi. L’eventuale controesempio minimo, inoltre, deve essere uno snark.

 

Un metodo d’attacco alla congettura è dimostrare che un eventuale controesempio è riducibile a un altro con meno nodi: ripetendo il procedimento si arriverebbe a un grafo composto da un solo ciclo, che però ammette una doppia copertura.

Sicuramente però non è possibile dimostrare la congettura dimostrando che un eventuale controesempio deve contenere almeno una tra le configurazioni di un insieme finito e che tutte queste sono riducibili, un po’ come è stato fatto per il teorema dei quattro colori (v. numeri di Heawood), perché il minimo ciclo contenuto in uno snark può essere grande a piacere.

 

Nel 1986 L. Goddyn dimostrò che un eventuale controesempio non può includere cicli formati da meno di 7 archi, limite che poi portò a 10; Andreas Huck dimostrò nel 1997 che devono essere almeno 12.

Dal limite dimostrato da Goddyn segue che la congettura della doppia copertura con cicli seguirebbe automaticamente, se fosse dimostrata la congettura proposta da F. Jaeger e Swart che uno Snark deve contenere un ciclo di non più di 6 archi.

 

La congettura è stata dimostrata nel caso di grafi planari e di grafi che non contengono un sottografo riducibile, facendo collassare nodi (v. congettura di Hadwiger (I)), al grafo di Petersen, mostrato nella figura seguente (Andreas Huck, 1997).

 

Grafo di Petersen

 

 

Una variante più forte della congettura è che per ogni grafo senza ponti esiste un insieme di esattamente n percorsi chiusi che insieme attraversano ogni arco esattamente due volte. Anche in questo caso il minimo controesempio, se esiste, è uno snark.

Il grafo di Petersen dimostra che n deve essere almeno 5; Nel 1997 Andreas Huck dimostrò che:

  • per n = 5 e n = 6 il minimo controesempio non può contenere cicli formati da meno di 10 archi;

  • per n = 7 il minimo controesempio non può contenere cicli formati da meno di 11 archi;

  • per n = 8 il minimo controesempio non può contenere cicli formati da meno di 12 archi;

  • un grafo che non contenga un sottografo riducibile al grafo di Petersen ha una doppia copertura con esattamente 5 cicli, che può essere costruita in un tempo che cresce come una potenza del numero di archi.

L’ultima parte deriva dalla dimostrazione di N. Robertson, P.D. Seymour e R. Thomas che un grafo del genere contiene almeno un ciclo di al massimo 5 archi.

 

L. Goddyn propose nel 1988 una versione più forte della congettura, secondo la quale esiste una copertura che include un qualsiasi ciclo specificato.

Contattami

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