stringtranslate.com

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

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

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

Определение

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

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

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

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

Подклассы

Простой направленный ациклический граф
Турнир на 4 вершинах

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

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

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

Дуга ( 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 ) и vV. Входящая степень v обозначается deg ( v ), а ее исходящая степень обозначается deg + ( v ).

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

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

Если для каждой вершины vV , 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. ^ abc Chartrand, Gary (1977). Введение в теорию графов. Courier Corporation. ISBN 9780486247755. Архивировано из оригинала 2023-02-04 . Получено 2020-10-02 .
  3. ^ Bang-Jensen & Gutin (2018), Глава 7, автор Йео.
  4. ^ ab 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, Cambridge University Press, стр. 51, ISBN 978-0-521-86565-4.
  9. ^ Bang-Jensen & Gutin (2000) стр. 19 в издании 2007 года; стр. 20 во 2-м издании (2009).

Ссылки

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