Różnica między wykreślonym i niekierowanym wykresem

Wykres skierowany a niekierowany

Wykres jest strukturą matematyczną złożoną z zestawu wierzchołków i krawędzi. Wykres przedstawia zestaw obiektów (reprezentowanych przez wierzchołki), które są połączone za pomocą niektórych łączy (reprezentowanych przez krawędzie). Za pomocą 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. Na niekierowanym wykresie nie ma żadnego kierunku związanego z krawędziami łączącymi wierzchołki. Na ukierunkowanym wykresie jest kierunek powiązany z krawędziami łączącymi wierzchołki.

Niekierowany wykres

Jak wspomniano wcześniej, niekierowany wykres jest wykresem, w którym nie ma kierunku na krawędziach łączących wierzchołki na wykresie. Ryc. 1 przedstawia niekierowany wykres z zestawem wierzchołków V = V1, V2, V3. Zestaw 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 niekierowanym wykresie nie są parami uporządkowanymi. Jest to główna cecha niekierowanego wykresu. Niekierowanych wykresów można użyć do przedstawienia symetrycznych relacji między obiektami reprezentowanymi przez wierzchołki. Na przykład dwukierunkowa sieć dróg łącząca zestaw miast może być reprezentowana za pomocą niekierowanego wykresu. Miasta mogą być reprezentowane przez wierzchołki na wykresie, a krawędzie reprezentują drogi dwukierunkowe łączące miasta.

Kierowany wykres

Wykres kierunkowy to wykres, w którym krawędzie na wykresie łączące wierzchołki mają kierunek. Ryc. 2 przedstawia ukierunkowany wykres z zestawem wierzchołków V = V1, V2, V3. Zestaw krawędzi na powyższym wykresie można zapisać jako V = (V1, V2), (V2, V3), (V1, V3). Krawędzie na niekierowanym wykresie są uporządkowane parami. Formalnie krawędź e na ukierunkowanym wykresie może być reprezentowana przez uporządkowaną parę e = (x, y), gdzie x jest wierzchołkiem, który nazywa się początkiem, źródłem lub początkowym punktem krawędzi e, a wierzchołek y nazywa się końcem , kończąc wierzchołek lub punkt końcowy. Na przykład sieć dróg, która łączy zbiór miast za pomocą dróg jednokierunkowych, można przedstawić za pomocą niekierowanego wykresu. 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 kierowanym a wykresem niekierowanym?

Na skierowanym wykresie krawędź jest uporządkowaną parą, gdzie uporządkowana para reprezentuje kierunek krawędzi, która łączy dwa wierzchołki. Z drugiej strony na niekierowanym wykresie krawędź jest parą nieuporządkowaną, ponieważ nie ma żadnego powiązanego kierunku z krawędzią. Niekierowanych wykresów można użyć do przedstawienia symetrycznych relacji między obiektami. Stopień i stopień każdego węzła na niekierowanym wykresie jest równy, ale nie jest to prawdą w przypadku wykresu skierowanego. Kiedy używasz macierzy do reprezentowania niekierowanego wykresu, macierz zawsze staje się grafem symetrycznym, ale nie jest to prawdą w przypadku wykresów ukierunkowanych. Niekierowany wykres można przekształcić w wykres skierowany, zastępując każdą krawędź dwiema skierowanymi krawędziami idącymi w przeciwnym kierunku. Nie można jednak przekonwertować grafu skierowanego na wykres niekierowany.