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

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

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

Определение [ править ]

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

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

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

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

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

Подклассы [ править ]

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

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

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

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

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

Основная терминология [ править ]

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

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

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

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

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

Indegree и outdegree [ править ]

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

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

Пусть 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 ) = град ^- ( v ) , то граф называется сбалансированным ориентированный граф . ^[4]

Последовательность степеней [ править ]

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

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

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

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

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

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

См. Также [ править ]

Викискладе есть медиафайлы, связанные с направленными графами .

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

Заметки [ править ]

Перейти ↑ Bang-Jensen & Gutin (2000) . Diestel (2005) , Раздел 1.10. Бонди и Мурти (1976) , Раздел 10.
^ a b c Чартранд, Гэри (1977). Вводная теория графов . Курьерская корпорация. ISBN 9780486247755.
^ Diestel (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.
↑ 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 ).
Бонди, Джон Адриан ; Мурти, USR (1976), Теория графов с приложениями , Северная Голландия, ISBN 0-444-19451-7.
Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer , ISBN 3-540-26182-6 (электронное 3-е издание находится в свободном доступе на сайте автора).
Харари, Фрэнк ; Норман, Роберт З .; Картрайт, Дорвин (1965), Структурные модели: Введение в теорию ориентированных графов , Нью-Йорк: Wiley.
Количество ориентированных графов (или ориентированных графов) с n узлами из Он-лайн энциклопедии целочисленных последовательностей

[1] Перейти ↑ Bang-Jensen & Gutin (2000) . Diestel (2005) , Раздел 1.10. Бонди и Мурти (1976) , Раздел 10.

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

[3] Diestel (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] Bang-Jensen & Gutin (2000), стр. 19 в издании 2007 г .; п. 20 во 2-м издании (2009 г.).

[1]