Ориентированный граф

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

Определение

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

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

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

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

Виды ориентированных графов

Подклассы

Симметричные ориентированные графы — это ориентированные графы, в которых все ребра появляются дважды, по одному в каждом направлении (то есть для каждой стрелки, принадлежащей орграфу, соответствующая обратная стрелка также принадлежит ему). (Такое ребро иногда называют «двунаправленным», а такие графы иногда называют «двунаправленными», но это противоречит значению двунаправленных графов .)
Простые ориентированные графы — это ориентированные графы, в которых нет петель (стрелок, которые напрямую соединяют вершины друг с другом) и множественных стрелок с одинаковыми исходными и целевыми узлами. Как уже говорилось, в случае нескольких стрелок к объекту обычно обращаются как к направленному мультиграфу . Некоторые авторы описывают орграфы с петлями как петлевые орграфы . ^[2]
- Полные ориентированные графы — это простые ориентированные графы, в которых каждая пара вершин соединена симметричной парой направленных дуг (это эквивалентно неориентированному полному графу, в котором ребра заменены парами обратных дуг). Отсюда следует, что полный орграф симметричен.
- Полуполные многодольные орграфы — это простые орграфы, в которых множество вершин разделено на множества так, что для каждой пары вершин x и y в разных наборах существует дуга между x и y . может быть одна дуга Между x и y или две дуги в противоположных направлениях. ^[3]
- Полуполные орграфы — это простые орграфы, в которых между каждой парой вершин есть дуга. Каждый полуполный орграф тривиально является полуполным многодольным орграфом, где каждая вершина представляет собой множество разбиения. ^[4]
- Квазитранзитивные орграфы — это простые орграфы, в которых для каждой тройки x , y , z различных вершин с дугами от x до y и от y до z существует дуга между x и z . может быть только одна дуга Между x и z или две дуги в противоположных направлениях. Полуполный орграф — это квазитранзитивный орграф. Существуют расширения квазитранзитивных орграфов, называемые k -квазитранзитивными орграфами. ^[5]
- Ориентированные графы — это ориентированные графы, не имеющие противоположных пар направленных ребер (т.е. не более одного из ( x , y ) и ( y , x ) может быть стрелками графа). Отсюда следует, что ориентированный граф является ориентированным тогда и только тогда, когда он не имеет 2-цикла . ^[6] (Это не единственное значение термина «ориентированный граф»; см. Ориентация (теория графов) .)
  - Турниры — это ориентированные графы, полученные выбором направления для каждого ребра в неориентированных полных графах . Турнир представляет собой полуполный диграф. ^[4]
  - Ориентированный граф является ациклическим, если он не имеет ориентированных циклов . Обычное название такого орграфа — ориентированный ациклический граф (DAG). ^[7]
    - Мультидеревья — это группы DAG, в которых нет двух различных направленных путей от одной и той же начальной вершины до одной и той же конечной вершины.
    - Ориентированные деревья или полидеревья — это DAG, образованные путем ориентации ребер деревьев (связных ациклических неориентированных графов).
      - Корневые деревья — это ориентированные деревья, у которых все ребра лежащего в основе неориентированного дерева направлены либо от корня, либо к нему (их называют соответственно древесными или out-деревьями и in-деревьями) .

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

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

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

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

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

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

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

Входящая и исходящая степень

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

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

Пусть G = ( V , E ) и v ∈ V . Входная степень v обозначается deg ⁻( v ) и его исходящая степень обозначается deg ⁺( v ).

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

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

\sum _{v\in V}\deg ^{-}(v)=\sum _{v\in V}\deg ^{+}(v)=|E|.

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

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

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

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

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

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

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

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

См. также

Примечания

^ Банг-Дженсен и Гутин (2000) . Банг-Дженсен и Гутин (2018) , Глава 1. Дистель (2005) , Раздел 1.10. Бонди и Мерти (1976) , Раздел 10.
^ Jump up to: ^а ^б ^с Чартранд, Гэри (1977). Введение в теорию графов . Курьерская корпорация. ISBN 9780486247755 . Архивировано из оригинала 4 февраля 2023 г. Проверено 2 октября 2020 г.
^ Bang-Jensen & Gutin (2018) , Глава 7, Йео.
^ Jump up to: ^а ^б Банг-Дженсен и Гутин (2018) , Глава 2, авторы: Банг-Дженсен и Хавет.
^ Bang-Jensen & Gutin (2018) , Глава 8, Галеана-Санчес и Эрнандес-Круз.
^ Дистель (2005) , Раздел 1.10.
^ Bang-Jensen & Gutin (2018) , Глава 3, Гутин.
^ Сатьянараяна, Бхаванари; Прасад, Кунчам Шьям, Дискретная математика и теория графов , PHI Learning Pvt. ООО, с. 460, ISBN 978-81-203-3842-5 ; Бруальди, Ричард А. (2006), Комбинаторные матричные классы , Энциклопедия математики и ее приложений, том. 108, Издательство Кембриджского университета, стр. 108. 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 ).
Банг-Йенсен, Йорген; Гутин, Григорий (2018), Классы ориентированных графов , Springer , ISBN 978-3319718408 .
Бонди, Джон Адриан ; Мурти, USR (1976), Теория графов с приложениями , Северная Голландия, ISBN 0-444-19451-7 .
Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 3-540-26182-6 (3-е электронное издание находится в свободном доступе на сайте автора).
Харари, Фрэнк ; Норман, Роберт З.; Картрайт, Дорвин (1965), Структурные модели: введение в теорию ориентированных графов , Нью-Йорк: Wiley .
Количество ориентированных графов (или ориентированных графов) с n узлами из Электронной энциклопедии целочисленных последовательностей

Внешние ссылки

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

[Chartrand-2] Jump up to: ^а ^б ^с Чартранд, Гэри (1977). Введение в теорию графов . Курьерская корпорация. ISBN 9780486247755 . Архивировано из оригинала 4 февраля 2023 г. Проверено 2 октября 2020 г.

[3] Bang-Jensen & Gutin (2018) , Глава 7, Йео.

[Bang-Jensen_2018-4] Jump up to: ^а ^б Банг-Дженсен и Гутин (2018) , Глава 2, авторы: Банг-Дженсен и Хавет.

[5] Bang-Jensen & Gutin (2018) , Глава 8, Галеана-Санчес и Эрнандес-Круз.

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

[7] Bang-Jensen & Gutin (2018) , Глава 3, Гутин.

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]