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

2024 Автор: Mildred Bawerman | [email protected]. Последнее изменение: 2023-12-16 08:42

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

Граф - это математическая структура, состоящая из множества вершин и ребер. Граф представляет собой набор объектов (представленных вершинами), которые связаны посредством некоторых связей (представленных ребрами). Используя математические обозначения, граф может быть представлен как 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 называется концом, завершающая вершина или конечная точка. Например, дорожная сеть, которая соединяет набор городов с помощью дорог с односторонним движением, может быть представлена с помощью неориентированного графа. Города могут быть представлены вершинами на графе, а направленные ребра представляют дороги, соединяющие города, с учетом направления движения транспорта на дороге.

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

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