Directed vs Undirected Graph
Graf je matematička struktura koja se sastoji od skupa vrhova i ivica. Graf predstavlja skup objekata (predstavljenih vrhovima) koji su povezani preko nekih veza (predstavljenih ivicama). Koristeći matematičke notacije, graf se može predstaviti sa G, gdje je G=(V, E) i V je skup vrhova, a E je skup ivica. U neusmjerenom grafu nema smjera povezanog s rubovima koji povezuju vrhove. U usmjerenom grafu postoji smjer povezan s rubovima koji spajaju vrhove.
Neusmjereni grafikon
Kao što je ranije spomenuto, neusmjereni graf je graf u kojem nema smjera u rubovima koji povezuju vrhove u grafu. Slika 1 prikazuje neusmjereni graf sa skupom vrhova V={V1, V2, V3}. Skup ivica u gornjem grafu može se zapisati kao V={(V1, V2), (V2, V3), (V1, V3)}. Takođe se može primetiti da ništa ne sprečava da se skup ivica zapiše kao V={(V2, V1), (V3, V2), (V3, V1)} jer ivice nemaju pravac. Stoga ivice u neusmjerenom grafu nisu uređeni parovi. Ovo je glavna karakteristika neusmjerenog grafa. Neusmjereni grafovi se mogu koristiti za predstavljanje simetričnih odnosa između objekata koji su predstavljeni vrhovima. Na primjer, dvosmjerna putna mreža koja povezuje skup gradova može se predstaviti korištenjem neusmjerenog grafa. Gradovi se mogu predstaviti vrhovima na grafu, a ivice predstavljaju dvosmjerne ceste koje povezuju gradove.
Directed Graph
Usmjereni graf je graf u kojem ivice u grafu koje povezuju vrhove imaju smjer. Slika 2 prikazuje usmjereni graf sa skupom vrhova V={V1, V2, V3}. Skup ivica u gornjem grafu može se zapisati kao V={(V1, V2), (V2, V3), (V1, V3)}. Rubovi u neusmjerenom grafu su uređeni parovi. Formalno, rub e u usmjerenom grafu može se predstaviti uređenim parom e=(x, y) gdje je x vrh koji se naziva ishodište, izvor ili početna tačka ruba e, a vrh y se naziva terminus, završni vrh ili terminalna točka. Na primjer, putna mreža koja povezuje skup gradova koristeći jednosmjerne ceste može se predstaviti korištenjem neusmjerenog grafa. Gradovi se mogu predstaviti vrhovima na grafu, a usmjerene ivice predstavljaju puteve koji povezuju gradove s obzirom na smjer u kojem saobraćaj teče na putu.
Koja je razlika između usmjerenog i neusmjerenog grafa?
U usmjerenom grafu ivica je uređeni par, gdje uređeni par predstavlja smjer ivice koja povezuje dva vrha. S druge strane, u neusmjerenom grafu, ivica je neuređeni par, budući da nema smjera pridruženog rubu. Neusmjereni grafovi se mogu koristiti za predstavljanje simetričnih odnosa između objekata. In-degree i out-degree svakog čvora u neusmjerenom grafu su jednaki, ali to ne vrijedi za usmjereni graf. Kada koristite matricu za predstavljanje neusmjerenog grafa, matrica uvijek postaje simetričan graf, ali to nije istina za usmjerene grafove. Neusmjereni graf se može pretvoriti u usmjereni graf zamjenom svake ivice s dvije usmjerene ivice koje idu u suprotnom smjeru. Međutim, nije moguće pretvoriti usmjereni graf u neusmjereni graf.
