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

Простой ориентированный граф. Здесь двунаправленная стрелка обозначает два разных края, по одному для каждого направления.

В математике , а точнее в теории графов , ориентированный граф (или орграф ) - это граф , состоящий из набора вершин, соединенных ориентированными ребрами, часто называемыми дугами .

Определение

Формально ориентированный граф - это упорядоченная пара G = ( V , A ), где

  • V - это множество , элементы которого называются вершинами , узлами или точками ;
  • A - это набор упорядоченных пар вершин, называемых дугами , ориентированными ребрами (иногда просто ребрами с соответствующим набором с именем E вместо A ), стрелками или направленными линиями .

Он отличается от обычного или неориентированного графа тем , что последний определяется в терминах неупорядоченных пар вершин, которые обычно называют ребрами , связями или линиями .

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

Типы ориентированных графов

Подклассы

Простой ориентированный ациклический граф
Турнир на 4 вершины
  • Симметричные ориентированные графы - это ориентированные графы, в которых все ребра двунаправлены (то есть для каждой стрелки, принадлежащей орграфу, соответствующая обратная стрелка также принадлежит ему).
  • Простые ориентированные графы - это ориентированные графы, которые не имеют петель (стрелки, которые напрямую соединяют вершины друг с другом) и не имеют нескольких стрелок с одними и теми же исходными и целевыми узлами. Как уже было сказано, в случае нескольких стрелок объект обычно обращается как направленный мультиграф . Некоторые авторы описывают орграфы с петлями как петлевые орграфы .
    • Полные ориентированные графы - это простые ориентированные графы, в которых каждая пара вершин соединена симметричной парой направленных дуг (это эквивалентно неориентированному полному графу с ребрами, замененными парами обратных дуг). Отсюда следует, что полный орграф симметричен.
    • Полуполные многодолевые орграфы - это простые орграфы , в которых множество вершин разбивается на части, так что для каждой пары вершин x и y в разных наборах частей существует дуга между x и y . Обратите внимание, что между x и y может быть одна дуга или две дуги в противоположных направлениях.
    • Полуполные орграфы - это простые орграфы , в которых есть дуга между каждой парой вершин. Каждый полузаполненный орграф - это полузаполненный составной орграф, в котором количество вершин равно количеству долевых множеств.
    • Квазитранзитивные орграфы - это простые орграфы, в которых для каждой тройки x , y , z различных вершин с дугами от x до y и от y до z существует дуга между x и z . Обратите внимание, что между x и z может быть только одна дуга или две дуги в противоположных направлениях. Полуполный орграф - это квазитранзитивный орграф. Существуют расширения квазитранзитивных орграфов, которые называются k -квазитранзитивными орграфами.
    • Ориентированные графы - это ориентированные графы, не имеющие двунаправленных ребер (т.е. не более одного из ( x , y ) и ( y , x ) могут быть стрелками графа). Отсюда следует, что ориентированный граф является ориентированным тогда и только тогда, когда он не имеет двух циклов .
      • Турниры - это ориентированные графы, полученные путем выбора направления для каждого ребра в неориентированных полных графах . Обратите внимание, что турнир - это полузаполненный орграф.
      • Направленные ациклические графы (DAG) - это ориентированные графы без ориентированных циклов .
        • Мультидеревья - это группы доступности базы данных, в которых никакие два различных направленных пути из одной начальной вершины не пересекаются в одной конечной вершине.
        • Ориентированные деревья или многодеревья - это группы DAG, сформированные путем ориентирования ребер неориентированных ациклических графов.
          • Деревья с корнем - это ориентированные деревья, в которых все ребра лежащего в основе неориентированного дерева направлены либо от корня, либо к нему (они называются исходящими деревьями и внутренними деревьями , соответственно.

Орграфы с дополнительными свойствами

Основная терминология

Ориентированный граф с соответствующей матрицей инцидентности

Считается, что дуга ( x , y ) направлена от x к y ; y называется головой, а x - хвостом дуги; у называются быть прямым преемником из й и х называются быть прямым предшественником из г . Если в пути ведет от й к у , то у называются быть правопреемником по й и достижим из х , а х называются быть предшественником из г . Дуги ( у , х ) называется перевернутое дугу из ( х , у ) .

Матрица смежности из multidigraph с петлями является целочисленной матрицей с строками и столбцы , соответствующими вершины, где Недиагональный запись IJ является числом дуг из вершины я к вершине J , и диагональный элемент II является числом петель в вершине i . Матрица смежности ориентированного графа уникальна с точностью до идентичной перестановки строк и столбцов.

Другим матричным представлением ориентированного графа является его матрица инцидентности .

Смотрите направление для получения дополнительных определений.

Степень и степень

Ориентированный граф с помеченными вершинами (степень, степень)

Для вершины количество головных концов, смежных с вершиной, называется входом вершины, а количество хвостовых концов, смежных с вершиной, - ее исходной степенью (называемым фактором ветвления в деревьях).

Пусть G = ( V , A ) и vV . Степень v обозначается deg - ( v ), а ее внешняя степень обозначается deg + ( v ).

Вершина с deg - ( v ) = 0 называется источником , так как она является началом каждой из исходящих дуг. Точно так же вершина с deg + ( v ) = 0 называется стоком , так как это конец каждой из входящих в нее дуг.

Формула суммы степеней утверждает, что для ориентированного графа

Если для каждой вершины обV , град + ( v ) = град - ( v ) , то граф называется сбалансированным ориентированный граф .

Последовательность степеней

Последовательность степеней ориентированного графа - это список пар его ступеней и исходов; для приведенного выше примера у нас есть последовательность степеней ((2, 0), (2, 2), (0, 2), (1, 1)). Последовательность степеней является инвариантным ориентированным графом, поэтому изоморфные ориентированные графы имеют одинаковую последовательность степеней. Однако последовательность степеней, как правило, не однозначно идентифицирует ориентированный граф; в некоторых случаях неизоморфные орграфы имеют одинаковую последовательность степеней.

Задача реализации ориентированного графа - это проблема нахождения ориентированного графа с последовательностью степеней заданной последовательности пар положительных целых чисел . (Конечные пары нулей можно игнорировать, поскольку они тривиально реализуются путем добавления подходящего числа изолированных вершин к ориентированному графу.) Последовательность, которая является последовательностью степеней некоторого ориентированного графа, т. Е. Для которой задача реализации ориентированного графа имеет решение , называется направленной графической или направленной графической последовательностью. Эта проблема может быть решена либо алгоритмом Клейтмана – Ванга, либо теоремой Фулкерсона – Чена – Ансти .

Связность направленного графа

Ориентированный граф является слабо связным (или просто связным ), если неориентированный базовый граф, полученный заменой всех направленных ребер графа неориентированными ребрами, является связным графом .

Ориентированный граф является сильно связным или сильным, если он содержит ориентированный путь от x до y (и от y до x ) для каждой пары вершин ( x , y ) . В сильные компоненты являются максимальными сильно связные подграфы.

Связный корневой граф (или потоковый граф ) - это такой граф, в котором существует направленный путь к каждой вершине из выделенной корневой вершины .

Смотрите также

Заметки

Рекомендации