[Gulli] Teoria dei Grafi e Programmazione (Collaborazione)

[G. Sica]

Salve a tutti,

Sto cercando un programmatore Linux con cui collaborare alla
realizzazione di un software open source utile per analizzare il DNA di
grafi semplici. Sono uno studente di dottorato presso l'Università di
Leiden, in Olanda, e mi occupo di teoria dei grafi e delle relative
applicazioni in ambito linguistico. Uno dei problemi principali in
questo campo di ricerca è dato dal riuscire a determinare le proprietà
di grafi molto complessi. Mi spiego meglio. Quando si ha un grafo con un
numero molto elevato di elementi e di collegamenti tra elementi è spesso
difficile distinguerlo da un grafo simile e determinarne le relative
proprietà. Per questo motivo è stata sviluppata la nozione di DNA del
grafo. Si tratta di una sorta di codice da cui è possibile derivare,
applicando pochi teoremi, le caratteristiche del grafo in esame. Nel
seguito dell'e-mail invio le informazioni relative alle modalità per
calcolare il DNA di un grafo e i dettagli relativi al software. Si
tratta di un progetto piuttosto semplice, che potrebbe però essere molto
utile. Spero che qualcuno possa essere interessato. Nel caso, prego di
usare il mio indirizzo e-mail privato per rispondere. Mi scuso molto per
il disturbo e per l'eventuale uso improprio della mailing list. Questo
non è un messaggio di spamming.

Grazie mille,
Nico

"Knowledge shared is power"

Contatti:
c/o
Polimetrica Onlus
Corso Milano 26
20052 Monza Mi Italia
Tel/Fax: 039.2301829
E-mail: g.sica chiocciola polimetrica.org

Faculty of Philosophy
Leiden University
http://www.leiden.edu

1st World Conference and School on Universal Logic
http://www.uni-log.org

*****************************************
*****************************************

Spiego il concetto di DNA di un grafo attraverso un semplicissimo
esempio.

Grafo:
o---o---o

DNA:
11
11
1212

Il grafo in esame è scomponibile in 3 sottografi:
o---o
o---o
o---o---o

A ciascuno dei sottografi è stata associata una stringa composta da
coppie di numeri: 
11 nel primo caso.
11 nel secondo caso.
1212 nel terzo caso.

Ogni coppia di numeri corrisponde ad una relazione inclusa nel
sottografo e rappresenta il numero totale di collegamenti dei due
elementi uniti attraverso la relazione.

Nel primo e nel secondo caso abbiamo una sola relazione che unisce due
elementi che hanno entrambi un collegamento totale. 
La stringa associata è infatti 11. 

Nel terzo caso abbiamo due relazioni identiche, che uniscono due
elementi cha hanno rispettivamente un collegamento e due collegamenti
totali. La stringa associata è infatti 1212. 

L'insieme totale delle stringhe si chiama DNA del grafo.
Tutti i numeri sono ordinati in maniera decrescente.

Il programma per cui si richiede la collaborazione dovrebbe avere due
funzioni.
1. Costruire il grafo.
2. Definire il DNA del grafo.

Costruire il grafo significa stabilire tutte le combinazioni che lo
compongono.

Grafo:
a   b   c
o---o---o

Combinazioni:
(a,b),(b,c)

Bisogna quindi inserire le combinazioni che compongono il grafo. 
Sarebbe ottimo qualora fosse possibile aggiungere anche la
rappresentazione visuale del grafo.

Un modo possibile di realizzare il software potrebbe essere quello di
utilizzare Python + NetworkX (per la rappresentazione visuale del
grafo).