Diferența dintre graficul direcționat și nedirecționat

Graficul direcționat 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 de vârfuri) care sunt conectate prin intermediul unor legături (reprezentate de margini). Folosind notații matematice, un grafic poate fi reprezentat de G, unde G = (V, E) și V este setul de vârfuri și E este setul de margini. Într-un grafic nedirecționat, nu există o direcție asociată cu marginile care conectează vârfurile. Într-un grafic direcționat există o direcție asociată cu marginile care conectează vârfurile.

Grafic nedirecționat

După cum am menționat mai devreme, un grafic nedirecționat este un grafic în care nu există nici o direcție în marginile care leagă vârfurile din grafic. Figura 1 prezintă un grafic nedirecționat cu setul 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, marginile dintr-un grafic nedirecționat nu sunt perechi ordonate. Aceasta este principala caracteristică a unui grafic nedirecționat. Graficele nedirecționate pot fi folosite pentru a reprezenta relațiile simetrice între obiectele reprezentate de vârfuri. De exemplu, o rețea rutieră cu două căi care conectează un set de orașe poate fi reprezentată utilizând un grafic nedirecționat. Orașele pot fi reprezentate de vârfurile din grafic, iar marginile reprezintă drumurile pe două căi care leagă orașele.

- <->

Grafic Direcționat

Un grafic orientat este un grafic în care marginile din grafic care leagă nodurile au o direcție. Figura 2 prezintă un grafic orientat cu setul 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 într-un grafic nedirecționat sunt ordonate perechi. Formal, marginea e într-un grafic direcționat poate fi reprezentată de perechea ordonată e = (x, y) unde x este vârful care se numește originea, sursa sau punctul inițial al muchiei e, iar punctul vertex y se numește terminus, terminând vârful sau punctul terminal. De exemplu, o rețea rutieră care conectează un set de orașe folosind drumuri de o singură cale poate fi reprezentată utilizând un grafic nedirecționat. Orașele pot fi reprezentate de vârfurile din grafic, iar marginile direcționate reprezintă drumurile care conectează orașele în funcție de direcția pe care traficul le circulă pe drum.

Care este diferența dintre graficul direcționat și graficul nedirecționat?

într-un grafic orientat, o margine 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 margine este o pereche neordonată, deoarece nu există nici o direcție asociată cu o margine.Graficele nedirecționate pot fi folosite pentru a reprezenta relațiile simetrice între obiecte. Gradul și gradul în afara fiecărui nod într-un grafic nedirecționat sunt egale, dar acest lucru nu este valabil pentru un grafic orientat. 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 valabil 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ă conversia unui grafic direcționat într-un grafic nedirecționat.