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