Indice articoli

Valutazione attuale: 5 / 5

Stella attivaStella attivaStella attivaStella attivaStella attiva
 
Yoyo




HARMONIOUS TREES
 
 
 
Yoyo_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.

 


Accedi per commentare

Articoli

Written on 17/01/2022, 14:43 by boboviz
rosetta-e-virtualboxDa un po' di tempo il progetto Rosetta@Home sembra aver decisamente puntato sull’applicativo VirtualBox (Phyton), lasciando spesso vuote le code per gli...

Ultime dal Blog

Written on 03/08/2021, 22:27 by boboviz
foldit-e-alphafoldLa "svolta" AlphaFold è una delle più importanti degli ultimi anni, motivo per cui ho deciso di tradurre l'articolo che parla della sua implementazione in...