Pagina 6 di 7
HARMONIOUS TREES
Scopo del progetto
Nel 1980 Graham e Sloane hanno introdotto per primi la nozione di “classificazione armoniosa dei grafi”. Si tratta di uno schema di classificazionesu“base additiva”. Fondamentalmente, per un grafo con N archi, una classificazione armoniosa è tale se ogni nodo riceve una “etichetta” univoca per cui la somma modulo N dei nodi adiacenti è un numero che va da 0 fino a N-1.
Non si tratta di una banale classificazione nel senso che non tutti i grafi hanno una classificazione armoniosa. Se un grafo ha una classificazione armoniosa, diciamo che esso è armonioso.
Graham e Sloane hanno proposto la seguente congettura: ogni albero è armonioso. Equivalentemente, “congetturano” che possiamo classificare ogni albero con N nodi da 0 a N-1 senza ripetizione, tale che la somma modulo (N-1) dei due nodi adiacenti va da 0 a N-2.
In accordo con la “mappa dinamica” di Gallian su una classificazione di grafi, ci sono pochi risultati sugli alberi armoniosi. Graham e Sloane hanno provato che “i bruchi” sono armoniosi. Aldred e McKay hanno usato un programma al computer per verificare che tutti gli alberi con al massimo 26 nodi sono armoniosi. Recentemente, Fang ha proposto un nuovo algoritmo e ha spinto la verifica ad alberi fino a 31 nodi. Una versione distribuita di questo algoritmo è usata in questo sottoprogetto.
Questo sottoprogetto mira a verificare se alberi con una determinata dimensione sono tutti armoniosi. Se sono tutti armoniosi, verrà confermata la nostra fiducia in questa congettura. In caso contrario, se si trova un contro-esempio, questo smentirà immediatamente la congettura, conseguentemente confuterà un vecchio e duraturo problema nella teoria dei grafi.