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

Граф с ориентированными ребрами

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

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

Определение

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

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

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

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

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

Подклассы

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

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

• Симметричные ориентированные графы — это ориентированные графы, в которых все ребра появляются дважды, по одному в каждом направлении (то есть для каждой стрелки, принадлежащей орграфу, соответствующая обратная стрелка также принадлежит ему). (Такое ребро иногда называют «двунаправленным», а такие графы иногда называют «двунаправленными», но это противоречит значению двунаправленных графов .)
• Простые ориентированные графы — это ориентированные графы, в которых нет петель (стрелок, которые напрямую соединяют вершины друг с другом) и множественных стрелок с одинаковыми исходными и целевыми узлами. Как уже говорилось, в случае нескольких стрелок к объекту обычно обращаются как к направленному мультиграфу . Некоторые авторы описывают орграфы с петлями как петлевые орграфы . ^[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 ^{F ( Q ),} где F ( Q ) — свободная категория на Q , состоящая из путей в Q , а FinVct _K — категория конечномерных векторных пространств над полем K. Представления колчана помечают его вершины векторными пространствами, а его ребра (и, следовательно, пути) совместимо с линейными преобразованиями между ними и преобразуются посредством естественных преобразований .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Бинарное отношение
• Граф Коутса
• Язык разметки направленных графов
• Блок-схема ДРАКОН
• Блок-схема
• Шаровидный набор
• Глоссарий теории графов
• Таблицы стилей графиков
• Теория графов
• График (абстрактный тип данных)
• Теория сетей
• Ориентация
• Предварительный заказ
• Топологическая сортировка
• Транспонировать график
• Граф вертикальных ограничений

Примечания

1. Банг-Дженсен и Гутин (2000). Банг-Дженсен и Гутин (2018), Глава 1. Дистель (2005), Раздел 1.10. Бонди и Мерти (1976), Раздел 10.
2. Чартран, Гэри (1977). Введение в теорию графов. Курьерская корпорация. ISBN 9780486247755. Архивировано из оригинала 4 февраля 2023 г. Проверено 2 октября 2020 г.
3. Bang-Jensen & Gutin (2018), Глава 7, Йео.
4. Bang-Jensen & Gutin (2018), Глава 2, авторы Bang-Jensen и Havet.
5. Bang-Jensen & Gutin (2018), Глава 8 Галеаны-Санчес и Эрнандес-Крус.
6. Дистель (2005), Раздел 1.10.
7. Банг-Дженсен и Гутин (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 г.).

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

• Банг-Йенсен, Йорген; Гутин, Грегори (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 узлами из Электронной энциклопедии целочисленных последовательностей

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