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

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

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

Определение

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

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

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

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

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

Подклассы

Простой ориентированный ациклический граф

Турнир на 4 вершины

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

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

Взвешенные ориентированные графы (также известен как направленные сети) являются (простыми) ориентированными графами с веса назначены их стрелкам, аналогично взвешенные графики (которые также известны как ненаправленные сети или взвешенные сети ).^[2]
- Поточные сети взвешенные ориентированные графы, в которых выделены два узла, источник и тонуть.
Корневые ориентированные графы (также известен как графы потока) - орграфы, в которых вершина выделена как корневая.
- Графики потока управления это корневые орграфы, используемые в информатике как представление путей, по которым программа может пройти во время ее выполнения.
Графики потока сигналов являются ориентированными графами, в которых узлы представляют системные переменные, а ветви (ребра, дуги или стрелки) представляют функциональные связи между парами узлов.
Графики потока являются орграфами, связанными с набором линейных алгебраических или дифференциальных уравнений.
Диаграммы состояний находятся направленные мультиграфы которые представляют конечные автоматы.
Коммутативные диаграммы диграфы используются в теория категорий, где вершины представляют (математические) объекты, а стрелки представляют морфизмы, с тем свойством, что все направленные пути с одинаковыми начальной и конечной точками приводят к одному и тому же результату по композиции.
В теории Группы Ли, а колчан Q ориентированный граф, служащий областью определения и, таким образом, характеризующий форму представление V определяется как функтор, в частности, объект категория функторов FinVct_K^F(Q) где F(Q) это свободная категория на Q состоящий из путей в Q и FinVct_K категория конечномерных векторные пространства через поле K. Представления колчана помечают его вершины векторными пространствами, а его ребра (и, следовательно, пути) совместимы с линейные преобразования между ними и преобразовать через естественные преобразования.

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

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

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

В матрица смежности мультииграфа с петлями - целочисленный матрица со строками и столбцами, соответствующими вершинам, где недиагональная запись а_ij это количество стрелок из вершины я к вершине j, а диагональный вход а_ii количество петель в вершине я. Матрица смежности ориентированного графа уникальна с точностью до идентичной перестановки строк и столбцов.

Еще одно матричное представление ориентированного графа - это его матрица инцидентности.

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

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

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

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

Позволять г = (V, А) и v ∈ V. Степень v обозначается deg⁻(v), а его выходная степень обозначается deg⁺(v).

Вершина с град⁻(v) = 0 называется источник, так как это начало каждой из его исходящих стрел. Аналогично вершина с град⁺(v) = 0 называется тонуть, поскольку это конец каждой из входящих в него стрелок.

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

{displaystyle sum _ {vin V} deg ^ {-} (v) = sum _ {vin V} deg ^ {+} (v) = | A |.}

Если для каждой вершины v ∈ V, град⁺(v) = град⁻(v), граф называется сбалансированный ориентированный граф.^[4]

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

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

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

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

Ориентированный граф - это слабо связанный (или просто связанный^[5]) если неориентированный нижележащий граф полученный заменой всех направленных ребер графа неориентированными ребрами, является связный граф. Ориентированный граф - это сильно связанный или сильный если он содержит направленный путь от Икс к y и направленный путь от y к Икс для каждой пары вершин {Икс, y}. В сильные компоненты - максимальные сильно связные подграфы.

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

Заметки

^ Банг-Дженсен и Гутин (2000). Дистель (2005), Раздел 1.10. Бонди и Мёрти (1976), Раздел 10.
^ ^а ^б ^c Чартран, Гэри (1977). Вводная теория графов. Курьерская корпорация. ISBN 9780486247755.
^ Дистель (2005), Раздел 1.10.
^ Сатьянараяна, Бхаванари; Прасад, Кунчам Шьям, Дискретная математика и теория графов, PHI Learning Pvt. Ltd., п. 460, г. ISBN 978-81-203-3842-5; Бруальди, Ричард А. (2006), Комбинаторные матричные классы, Энциклопедия математики и ее приложений, 108, Cambridge University Press, стр.51, ISBN 978-0-521-86565-4.
^ Банг-Дженсен и Гутин (2000) п. 19 в издании 2007 г .; п. 20 во 2-м издании (2009 г.).

использованная литература

Банг-Йенсен, Йорген; Гутин, Григорий (2000), Орграфы: теория, алгоритмы и приложения, Springer, ISBN 1-85233-268-9
(исправленное 1-е издание 2007 г. теперь находится в свободном доступе на сайте авторов; 2-е издание появилось в 2009 г. ISBN 1-84800-997-6).
Бонди, Джон Адриан; Мурти, США. (1976), Теория графов с приложениями, Северная Голландия, ISBN 0-444-19451-7.
Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer, ISBN 3-540-26182-6 (электронное 3-е издание находится в свободном доступе на сайте автора).
Харари, Фрэнк; Норман, Роберт З .; Картрайт, Дорвин (1965), Структурные модели: введение в теорию ориентированных графов, Нью-Йорк: Wiley.
Количество ориентированных графов (или ориентированных графов) с n узлами от Он-лайн энциклопедия целочисленных последовательностей

[1] Банг-Дженсен и Гутин (2000). Дистель (2005), Раздел 1.10. Бонди и Мёрти (1976), Раздел 10.

[Chartrand-2] а ^б ^c Чартран, Гэри (1977). Вводная теория графов. Курьерская корпорация. ISBN 9780486247755.

[3] Дистель (2005), Раздел 1.10.

[4] Сатьянараяна, Бхаванари; Прасад, Кунчам Шьям, Дискретная математика и теория графов, PHI Learning Pvt. Ltd., п. 460, г. ISBN 978-81-203-3842-5; Бруальди, Ричард А. (2006), Комбинаторные матричные классы, Энциклопедия математики и ее приложений, 108, Cambridge University Press, стр.51, ISBN 978-0-521-86565-4.

[5] Банг-Дженсен и Гутин (2000) п. 19 в издании 2007 г .; п. 20 во 2-м издании (2009 г.).

[1]

[2]

[3]

[4]

[5]