Wykres ukierunkowany i nieukierunkowany
Wykres to struktura matematyczna składająca się z zestawu wierzchołków i krawędzi. Wykres reprezentuje zbiór obiektów (reprezentowanych przez wierzchołki), które są połączone pewnymi połączeniami (reprezentowanymi przez krawędzie). Korzystając z notacji matematycznych, wykres można przedstawić za pomocą G, gdzie G=(V, E) i V to zbiór wierzchołków, a E to zbiór krawędzi. W grafie nieskierowanym nie ma kierunku związanego z krawędziami łączącymi wierzchołki. W grafie skierowanym istnieje kierunek powiązany z krawędziami łączącymi wierzchołki.
Wykres nieskierowany
Jak wspomniano wcześniej, graf nieskierowany to graf, w którym krawędzie łączące wierzchołki grafu nie mają kierunku. Rysunek 1 przedstawia graf nieskierowany ze zbiorem wierzchołków V={V1, V2, V3}. Zbiór krawędzi na powyższym wykresie można zapisać jako V={(V1, V2), (V2, V3), (V1, V3)}. Można również zauważyć, że nic nie stoi na przeszkodzie zapisaniu zbioru krawędzi jako V={(V2, V1), (V3, V2), (V3, V1)}, ponieważ krawędzie nie mają kierunku. Dlatego krawędzie w grafie nieskierowanym nie są parami uporządkowanymi. Jest to główna cecha grafu nieskierowanego. Grafów nieskierowanych można używać do przedstawiania symetrycznych relacji między obiektami reprezentowanymi przez wierzchołki. Na przykład dwukierunkową sieć dróg łączącą zbiór miast można przedstawić za pomocą wykresu nieskierowanego. Miasta mogą być reprezentowane przez wierzchołki na wykresie, a krawędzie reprezentują drogi dwukierunkowe łączące miasta.
Wykres ukierunkowany
Wykres skierowany to graf, w którym krawędzie grafu łączące wierzchołki mają kierunek. Rysunek 2 przedstawia graf skierowany ze zbiorem wierzchołków V={V1, V2, V3}. Zbiór krawędzi na powyższym wykresie można zapisać jako V={(V1, V2), (V2, V3), (V1, V3)}. Krawędzie w grafie nieskierowanym są parami uporządkowanymi. Formalnie krawędź e w grafie skierowanym może być reprezentowana przez uporządkowaną parę e=(x, y) gdzie x jest wierzchołkiem nazywanym początkiem, źródłem lub punktem początkowym krawędzi e, a wierzchołek y nazywany jest końcem, kończący wierzchołek lub punkt końcowy. Na przykład sieć drogową łączącą zbiór miast za pomocą dróg jednokierunkowych można przedstawić za pomocą wykresu nieskierowanego. Miasta mogą być reprezentowane przez wierzchołki na wykresie, a skierowane krawędzie reprezentują drogi łączące miasta, biorąc pod uwagę kierunek ruchu na drodze.
Jaka jest różnica między wykresem skierowanym a wykresem nieskierowanym?
W grafie skierowanym krawędź jest parą uporządkowaną, gdzie para uporządkowana reprezentuje kierunek krawędzi łączącej dwa wierzchołki. Z drugiej strony, w grafie nieskierowanym krawędź jest parą nieuporządkowaną, ponieważ nie ma kierunku związanego z krawędzią. Wykresy nieskierowane mogą służyć do reprezentowania symetrycznych relacji między obiektami. Stopień wejściowy i stopień wyjściowy każdego węzła w grafie nieskierowanym jest równy, ale nie jest to prawdą w przypadku grafu skierowanego. Kiedy używamy macierzy do reprezentowania grafu nieskierowanego, macierz zawsze staje się grafem symetrycznym, ale nie jest to prawdą w przypadku grafów skierowanych. Graf nieskierowany można przekształcić w graf skierowany, zastępując każdą krawędź dwiema krawędziami skierowanymi w przeciwnych kierunkach. Nie jest jednak możliwe przekształcenie grafu skierowanego w graf nieskierowany.
