Grafic direcționat vs.
Un grafic este o structură matematică care este alcătuită din set de vârfuri și muchii. Un grafic reprezintă un set de obiecte (reprezentate prin vârfuri) care sunt conectate prin intermediul unor legături (reprezentate prin margini). Folosind notații matematice, un grafic poate fi reprezentat de G, unde G = (V, E) și V este mulțimea vârfurilor și E este mulțimea muchiilor. Într-un grafic nedirecționat nu există nicio direcție asociată cu marginile care leagă vârfurile. Într-un grafic direcționat există o direcție asociată cu marginile care leagă vârfurile.
Grafic nedirectat
După cum sa menționat mai devreme, un grafic nedirecționat este un grafic în care nu există direcție în margini care leagă vârfurile din grafic. Figura 1 prezintă un grafic nedirecționat cu set de vârfuri V = {V1, V2, V3}. Setul de margini din graficul de mai sus poate fi scris ca V = {(V1, V2), (V2, V3), (V1, V3)}. De asemenea, se poate observa că nu există nimic care să împiedice scrierea setului de margini ca V = {(V2, V1), (V3, V2), (V3, V1)} deoarece marginile nu au o direcție. Prin urmare, muchiile dintr-un grafic neorientat nu sunt perechi ordonate. Aceasta este principala caracteristică a unui grafic nedirecționat. Graficele nedirecționate pot fi folosite pentru a reprezenta relații simetrice între obiectele care sunt reprezentate de vârfuri. De exemplu, o rețea rutieră cu două sensuri care conectează un set de orașe poate fi reprezentată folosind un grafic nedirecționat. Orașele pot fi reprezentate prin vârfurile din grafic, iar marginile reprezintă drumurile cu două sensuri care leagă orașele.
Grafic regizat
Un grafic direcționat este un grafic în care marginile din graficul care leagă vârfurile au o direcție. Figura 2 prezintă un grafic direcționat cu set de vârfuri V = {V1, V2, V3}. Setul de margini din graficul de mai sus poate fi scris ca V = {(V1, V2), (V2, V3), (V1, V3)}. Marginile dintr-un grafic nedirectat sunt perechi ordonate. În mod formal, muchia e într-un grafic direcționat poate fi reprezentată de perechea ordonată e = (x, y) unde x este vârful care se numește origine, sursă sau punctul inițial al muchiei e, iar vârful y se numește terminal, vârf de terminare sau punct terminal. De exemplu, o rețea rutieră care conectează un set de orașe folosind drumuri cu sens unic poate fi reprezentată folosind un grafic nedirecționat. Orașele pot fi reprezentate prin vârfurile din grafic, iar marginile direcționate reprezintă drumurile care leagă orașele, având în vedere direcția pe care circulă traficul pe drum.
Care este diferența dintre graficul direcționat și graficul nedirectat?
Într-un grafic direcționat, o margine este o pereche ordonată, unde perechea ordonată reprezintă direcția marginii care leagă cele două vârfuri. Pe de altă parte, într-un grafic nedirecționat, o margine este o pereche neordonată, deoarece nu există o direcție asociată cu o margine. Graficele nedirecționate pot fi folosite pentru a reprezenta relații simetrice între obiecte. În grad și în afara fiecărui nod dintr-un grafic nedirecționat este egal, dar acest lucru nu este adevărat pentru un grafic direcționat. Atunci când se utilizează o matrice pentru a reprezenta un grafic nedirecționat, matricea devine întotdeauna un grafic simetric, dar acest lucru nu este adevărat pentru un grafic direcționat. Un grafic nedirectat poate fi convertit într-un grafic direcționat prin înlocuirea fiecărei muchii cu două margini direcționate care merg în direcție opusă. Cu toate acestea, nu este posibil să convertiți un grafic direcționat într-un grafic nedirecționat.
