Ma gli archi nei grafi non orientati come vanno considerati?
Salve, sto cercando di capire il funzionamento dell'algorotimo PageRank e le mie ricerche mi hanno portato verso la teoria dei grafi e il modello stacanovista markoviano.
Per il momento credo di aver compreso bene il sistema dei grafi (tutto abbastanza semplice imho) ma mi sfugge una questione.
Vedendo l'immagine cho ho allegato, c'è un esempio di grafo non orientato, tuttavia le formule nonché la matrice di adiacenza parlano chiaro, ovvero, è come se comunque ogni vertice sia collegato con il successivo tramite un orientamento a senso unico.
L'immagine dovrebbe essere abbastanza esaustiva, grazie in anticipo.
Per il momento credo di aver compreso bene il sistema dei grafi (tutto abbastanza semplice imho) ma mi sfugge una questione.
Vedendo l'immagine cho ho allegato, c'è un esempio di grafo non orientato, tuttavia le formule nonché la matrice di adiacenza parlano chiaro, ovvero, è come se comunque ogni vertice sia collegato con il successivo tramite un orientamento a senso unico.
L'immagine dovrebbe essere abbastanza esaustiva, grazie in anticipo.
Risposte
La matrice di adiacenza è simmetrica (o, equivalentemente, si considera solo la meta sopra o quella sotto la diagonale principale). Se v1 è adiacente a v2, allora v2 è adiacente a v1. Nel tuo secondo esempio invece v2 è adiacente a v1, ma non viceversa.
Ma a conti fatti se dovessi scrivere la formula del secondo esempio, non sarebbe ugualmente
V = {1,2,3,4} E={(1,2);(1,3);(2,3);(3,4)}
?
non vedo dove sia la sifferenza. Inoltre non mi è chiaro cosa rappresentano gli archi privi di freccia. Sono archi bidirezionali o addirittura privi di direzione? E in questo caso che senso hanno?
V = {1,2,3,4} E={(1,2);(1,3);(2,3);(3,4)}
?
non vedo dove sia la sifferenza. Inoltre non mi è chiaro cosa rappresentano gli archi privi di freccia. Sono archi bidirezionali o addirittura privi di direzione? E in questo caso che senso hanno?
Sì, la formula nel secondo esempio sarebbe proprio quella. Ma nel primo esempio in realtà E={(1,2);(2,1);(1,3);(3,1);(2,3);(3,2);(3,4);(4,3)}. Nei grafi non orientati tutti gli archi sono bidirezionali (quindi in E si possono elencare solo la metà delle coppie, le altre sono implicite). Nei grafi orientati alcuni archi possono essere bidirezionali, ma in generale non lo sono.
ahh ecco svelato l'arcano era sballato l'esempio che ho trovato... in effetti poi scrivendo la matrice di adiacenza mi sono accorto delel differenze tra l'orientato e il non orientato 
Ho un'altra domanda (misà che vi tartasserò con i miei dubbi, spero che almeno possa farlo e non infranga il regolamento)
Cosa significa che una diagonale principlae nella matrice di adiacenza è simmetrica?
E poi questi simboli?
http://img12.imageshack.us/img12/8694/xl09.jpg
Cosa significa che una diagonale principlae nella matrice di adiacenza è simmetrica?
E poi questi simboli?
http://img12.imageshack.us/img12/8694/xl09.jpg
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
