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

Harborth (congettura di)

Congetture  Teoria dei grafi 

Il teorema di Fáry afferma che un grafo planare, ossia tale che può essere disegnato sul piano senza incroci, può essere disegnato con archi costituiti da segmenti.

 

La congettura proposta da Heiko Harborth afferma che un grafo planare può essere disegnato con archi costituiti da segmenti di lunghezza intera.

 

Il teorema è stato dimostrato per tutti i grafi che possono essere ridotti a un solo punto applicando ripetutamente le seguenti operazioni:

  • rimuovere i nodi connessi ad altri da uno o due archi;

  • sostituire i nodi connessi ad altri da tre archi con un arco tra due qualsiasi dei tre nodi ai quali è connesso; se tali nodi sono già connessi da un arco, si rimuove semplicemente il nodo.

La dimostrazione è costruttiva e consiste nell’invertire il processo di eliminazione: ogni nodo eliminato nei due casi precedenti, infatti, può essere rimpiazzato da un nodo connesso agli stessi altri nodi con segmenti di lunghezza razionale. Basta poi moltiplicare tutte le lunghezze per il minimo comune multiplo dei denominatori, per avere tutte lunghezze intere.

La dimostrazione vale per alcune categorie di grafi planari, tra le quali:

  • i grafi bipartiti;

  • i grafi nei quali ogni nodo si trova sul perimetro del grafo;

  • i grafi che hanno due nodi estremi, connessi da una combinazione di cammini lineari in serie e in parallelo (come un circuito elettrico formato da una combinazione di componenti in serie e in parallelo);

  • i grafi corrispondenti ai 5 solidi platonici (aventi i vertici per nodi e gli spigoli per archi);

  • i grafi di grado massimo non superiore a 4, che possono essere divisi in parti separate rimuovendo 3 archi o contengono il grafo a diamante mostrato nella figura seguente.

 

Grafo a diamante

 

 

Il teorema dimostrato nel 1945 da Paul Erdös e Norman H. Anning afferma che non esiste un insieme infinito di punti sul piano, non tutti sulla stessa retta, con tutte le distanze tra essi intere. Questo non dimostra che la congettura di Harboth sia falsa, ma implica che all’aumentare del numero di nodi le distanze crescono illimitatamente.

 

La congettura sarebbe dimostrata vera, se esistesse una soluzione del problema di Erdös – Ulam.

 

Una versione più forte, proposta da Michael Kleber nel 2008, afferma che un grafo planare può essere disegnato con archi costituiti da segmenti di lunghezza intera e nodi con coordinate intere.

Di questa congettura si sa che vale per i grafi planari nei quali se:

  • ogni nodo è connesso a 3 altri (J. Geelen, A. Guo, D. McKinnon, 2008);

  • vi sono al massimo 4 nodi connessi a più di 3 altri (A. Dubickas, 2011);

  • ogni nodo è connesso ad al massimo 4 altri e almeno un nodo è connesso a meno di 4 altri (Vladimir I. Benediktovich, 2013).

Contattami

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