Różnica Między Wykresem Skierowanym I Nie Skierowanym

2024 Autor: Mildred Bawerman | [email protected]. Ostatnio zmodyfikowany: 2023-12-16 08:41

Wykres skierowany i nieukierunkowany

Graf jest matematyczną strukturą, która składa się z zestawu wierzchołków i krawędzi. Graf reprezentuje zbiór obiektów (reprezentowanych przez wierzchołki), które są połączone za pomocą pewnych łączy (reprezentowanych przez krawędzie). Korzystając z notacji matematycznych, wykres można przedstawić za pomocą G, gdzie G = (V, E), a V to zbiór wierzchołków, a E to zbiór krawędzi. W grafie niekierowanym nie ma kierunku związanego z krawędziami łączącymi wierzchołki. Na wykresie skierowanym istnieje kierunek powiązany z krawędziami łączącymi wierzchołki.

Niekierowany wykres

Jak wspomniano wcześniej, graf nieukierunkowany to graf, w którym nie ma kierunku w krawędziach łączących wierzchołki wykresu. Rysunek 1 przedstawia wykres nieukierunkowany 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, aby zapisać zestaw krawędzi jako V = {(V2, V1), (V3, V2), (V3, V1)}, ponieważ krawędzie nie mają kierunku. Dlatego krawędzie na wykresie nieukierunkowanym nie są parami uporządkowanymi. To jest główna cecha grafu niekierowanego. Grafów nieukierunkowanych można używać do reprezentowania symetrycznych relacji między obiektami reprezentowanymi przez wierzchołki. Na przykład dwukierunkową sieć drogową, która łączy zbiór miast, można przedstawić za pomocą niekierowanego wykresu. Miasta można przedstawić za pomocą wierzchołków na wykresie, a krawędzie reprezentują dwukierunkowe drogi łączące miasta.

Kierowany wykres

Graf skierowany to graf, w którym krawędzie wykresu łączące wierzchołki mają kierunek. Rysunek 2 przedstawia skierowany wykres 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 na wykresie nieukierunkowanym to uporządkowane pary. 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 początkowym punktem krawędzi e, a wierzchołek y nazywany jest końcem, kończący wierzchołek lub punkt końcowy. Na przykład sieć drogowa, która łączy zbiór miast za pomocą dróg jednokierunkowych, może być przedstawiona za pomocą niekierowanego wykresu. Miasta można przedstawić za pomocą wierzchołków 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 nie skierowanym?

W grafie skierowanym krawędź jest uporządkowaną parą, gdzie uporządkowana para reprezentuje kierunek krawędzi, która łączy dwa wierzchołki. Z drugiej strony w grafie niekierowanym krawędź jest nieuporządkowaną parą, ponieważ nie ma kierunku związanego z krawędzią. Grafów nieukierunkowanych można używać do reprezentowania symetrycznych relacji między obiektami. Stopień wejściowy i wyjściowy każdego węzła na grafie niekierowanym jest równy, ale nie dotyczy to grafu skierowanego. W przypadku używania macierzy do reprezentowania wykresu niekierowanego, macierz zawsze staje się wykresem symetrycznym, ale nie jest to prawdą w przypadku wykresów skierowanych. Graf nie skierowany można przekształcić w wykres skierowany, zastępując każdą krawędź dwoma skierowanymi krawędziami biegnącymi w przeciwnym kierunku. Jednak nie jest możliwe przekonwertowanie wykresu skierowanego na wykres nieukierunkowany.