В математике , а точнее в теории графов , ориентированный граф (или орграф ) — это граф , состоящий из набора вершин , соединенных направленными ребрами , часто называемыми дугами .
Определение
Формально ориентированный граф — это упорядоченная пара G = ( V , A ) , где [1]
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-деревья, в которых нет двух различных направленных путей из одной и той же начальной вершины в одну и ту же конечную вершину.
Ориентированные деревья или полидеревья — это DAG-графы, образованные путем ориентирования ребер деревьев (связных, ациклических неориентированных графов).
Корневые деревья — это ориентированные деревья, в которых все ребра базового неориентированного дерева направлены либо от корня, либо к нему (они называются, соответственно, древовидными деревьями или внешними деревьями и внутренними деревьями) .
Орграфы с дополнительными свойствами
Взвешенные ориентированные графы (также известные как направленные сети ) — это (простые) направленные графы с весами, назначенными их стрелкам, аналогично взвешенным графам (которые также известны как ненаправленные сети или взвешенные сети ). [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 , E ) и v ∈ V. Входящая степень v обозначается deg − ( v ), а ее исходящая степень обозначается deg + ( v ).
Вершина с deg − ( v ) = 0 называется источником , так как она является началом каждой из своих исходящих дуг. Аналогично, вершина с deg + ( v ) = 0 называется стоком , так как она является концом каждой из своих входящих дуг.
Формула суммы степеней утверждает, что для ориентированного графа
Если для каждой вершины v ∈ V , deg + ( v ) = deg − ( 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.
^ abc Chartrand, Gary (1977). Введение в теорию графов. Courier Corporation. ISBN 9780486247755. Архивировано из оригинала 2023-02-04 . Получено 2020-10-02 .
^ Bang-Jensen & Gutin (2018), Глава 7, автор Йео.
^ ab Bang-Jensen & Gutin (2018), Глава 2, авторы Bang-Jensen и Havet.
^ Bang-Jensen & Gutin (2018), Глава 8 Галеаны-Санчес и Эрнандес-Круса.
^ Дистель (2005), Раздел 1.10.
^ Банг-Дженсен и Гутин (2018), Глава 3 Гутина.
^ Сатьянараяна, Бхаванари; Прасад, Кунчам Шьям, Дискретная математика и теория графов , PHI Learning Pvt. ООО, с. 460, ISBN978-81-203-3842-5; Бруальди, Ричард А. (2006), Комбинаторные матричные классы, Энциклопедия математики и ее приложений, т. 108, Cambridge University Press, стр. 51, ISBN 978-0-521-86565-4.
^ Bang-Jensen & Gutin (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.
Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 3-540-26182-6(электронное 3-е издание находится в свободном доступе на сайте автора).
Харари, Фрэнк ; Норман, Роберт З.; Картрайт, Дорвин (1965), Структурные модели: Введение в теорию направленных графов , Нью-Йорк: Wiley.
