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

Ricostruzione dei grafi dagli archi (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.

Se in un grafo con n archi cancelliamo in tutti gli n modi possibili un arco, otteniamo n sottografi; un grafo si dice “ricostruibile dagli archi” se può essere ricostruito partendo da questi n sottografi.

La congettura della ricostruzione dei grafi dagli archi, avanzata da Frank Harary nel 1964, afferma che tutti i grafi semplici con almeno 4 archi sono ricostruibili dagli archi.

 

L. Lovász dimostrò nel 1972 che la congettura è vera per tutti i grafi con n nodi e più di nlog2n archi.

Contattami

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