Grafic regizat vs nedirecționat
Un grafic este o structură matematică care este alcătuită dintr-un set de vârfuri și muchii. Un grafic reprezintă un set de obiecte (reprezentate prin vârfuri) care sunt conectate prin niște legături (reprezentate prin muchii). Folosind notații matematice, un grafic poate fi reprezentat prin G, unde G=(V, E) și V este mulțimea vârfurilor și E este mulțimea muchiilor. Într-un graf nedirecționat nu există nicio direcție asociată cu muchiile care leagă vârfurile. Într-un grafic direcționat există o direcție asociată cu muchiile care leagă vârfurile.
Grafic nedirecționat
Așa cum am menționat mai devreme, un grafic nedirecționat este un grafic în care nu există nicio direcție în muchiile care leagă vârfurile din grafic. Figura 1 prezintă un grafic nedirecționat cu un set de vârfuri V={V1, V2, V3}. Setul de muchii din graficul de mai sus poate fi scris ca V={(V1, V2), (V2, V3), (V1, V3)}. De asemenea, se poate observa că nimic nu împiedică scrierea setului de muchii ca V={(V2, V1), (V3, V2), (V3, V1)} deoarece muchiile nu au o direcție. Prin urmare, muchiile dintr-un grafic nedirecționat nu sunt perechi ordonate. Aceasta este caracteristica principală a unui grafic nedirecționat. Graficele nedirecționate pot fi folosite pentru a reprezenta relații simetrice între obiecte care sunt reprezentate prin vârfuri. De exemplu, o rețea de drumuri 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 muchiile din grafic care leagă vârfurile au o direcție. Figura 2 prezintă un grafic direcționat cu un set de vârfuri V={V1, V2, V3}. Setul de muchii din graficul de mai sus poate fi scris ca V={(V1, V2), (V2, V3), (V1, V3)}. Muchiile dintr-un grafic nedirecționat sunt perechi ordonate. În mod formal, muchia e într-un grafic direcționat poate fi reprezentată prin perechea ordonată e=(x, y) unde x este vârful numit origine, sursă sau punctul inițial al muchiei e, iar vârful y este numit capăt, vârf terminal sau punct terminal. De exemplu, o rețea de drumuri care conectează un set de orașe folosind drumuri cu sens unic poate fi reprezentată folosind un grafic nedirecționat. Orasele pot fi reprezentate prin varfurile din grafic iar marginile directionate reprezinta drumurile care leaga orasele avand in vedere directia in care circula circulatia in drum.
Care este diferența dintre Graficul direcționat și Graficul nedirecționat?
Într-un grafic direcționat o muchie este o pereche ordonată, unde perechea ordonată reprezintă direcția muchiei care leagă cele două vârfuri. Pe de altă parte, într-un grafic nedirecționat, o muchie este o pereche neordonată, deoarece nu există nicio direcție asociată cu o muchie. Graficele nedirecționate pot fi folosite pentru a reprezenta relații simetrice între obiecte. Gradul interior și gradul exterior al fiecărui nod dintr-un graf nedirecționat este egal, dar acest lucru nu este adevărat pentru un graf direcționat. Când folosiți 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 nedirecționat poate fi convertit într-un grafic direcționat prin înlocuirea fiecărei muchii cu două muchii 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.
