Разница между направленным и неориентированным графом

Направленный против неориентированного графа

Граф - это математическая структура, состоящая из множества вершин и ребер. Граф представляет собой набор объектов (представленных вершинами), которые связаны через некоторые связи (представленные ребрами). Используя математические обозначения, граф можно представить как G, где G = (V, E), а V - множество вершин, а E - множество ребер. В неориентированном графе нет направления, связанного с ребрами, соединяющими вершины. В ориентированном графе есть направление, связанное с ребрами, соединяющими вершины.

Ненаправленный граф

Как упоминалось ранее, неориентированный граф - это граф, в котором нет ребер в ребрах, которые связывают вершины графа. На рисунке 1 изображен неориентированный граф с множеством вершин V = V1, V2, V3. Множество ребер в приведенном выше графике можно записать как V = (V1, V2), (V2, V3), (V1, V3). Также можно отметить, что ничто не мешает записать множество ребер как V = (V2, V1), (V3, V2), (V3, V1), поскольку ребра не имеют направления. Поэтому ребра в неориентированном графе не являются упорядоченными парами. Это главная характеристика неориентированного графа. Ненаправленные графы могут использоваться для представления симметричных отношений между объектами, которые представлены вершинами. Например, сеть дорог с двусторонним движением, которая соединяет множество городов, может быть представлена ​​с использованием неориентированного графика. Города могут быть представлены вершинами на графике, а края представляют собой дороги с двусторонним движением, которые соединяют города.

Направленный граф

Направленный граф - это граф, в котором ребра графа, связывающие вершины, имеют направление. На рисунке 2 изображен ориентированный граф с множеством вершин V = V1, V2, V3. Множество ребер в приведенном выше графике можно записать как V = (V1, V2), (V2, V3), (V1, V3). Края в неориентированном графе являются упорядоченными парами. Формально ребро e в ориентированном графе может быть представлено упорядоченной парой e = (x, y), где x - это вершина, которая называется началом, источником или начальной точкой ребра e, а вершина y называется концом , завершающая вершина или конечная точка. Например, дорожная сеть, которая соединяет множество городов с использованием односторонних дорог, может быть представлена ​​с использованием неориентированного графика. Города могут быть представлены вершинами на графике, а направленные ребра представляют собой дороги, которые соединяют города с учетом направления движения транспорта на дороге..

В чем разница между направленным графом и неориентированным графом?

В ориентированном графе ребро - это упорядоченная пара, где упорядоченная пара представляет направление ребра, связывающего две вершины. С другой стороны, в неориентированном графе ребро является неупорядоченной парой, поскольку нет направления, связанного с ребром. Ненаправленные графики могут использоваться для представления симметричных отношений между объектами. Степень входа и выхода каждого узла в неориентированном графе равна, но это не верно для ориентированного графа. При использовании матрицы для представления неориентированного графа матрица всегда становится симметричным графом, но это не так для ориентированных графов. Ненаправленный граф можно преобразовать в ориентированный граф, заменив каждое ребро двумя направленными ребрами, идущими в противоположном направлении. Однако невозможно преобразовать ориентированный граф в неориентированный граф.