Grafo aciclico numero di archi

[mariaaa1]

Domanda.Ho un grafo aciclico, con un nodo iniziale che chiamo vi, un nodo finale che chiamo vf: vi e vf sono connessi tra loro tramite altri nodi. Non è permesso l'arco che mi porta direttamente da vi a vf.

Allora, se il numero totale (vi + vf + tutti i nodi intermedi ) è pari ad n, quanti archi ho al massimo, considerando che appunto il grafo è aciclico, e che non viene dato alcun vincolo sul numero di archi incidenti o uscenti dal nodo, tranne quello che riguarda vi e vf ?

[hamming_burst]

"mariaaa":Domanda.Ho un grafo aciclico, con un nodo iniziale che chiamo vi, un nodo finale che chiamo vf: vi e vf sono connessi tra loro tramite altri nodi. Non è permesso l'arco che mi porta direttamente da vi a vf.

Allora, se il numero totale (vi + vf + tutti i nodi intermedi ) è pari ad n, quanti archi ho al massimo, considerando che appunto il grafo è aciclico, e che non viene dato alcun vincolo sul numero di archi incidenti o uscenti dal nodo, tranne quello che riguarda vi e vf ?

Ciao,
da quanto dici presumo che è un grafo orientato.
Perciò stiamo parlando di un DAG.
Il trucco sta nel pensare ad un ordinamento topologico.

Allora intanto ci riduciamo ad un grafo non orientato (non contanto $v_i$ e $v_f$ da trattare a parte) completamente connesso di nodi interni che chiamiamo $V_{i\n}$ allora il numero di archi saranno $|V_{i\n}|(|V_{i\n}|-1)/2$.

Se trasformassimo un grafo non orientato completamente connesso in uno orientato avremmo $|V_{i\n}|(|V_{i\n}|-1)$ archi.
Ora un arco in un grafo orientato può essere uscente od entrante in un nodo.
Mettiamo che abbiamo una combinazione $F()$di archi di un grafo orientato tale da non formare cicli, avremmo perciò un grafo non orientato con una configurazione tale che in un grafo orientato non forma cicli.

$F()$ può essere strutturato in questo modo: partendo da una foresta, prendiamo un nodo $v_1$ e lo colleghiamo con archi uscenti a tutti i nodi (tranne se stesso ovviamente). Ora prendiamo $v_2$ lo colleghiamo a tutti gli altri nodi tranne a $v_1$ con archi uscenti. E così via, così da formare un ordinamento topologico di un DAG.

Perciò avremo che gli archi totali in questa configurazione siano $|V_{i\n}|(|V_{i\n}|-1)/2$. Sommando poi gli archi di $v_i$ e $v_f$ che sono $2$.

Se non ho fatto castronerie, questo è tutto.
Si potrebbe essere anche più rigorosi a mio avviso, ma ti volevo dare più un'idea

[mariaaa1]

ok perfetto molto chiaro, l'idea c'è tutta:-) !!! Grazie mille!!!