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

Ricostruzione dei grafi dai nodi (congettura della)

Congetture  Teoria dei grafi 

Un grafo si dice “semplice” se non ha più archi con gli stessi nodi per estremi, né archi che congiungano un nodo a se stesso, e “non direzionato” se gli archi non hanno una direzione.

Se in un grafo semplice con n vertici cancelliamo in tutti gli n modi possibili un nodo e tutti gli archi che lo hanno per estremo, otteniamo n sottografi; un grafo si dice “ricostruibile dai nodi” se può essere ricostruito partendo da questi n sottografi.

La congettura della ricostruzione dei grafi dai nodi, avanzata da P.J. Kelly e Stanisław Marcin Ulam nel 1942, afferma che tutti i grafi semplici non direzionati finiti con almeno 3 nodi sono ricostruibili dai nodi.

 

La congettura non vale in generale per i grafi infiniti.

 

E’ stato dimostrato che la congettura vale per alcune famiglie infinite di grafi, in particolare vale per:

  • i grafi regolari, nei quali tutti i nodi sono connessi allo stesso numero di archi (Frank Harary, 1974);

  • gli alberi (Frank Harary, 1974);

  • i grafi costituiti da sottografi non connessi tra loro (Frank Harary, 1974);

  • i grafi tali che assegnando un numero reale a ogni nodo sono connesse da un arco tutte e sole le coppie di nodi i cui valori differiscono al massimo di 1 (M. von Rimscha, 1983);

  • i grafi che non hanno nodi connessi da un solo arco e che hanno un nodo rimuovendo il quale si divide il grafo in due parti separate (J.-A. Bondy, 1969);

  • i grafi planari tali che non sarebbero più planari se si aggiungesse in qualsiasi modo un arco tra due nondi non connessi;

  • i grafi planari tali che tutti i nodi si trovano sulla “faccia” più esterna ossia tali che aggiungendo un nodo esterno, sia possibile connetterlo a tutti gli altri senza incrociare archi.

 

Nel 1990 Béla Bollobás dimostrò che quasi tutti i grafi sono ricostruibili, nel senso che la frazione di quelli non ricostruibili (se esistono) tende a zero all’aumentare del numero di nodi.

 

Brendan D. McKay verificò nel 1997 la congettura per tutti i grafi con fino a 11 nodi.

 

Nel 1974 Frank Harary estese la congettura ai grafi direzionati (nei quali ogni arco ha una direzione di percorrenza) con almeno 5 vertici, ma nel 1977 P.K. Stockmeyer, dimostrò che la congettura non vale per i grafi direzionati, mostrando una famiglia infinita di grafi non ricostruibili. Questo fece sorgere qualche dubbio sulla validità della congettura per i grafi non direzionati.

 

Nel 1979 F. Ramachandran propose una versione più ristretta della congettura, valida per i grafi direzionati, nota come “nuova congettura di ricostruzione dei grafi direzionati: se D ed E sono due grafi direzionati tra i nodi quali esiste una corrispondenza biunivoca che fa corrispondere a ogni nodo v di D un nodo f(v) di E, tali che per ogni nodo v di D, D privato di v sia isomorfo a E privato di f(v), il numero di archi uscenti da v sia uguale al numero di archi uscenti da f(v) e il numero di archi entranti in v sia uguale al numero di archi entranti in f(v), allora D ed E sono isomorfi.

Questa versione implica la congettura per i grafi non direzionati.

Contattami

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