Newsgroup: it.scienza.informatica
Titolo: Problema grafo

Salve a tutti, ho una struttura dati che avrei intenzione di rappresentare 
con un grafo, in cui ogni nodo ha queste caratteristiche:
* numero variabile di rami entranti (>=2)
* un solo ramo uscente
Ad ogni nodo è associato un valore, calcolato in funzione dei rami entranti: 
tale valore viene propagato al ramo uscente.
Il problema è: come calcolo il valore del nodo x ? La risposta più ovvia 
potrebbe essere di applicare la funzione ricorsivamente ai rami entranti, 
ma non credo sia la soluzione più efficiente, e poi se nel grafo ci sono 
cicli che succede ?
Secondo voi è possibile ricondurre questo problema a qualche algoritmo 
efficiente sui grafi (che so, Dijkstra, etc..) ? 
In caso di risposta positiva, qualcuno sa dirmi a grandi linee la strada da 
seguire utilizzando la Boost Graph Library in C++ ?
Grazie in anticipo...:)
-- 
Lorenzo

 cicli che succede ?
Fammi capire bene: tu hai un grafo orientato (dato che parli di entrata 
e uscita) in cui ogni nodo ha piů archi entranti e un solo arco uscente.
Il valore da assegnare agli archi in uscita (e quindi ai nodi) dipende 
dal numero e valore degli archi entranti.
A questo punto mi chiedo:
Esiste un input? Se si la risposta non richiede l'utilizzo di algoritmi 
sui grafi ma solo un po' di calcolo matriciale. Se no, invece bisogna 
specificare meglio il problema.
A questo punto perň ti consiglierei di cercare algoritmi legati ai 
"network", cioé a grafi orientatri in cui c'č "conservazione della 
massa" attorno ai nodi (ossia quello che entra č uguale a quello che esce).
Ciao
Stefano

 esce).
Mi sai dare qualche riferimento ? Comunque la "conservazione della massa" è 
valida anche se il valore degli archi entranti viene "passato" attraverso
la funzione F di cui sopra ?
Grazie per ora...:)
-- 
Lorenzo

 cicli che succede ?
Non te lo saprei dimostrare, ma così a naso azzarderei queste due cose:
In un grafo come quello da te descritto
    1) non ci può essere più di un ciclo
    2) se non ci sono cicli, il grafo degenera in un albero (e quindi puoi
utilizzarne tutte le proprietà)
Della seconda sono quasi certo, sulla prima ho qualche dubbio.
Ste

 Della seconda sono quasi certo, sulla prima ho qualche dubbio.
Anzi, leggendo quello che hai scritto dopo direi che la 1) può diventare
tranquillamente "non ci possono essere cicli", e quindi il grafo in
questione è sempre un albero. A te la dimostrazione.
Ste

 
Questi libri potrebbero aiutarti:
Graphs, Networks & Algorithms
by Dieter Jungnickel, E. Becker (Editor)
Digraphs: Theory, Algorithms and Applications
by Jorgen Bang-Jensen, et al
Matrix Methods: An Introduction
by Richard Bronson (Hardcover -- March 1991)
ciao Stefano
PS cosa ne dici della question cicli si/no (proposta da un altro stefano)?

 questione è sempre un albero. A te la dimostrazione.
Ma intendi che il grafo in questione può essere sempre "ridotto" ad un 
albero equivalente, oppure proprio che non possono esserci ?
Grazie !! :)
-- 
Lorenzo

 Grazie !! :)
Prego!
Ste

 all'equipaggio di
it.scienza.informatica:

L'albero e' (per definizione) un grafo indiretto connesso aciclico.
Le proprieta' desiderate - un ramo uscente e n>=2 rami entranti -
rispecchiano solo i nodi interni di un albero radicato, quindi radice
e foglie non posseggono quelle proprieta'.
Se a tali proprieta' possono far deroga un nodo, che accetta solo rami
entranti, e certe foglie, che posseggono solo rami uscenti, allora
siamo di fronte proprio ad un albero radicato: la radice e'
determinata dall'unico nodo senza rami uscenti.
Se tralasciamo il discorso esposto sopra, una considerazione
particolare deve essere fatta sui cicli.
In presenza di cicli l'albero se ne va a benedire. I cicli sono,
diciamo, "orientati" xche' hanno un senso di rotazione.
Penso che secondo le tue proprieta' (compresa quella dei nodi senza
rami entranti) in tale struttura dati si possa avere al massimo un
ciclo.
Ammettiamo esistano 2 cicli, essi possono essere disposti:
1) unendo i due distinti cicli tramite un percorso con nodi e rami
(visivamente due cerchi con una linea che li unisce)
2) avendo in comune alcuni nodi, a formare qundi una specie di "8"
Nel caso 1) il percorso che unisce i cicli ha un estremo che entra nel
primo ciclo, mentre l'altro estremo e' un ramo uscente da un certo
nodo del secondo ciclo. Tale nodo possiede un primo ramo uscente che
fa parte del ciclo, ed un altro ramo uscente che fa parte del percorso
sudetto. Cio' non e' possibile in quanto contraddice le proprieta' dei
nodi (un solo ramo uscente per nodo).
Nel caso 2) il cammino in comune ai due cicli possiede ad una
estremita' un nodo in cui entrano 2 rami: sia del primo ciclo che del
secondo. L'altra estremita' e' un nodo che ha 2 rami uscenti: uno per
il primo ciclo e l'altro per il secondo ciclo. Per lo stesso motivo
qui sopra cio' non e' possibile.
Quindi non possono esistere 2 cicli. Penso che il discorso sia
facilmente generalizzabile per n>2 cicli.
Spero che il ragionamento sia corretto e in qualche modo utile al tuo
problema: avere un solo ciclo semplifica le cose, no? :-)))
-- 
Linux Registered User #181013
[Exokernels] Although one approach to eliminating bloated, buggy,
unreliable operating systems is to make them smaller, a more radical
one is to eliminate the operating system altogether.

I1-------A----|
              |        |
              ------|
I2-------B----|
              |        |
              ------|
Questo grafo soddisfa le proprietà richieste eppure possiede 2 cicli.

 all'equipaggio di
it.scienza.informatica:

Faccio fatica a riconoscere i cicli nel tuo grafo, il disegno non si
capisce molto bene.
Forse vuoi dirmi che un grafo non connesso puo' avere un ciclo per
ogni sottografo? Si' in effetti e' vero, allora aggiungiamo al mio
post precedente il vincolo di grafo connesso.
