Usmjereni vs neusmjereni grafikon
Graf je matematička struktura koja se sastoji od skupa vrhova i bridova. Grafikon predstavlja skup objekata (predstavljenih vrhovima) koji su povezani nekim vezama (predstavljeni rubovima). Koristeći matematičke zapise, graf se može predstaviti s G, gdje je G = (V, E) i V skup vrhova, a E skup bridova. U neusmjerenom grafu ne postoji smjer povezan s bridovima koji povezuju vrhove. U usmjerenom grafu postoji smjer povezan s bridovima koji povezuju vrhove.
Neusmjereni grafikon
Kao što je ranije spomenuto, neusmjereni graf je graf u kojem nema smjera na rubovima koji povezuju vrhove na grafu. Slika 1 prikazuje neusmjereni graf sa skupom vrhova V = {V1, V2, V3}. Skup rubova u gornjem grafikonu može se zapisati kao V = {(V1, V2), (V2, V3), (V1, V3)}. Također se može primijetiti da ništa ne sprječava zapisivanje skupa rubova kao V = {(V2, V1), (V3, V2), (V3, V1)} jer rubovi nemaju smjer. Stoga rubovi u neusmjerenom grafu nisu poredani parovi. To je glavna karakteristika neusmjerenog grafa. Neusmjereni grafovi mogu se koristiti za predstavljanje simetričnih odnosa između objekata koji su predstavljeni vrhovima. Na primjer, dvosmjerna cestovna mreža koja povezuje skup gradova može se predstaviti pomoću neusmjerenog grafa. Gradovi se mogu prikazati vrhovima na grafikonu, a rubovi predstavljaju dvosmjerne ceste koje povezuju gradove.
Usmjereni grafikon
Usmjereni graf je graf u kojem rubovi u grafu koji povezuju vrhove imaju smjer. Slika 2 prikazuje usmjereni graf sa skupom vrhova V = {V1, V2, V3}. Skup rubova u gornjem grafikonu može se zapisati kao V = {(V1, V2), (V2, V3), (V1, V3)}. Rubovi u neusmjerenom grafu su poredani 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 točka ruba e, a vrh y naziva se kraj, završni vrh ili završna točka. Na primjer, cestovna mreža koja povezuje skup gradova jednosmjernim cestama može se prikazati pomoću neusmjerenog grafa. Gradovi se mogu prikazati vrhovima na grafikonu, a usmjereni rubovi predstavljaju ceste koje povezuju gradove s obzirom na smjer kretanja prometa na cesti.
Koja je razlika između usmjerenog grafikona i neusmjerenog grafikona?
U usmjerenom grafu rub je uređeni par, gdje uređeni par predstavlja smjer brida koji povezuje dva vrha. S druge strane, u neusmjerenom grafu, rub je neuređeni par, jer nema smjera povezanog s rubom. Neusmjereni grafovi mogu se koristiti za prikaz simetričnih odnosa između objekata. Stupanj i stupanj svakog čvora u neusmjerenom grafu jednak je, ali to nije točno za usmjereni graf. Kada se matrica koristi za predstavljanje neusmjerenog grafa, matrica uvijek postaje simetrični graf, ali to ne vrijedi za usmjerene grafove. Neusmjereni graf može se pretvoriti u usmjereni graf zamjenom svakog ruba s dva usmjerena brida koja idu u suprotnom smjeru. Međutim, nije moguće pretvoriti usmjereni graf u neusmjereni graf.
