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

Arboricità lineare (congettura della)

Congetture  Teoria dei grafi 

Nel 1981 Jin Akiyama, Geoffrey Exoo e Frank Harary proposero la congettura dell’arboricità lineare, che afferma che un grafo con grado massimo d, ossia tale che ogni nodo sia estremità di al massimo d archi, lo si può scomporre in una foresta lineare di Massimo intero non superiore a (d + 1) / 2 grafi.

Una foresta lineare è semplicemente un insieme di grafi lineari, nei quali ogni nodo è unito solo ai due adiacenti, salvo i due nodi estremi della catena. La congettura afferma quindi che un grafo con grado massimo d può essere scomposto in Massimo intero non superiore a (d + 1) / 2 percorsi lineari aperti.

 

Per qualsiasi grafo servono evidentemente almeno d / 2 percorsi ed è possibile dimostrare che d + 1 bastano. Che il numero indicato dalla congettura non possa essere ridotto in generale lo si vede dai grafi regolari, nei quali ogni nodo è connesso a d altri: se n è il numero di nodi e a il numero di archi, dato che un percorso non chiuso ha al massimo n – 1 archi, il numero di percorsi è almeno a / (n – 1) ≥ n * d / 2 / (n – 1) > d / 2 e il fatto che sia un intero implica che sia almeno Massimo intero non superiore a (d + 1) / 2.

 

La congettura è stata dimostrata vera per alcuni valori di d e per grafi particolari:

  • nel 1980 Jin Akiyama, Geoffrey Exoo e Frank Harary dimostrarono che la congettura è vera per d fino a 4 e per i grafi bipartiti (ossia tali che i nodi siano suddivisi in due insiemi e ciascuno sia connesso solo ai nodi dell’altro insieme);

  • nel 1984 B.P.H. Enomoto dimostrò che è vera per d = 5, 6, 8;

  • nel 1986 F. Guldan dimostrò che è vera per d = 10;

  • nel 1999 Jian-Liang Wu dimostrò che la congettura è vera per i grafi planari (ossia disegnabili sul piano senza incroci) per d diverso da 7;

  • nel 2008 Jian-Liang Wu e Yu-Wen Wu dimostrarono che la congettura è vera per i grafi planari per d = 7.

 

Nel 1988 N. Alon dimostrò che per i grafi regolari il numero di percorsi non supera d / 2 + c * log(log(d)) / log(d) per una costante positiva c.

 

Nel 2009 Marek Cygan, Lukasz Kowalik e Borut Lužar dimostrarono che per i grafi planari con d pari e maggiore di 8 il numero di percorsi può essere ridotto a d / 2, avanzando la congettura che questo limite valga anche per d uguale a 6 e 8.

Questa congettura era stata già dimostrata vera in alcuni casi particolari:

  • nel 1999 da Jian-Liang Wu per grafi privi di cicli di lunghezza 3 e d > 6;

  • nel 2008 Jian-Liang Wu e Yu-Wen Wu per grafi privi di cicli di lunghezza 5 e d > 6;

  • nel 2007 da Jian-Liang Wu, J.-F. Hou e G.-Z. Liu per grafi privi di cicli di lunghezza 4.

 

Per i grafi regolari sono stati fatti progressi nel ridurre il limite superiore del numero di percorsi:

  • nel 1992 N. Alon e J.H. Spencer dimostrarono che non supera d / 2 + c * (d^2 * log(d))^ (1 / 3) per una costante positiva c;

  • nel 2018 Asaf Ferber, Jacob Fox e Vishesh Jain dimostrarono che non supera d / 2 + c * (d^(2 – α)^ (1 / 3)) per due costanti positive c e α.

 

Sono anche stati cercati limiti al numero di percorsi nel caso si ponga un limite alla loro lunghezza:

  • nel 1999 C. Thomassen dimostrò che è possibile scomporre un grafo trivalente in percorsi lunghi al massimo 5 archi;

  • nel 2001 N. Alon, V.J. Teague e N.C. Wormald dimostrarono che se si limita a k la lunghezza massima di ogni percorso, per i grafi regolari il numero di percorsi non supera (k + 1) * d / (2 * k) + c * sqrt(k * d * log(d)) per 2 ≤ k < sqrt(d) e per una costante positiva c e non supera d per qualsiasi valore di k.

 

Trovare il minimo insieme di percorsi non è semplice: nel 1985 B. Péroche dimostrò che è un problema NP-completo, cioè che appartiene a una categoria di problemi per i quali non si conoscono algoritmi per i quali il numero di operazioni non cresca esponenzialmente col numero di elementi da trattare. Il problema resta intrattabile anche se ci si chiede semplicemente se due percorsi bastino.

Per grafi regolari con d = 3 si sa che due percorsi bastano e possono essere trovati in un tempo proporzionale al numero di nodi; è tuttora aperta la questione se il problema sia NP-completo per i grafi regolari con d = 4.

Contattami

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