TuLKaS85
08-04-2011, 19:47
salve
devo trovare le facce di un grafo planare.
Un grafo planare, è un grafo in cui gli archi non si incrociano mai se non nei vertici stessi. Nel mio caso gli archi sono dei segmenti che uniscono i vertici, e sono non orientati, quindi se ho due vertici a,b collegati da un arco e1 è possibile che avvengano le seguenti comunicazioni
a->b
b->a
dove le frecce rappresentano l'arco e1
Non è un problema di facile risoluzione e non mi interessano metodi particolarmente efficienti.
Qualcuno con esperienze in tal senso sa darmi qualche consiglio ?
A livello di implementazione, diciamo che riesco a ricavarmi un grafo planare, con una struttura contente le coordinate x,y dei nodi ed un altra gli archi, ogni arco non è altro che una coppia di nodi.
Sto lavorando in java, ma se qualcuno ha qualche idea usando qualche altro linguaggio non ci sono problemi.
devo trovare le facce di un grafo planare.
Un grafo planare, è un grafo in cui gli archi non si incrociano mai se non nei vertici stessi. Nel mio caso gli archi sono dei segmenti che uniscono i vertici, e sono non orientati, quindi se ho due vertici a,b collegati da un arco e1 è possibile che avvengano le seguenti comunicazioni
a->b
b->a
dove le frecce rappresentano l'arco e1
Non è un problema di facile risoluzione e non mi interessano metodi particolarmente efficienti.
Qualcuno con esperienze in tal senso sa darmi qualche consiglio ?
A livello di implementazione, diciamo che riesco a ricavarmi un grafo planare, con una struttura contente le coordinate x,y dei nodi ed un altra gli archi, ogni arco non è altro che una coppia di nodi.
Sto lavorando in java, ma se qualcuno ha qualche idea usando qualche altro linguaggio non ci sono problemi.