Орграфы, теория и применение
Распознавание гамильтоновости орграфов и построение гамильтоновых контуров так же сложны, как и для неориентированных графов. Рассмотрим одно из достаточных условий гамильтоновости орграфа.
Теорема (Мейниэл, 1973). Пусть G – сильносвязный орграф порядка n>1 без петель и параллельных дуг. Если для любой пары v и w его несовпадающих несмежных вершин справедливо неравенство
delta(v)+delta(w)>=2*n-1,
то в G есть гамильтонов контур.
Пусть G=(V,E) – АЦИКЛИЧЕСКИЙ ОРГРАФ. Вершину v in V называют ЛИСТОМ, если delta+(v)=0. Если (v,w) in E, то v является НЕПОСРЕДСТВЕННЫМ ПРЕДКОМ w, а w – НЕПОСРЕДСТВЕННЫМ ПОТОМКОМ v. Если существует маршрут из v в w, то говорят, что v является ПРЕДКОМ w, а w – ПОТОМКОМ v. Эти понятия не имеют смысла для графов, имеющих циклы, так как в этом случае вершины в цикле являлись бы потомками и предками самих себя!
+Я------v1-----а+ v4
v2<-----------------v3----------->v5<---------v6
Из вершин v2, v4, v5 дуги не выходят (листья графа), v1 является предком v5, v5 является потомком v1 и прямым потомком v3 и т.д.
Существует тесная связь между ациклическими графами и частично упорядоченными отношениями. Частичные порядки будут основаны скорее на отношении <, чем на отношении <=, и, следовательно, являются нерефлексивными и транзитивными.
Утверждения:
а) Пусть G=(V,E) - а–иклический орграф и отношение < определяется следующим образом: v<w, если v является предком w. Тогда отношение < является частичным отношением порядка на V.
б) Пусть отношение < является частичным отношением порядка на конечном множестве V. Тогда, если E={(v,w): v<w}, то пара G=(V,E) является ациклическим графом.
ОРИЕНТИРОВАННОЕ ДЕРЕВО T=(V,E) - э–о ациклический орграф, в котором одна вершина vr in V не имеет предков и называется КОРНЕМ, а каждая другая вершина имеет ровно одного непосредственного предка. Корень соединяется с любой другой вершиной единственным маршрутом. БИНАРНОЕ ДЕРЕВО - э–о ориентированное дерево, в котором каждая вершина имеет не более двух непосредственных потомков, т.е. delta+(v)<=2 для всех v in V. Бинарное дерево является ПОЛНЫМ, если каждая вершина, не являющаяся листом дерева, имеет ровно 2 непосредственных потомка. Очевидно обобщение на k-арное дерево.
УРОВЕНЬ ВЕРШИНЫ - м–ксимальная длина маршрута от этой вершины до листа дерева.
ГЛУБИНА ВЕРШИНЫ - д–ина пути от корня до этой вершины.
ГЛУБИНА ОРДЕРЕВА - д–ина самого длинного пути в Т.
Утверждение. Для полного k-арного ордерева, в котором все l листьев имеют одинаковую глубину d, справедливо следующее:
l<=k^d; d=log(k) l.
Планарность
Плоский граф - г–аф с вершинами, расположенными на плоскости и непересекающимися ребрами. Планарный граф изоморфен плоскому. Всякий подграф планарного графа планарен. Задача о трех домах и трех колодцах. Провести от каждого из трех домов дорожки ко всем трем колодцам так, чтобы дорожки не пересекались. Граф этой задачи не является планарным. Грань графа - м–ожество всех точек плоскости, каждая пара которых может быть соединена жордановой кривой. Граница грани - м–ожество вершин и ребер, принадлежащих грани. Всякий плоский граф имеет одну, и притом единственную, неограниченную грань. Эта грань является внешней гранью графа, остальные - в–утренние.
Теорема Эйлера. Для всякого связного плоского графа n-m+f=2, где n - ч–сло вершин,m - ч–сло ребер, f - ч–сло граней. Подразбиение ребра - у–аление ребра и добавление двух новых, инцидентных вершинам удаленного ребра и соединенных между собой новой вершиной. Два графа называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его ребер.
Теорема Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 и K3,3. Деревья и лес. Дерево - с–язный граф без циклов. Лес (или ациклический граф) - н–ограф без циклов (может быть и несвязным).
Теорема. Для неографа G с n вершинами без петель следующие условия эквивалентны:
G - д–рево;
G - с–язный граф, содержащий n-1 ребро;
G - а–иклический граф, содержащий n-1 ребро;
Любые две несовпадающие вершины графа G соединяет единственная цепь.
G - а–иклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.
Остов (каркас) связного графа - д–рево, содержащее все вершины графа. Определяется неоднозначно. Редукция графа - о–тов с наибольшим числом ребер. Цикломатическое (или циклический ранг) число графа ν=m-n+c, где n - ч–сло вершин,m - ч–сло ребер, c - ч–сло компонент связности графа. Коциклический ранг (или коранг) ν*=n-c.
Теорема. Число ребер неографа, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно цикломатическому числу графа.
Неограф G является лесом тогда и только тогда, когда ν(G)=0. Неограф G имеет единственный цикл тогда и только тогда, когда ν(G)=1. Остов неографа имеет ν* ребер. Ребра графа, не входящие в остов, называются хордами. Цикл, получающийся при добавлении к остову графа его хорды, называется фундаментальным относительно этой хорды.
Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)- маршрут.
Теорема. Граф G=(V,E) связен тогда и только тогда, когда множество го вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы бе граничные точки каждого ребра находились в одном и том же множестве. Всякий максимальный связный подграф графа G называется связной компонентой (или компонентой) графа G. Слово "ма«симальный" о»начает максимальный относительно включения, т.е. не содержащийся в связном подграфе с большим числом элементов. Множество вершин связной компоненты называется областью связности. Для ориентированного графа вводится понятие ориентированного маршрута – это последовательность вида (1), в которой ei=(vi,vi+1). Аналогом цепи в этой итуации служить путь (ориентированная цепь). Аналогом цикла служит контур ориентированный цикл).
Орграф называется сильносвязным, если любые две его вершины достижимы руг из друга. Орграф называется одностороннесвязным, если для любой пары его вершин по меньшей мере одна достижима из другой. Орграф называется слабосвязным, если любые две вершины его основания соединены маршрутом. Орграф называется несвязным, если его основание несвязный псевдограф.
Теорема. Орграф является сильносвязным тогда и только тогда, когда в нем есть основной циклический маршрут.
Необходимость. Пусть G – сильносвязный орграф и T=(v0, x1, v1, ..., xn, v0) – его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G – сильносвязный орграф, то существуют маршруты T1=(v0, y1, ..., v), T2=(v, z1, ..., v0). Но тогда циклический маршрут T’=(v0, x1, v1, ..., xn, v0, y1, ..., v, z1, ..., v0) содержит большее число вершин, чем T, что противоречит выбору маршрута T. Следовательно, T – остовной маршрут.
Достаточность. Пусть u и v – две произвольные вершины орграфа G, а T=(v0, x, ..., v, y, ..., u, z, ..., v0) – циклический маршрут. Тогда u достижима из v с помощью маршрута (v, y, ..., u) – части маршрута T, – а v из u – с помощью маршрута (u, z, ..., v0, x, ..., v).3
Теорема. Орграф является одностороннесвязным тогда и только тогда, когда в нем есть остовной маршрут.
Теорема. Орграф является слабосвязным тогда и только тогда, когда в его основание есть связный псевдограф.
Сильносвязной компонентой орграфа называется его максимальный относительно включения сильносвязный подграф.
Матричное представление графов
Орграфы и матрицы. Матрицей сложностей A (D) орграфа D называется (рхр)-матрица \аи\> У которой ai}=, если vfl,— дуга орграфа D, и atj~Q в противном случае. Сумма по столбцу легко проверить, что суммы элементов по строкам матрицы A (D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам — полустепеням захода. Как и в случае графов, степени матрицы смежностей. А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую. Есть еще три матрицы, связанные с орграфом D — матрица достижимостей, матрица расстояний и матрица обходов. Матрицу достижимостей орграфа можно использовать для нахождения его сильных компонент. Формула для числа остовных входящих деревьев данного орграфа была найдена BOTTOM и Мейберри, а доказана Таттом. Чтобы сформулировать этот результат, известный как матричная теорема о деревьях для орграфов, введем еще матрицы, связанные с D. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента 1-й строки матрицы Mod равно числу остовных входящих деревьев, у которых вершина vt является стоком. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента j-го столбца матрицы Mid равно числу остовных выходящих деревьев, у которых вершина Vj является источником. Эйлеров контур в орграфе D — это замкнутый остовный маршрут, в котором каждая дуга орграфа D встречается по одному разу. Орграф называется эйлеровым, если в нем есть эйлеров контур. Для графов, можно легко показать, что слабый орграф D эйлеров тогда и только тогда, когда у каждой его вершины полустепень захода равна полустепени исхода. Сформулируем теперь теорему, в которой дается формула для числа эйлеровых контуров в эйлеровых орграфах. Эту теорему можно доказать очень изящно с помощью матричной теоремы о деревьях для орграфов; В эйлеровом орграфе число эйлеровых контуров равно с \ (d,-—1)! Заметим, что для эйлерова орграфа МоА=МА и все суммы и по строкам, и по столбцам равны нулю, так что все алгебраические дополнения равны между собой. Первый орграф с тремя вершинами называется транзитивной тройкой, второй — циклической тройкой.
Орграф называется строго слабым, если он слабый и не односторонний; строго односторонним, если он односторонний и не сильный. Пусть С0— класс всех несвязных орграфов, GI— класс всех строго слабых орграфов, С2— класс всех строго односторонних орграфов и Ся— класс всех сильных орграфов. Тогда максимум и минимум числа q дуг среди всех орграфов с р вершинами, относящихся по соединимости к категории С;, i=0, 1, 2, 3,. Орграф, являющийся декартовым произведением DjXZ^ двух орграфов, имеет VjX У2 в качестве множества вершин, и вершина («j, и2) смежна к вершине (уь у2) тогда и только тогда, когда или [ui=0i и u, adj гл2], или u. Если орграф D относительно соединимости находится в категории С„, то будем писать c(D)=n. Ни один строго слабый орграф не содержит вершину, удаление которой приводит к сильному орграфу.
Реберный орграф L(D) имеет множество всех дуг данного орграфа D в качестве множества вершин, и две его вершины х и у смежны тогда и только тогда, когда дуги х к у порождают маршрут в орграфе D. Выразить число вершин и число дуг орграфа L(D) через соответствующие величины орграфа D. Реберный орграф L (D) слабого орграфа D изоморфен самому орграфу D тогда и только тогда, когда D или D' — функциональный орграф. Если D — несвязный орграф, то утверждение, содержащееся в предыдущем упражнении, не верно. Пусть S и Т — непересекающиеся множества вершин орграфа D, а X (S, Т) — множество всех дуг, идущих из S в Т. Орграф D реберный тогда и только тогда, когда не существует множеств 5 и Т, имеющих по две вершины и таких, что Х (S,T)|=3. Число эйлеровых путей орграфа D равно числу гамильтоновых контуров реберного орграфа L(D]. Пусть орграф 7 состоит из одной вершины с двумя ориентированными петлями. Пусть T2=L(T1) — реберный орграф (здесь, если быть более точным, нужно использовать термин «псевдоорграф») орграфа Тг, определенный естественным образом; рекурсивно определяется Tn=L(Tn,l). (Такие орграфы Т„ известны под названием «телетайпных диаграмм».) Тогда число эйлеровых путей в орграфе Т„ равно 22""1-1. Каждый орграф, у которого id (v)^p/2, od (v)^p/2 для любой вершины v, гамильтонов.
Рассмотрим орграфы, у которых для любой вершины и сумма ^d(u, v) расстояний от этой вершины до всех остальных постоянна. Найти среди этих орграфов орграф, не являющийся вершинно-симметрическим. Орграф D, его дополнение D и обратный к нему D' имеют одну и ту же группу (автоморфизмов). Пусть А—матрица смежностей реберного орграфа полного симметрического орграфа.
Два орграфа называются коспектральными, если их матрицы смежностей имеют один и тот же характеристический многочлен. Существуют в точности три различных коспектральных сильных орграфа с четырьмя вершинами.
Орграф, называемый конъюнкцией D=Dl/D2 двух орграфов Z)j и D2, имеет в качестве множества вершин K=V1XV2, и вершина u=(u1, ы2) смежна к вершине v=(v-L,v2) тогда и только тогда, когда %adj г,^ в орграфе Dl и ы2 adj v.
Матрица смежностей А конъюнкции D=Dl/D2 есть тензорное произведение матриц смежностей орграфов D1 и D2. Пусть Dl и D2— два орграфа, a d,-— наибольший общий делитель длин всех простых контуров орграфа D,-, t=l,2. Конъюнкция DlfD^ является сильным орграфом тогда и только тогда, когда Ог и D2 — сильные орграфы, a d1 и d2 взаимно просты.
Орграф называется примитивным, если какая-нибудь степень его матрицы смежностей целиком состоит из положительных чисел. Орграф примитивен тогда и только тогда, когда длины его простых контуров имеют наибольший общий делитель, равный 1. Пусть D — примитивный орграф. Аналогично для вершин и и v орграфа из и в v. Исключение составляют (3,3)-орграф и (4,6)-орграф. П2, составленной Обершельпом , приведены числа орграфов с р вершинами, Эти числа вычислены с помощью соотношения (15. L(D) реберный орграф орграфа D.
ОРИЕНТИРОВАННЫЙ ГРАФ (ОРГРАФ) G есть пара G=(V,E), где V - к–нечное множество вершин, а E - п–оизвольное подмножество V*V – множество ориентированных (направленных) ребер (дуг). Предложения.
а) Ориентированный граф G=(V,E) определяет отношение на V.
б) Пусть V - к–нечное множество. Тогда отношение на V определяет ориентированный граф, у которого множество вершин - V–
Доказательство.
а) Как и в случае неориентированных графов, определим R(E) следующим образом: vR(E)w тогда и только тогда, когда (v,w) in E. Очевидно, что R(E) - о–ношение.
б) Если R - о–ношение на V, то ориентированный граф G=(V,E), определяемый R, имеет множество дуг Е, где (v,w) in E тогда и только тогда, когда vRw.
Направление дуги обозначают порядком в V*V; если (v,w) in E, то говорят, что дуга выходит из v и входит в w. На диаграмме в этом случае для указания направления используют стрелки.
Матрицу смежности A для орграфа определим следующим образом:
Aij=1, если дуга (vi,vj) in E, 0 в противном случае.
### Пусть G=({v1, v2, v3},{(v1,v2), (v2,v3), (v3,v1)}). Тогда матрица смежности и изображение орграфа имеют вид:
| /-------->+
1 1 1 +<---------v1<--------+ |
0 0 1 | | /
1 0 0 v2------------------->v3
Поскольку реберное отношение для орграфа не обязательно нерефлексивно или симметрично, то вообще говоря, не обязательно, чтобы А=А^T или Aii=0. Дуги типа (v,v) называют ПЕТЛЕЙ.
СТЕПЕНЬ ВЕРШИНЫ v in V, может быть записана в виде суммы
delta(v)=delta+(v)+delta-(v),
где delta+(v) - чис–о дуг, выходящих из v (полустепень исхода);
delta-(v) - чис–о дуг, входящих в v (полустепень захода);
Для орграфов справедливо утверждение:
Сумма полустепеней исхода всех вершин орграфа равна сумме полустепеней захода и равна числу его дуг:
SUM delta+(v)=SUM delta-(v)=|E|.
v in V v in V
Определим матрицу инцидентности I орграфа. Пусть G=(V,E) - орг–аф, |V|=n, |E|=m. Если перенумеровать некоторым образом дуги, то матрица инцидентности - бин–рная n*m матрица вида:
| 1, если вершина vk является началом дуги el;
Ikl=| -1, если вершина vk является концом дуги el;
| 0, если вершина vk и дуга el не инцидентны.
Орграфы изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга последовательностью одинаковых перестановок строк и столбцов.
Пусть G –помеченный граф порядка n, VG={1, 2, ... , n}. Определим бинарную nЧn- матрицу A=A(G), положив
1, {i, k } ∈ EG
Aik = .
0, {i, k } ∉ EG
A(G) называется матрицей смежности графа G. Это симметричная матрица с нулями на диагонали. Число единиц в строке равно степени соответствующей вершины. Очевидно, что соответствие G→A(G) определяет биекцию множества помеченных графов порядка n на множество бинарных симметричных nЧn- матриц с нулевой диагональю. Аналогично определяются матрицы смежности A мульти- и псевдографов: Aik равно числу ребер, соединяющих вершины i и k (при этом петля означает два ребра). Также определяется матрица смежности A(G) ориентированного графа.
Очевидно, что если A(G) – матрица смежности орграфа G порядка n, то
n n
∑ Aik = d + ( i ) , ∑A i =1
k =1 ik = d − (i ),
I.е. число единиц в i-й строке матрицы A(G) равно полустепени исхода i-й вершины, а число единиц в k-м столбце равно полустепени захода k-й вершины.
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одинаковыми перестановками строк и столбцов.
Теорема верна также для мультиграфов, псевдографов и орграфов.
Пусть G – (n, m)-граф, VG={1, 2, ... , n} EG={e1, e2, ... , em}. Определим бинарную nЧm- матрицу I=I(G) условиями
1, если вершина k и ребро ei инцидентны I ki =
0, если вершина k и ребро ei не инцидентны
Матрица I называется матрицей инцидентности графа G. В каждом её столбце ровно две единицы, равных столбцов нет. Как и выше, соответствие G→I(G) является биекцией множества помеченных (n, m)-графов с занумерованными ребрами на множество nЧm- матриц, удовлетворяющих описанным условиям.
Матрица инцидентности I для орграфа:
1 − если вершина k является началом дуги
I ki = −1 − если вершина k является концом дуги
0 − если вершины k и i не смежны
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга произвольными перестановками строк и столбцов.
Теорема верна также для мультиграфов, псевдографов и орграфов.
Свойства матриц смежности и инцидентности:
1) Сумма элементов матрицы A(G), где G=(V, E) – мультиграф, V={v1, v2, ..., vn}, по i-й строке (или по i-му столбцу) равна δ(vi).
2) Сумма элементов матрицы A(G), где G=(V, E) – ориентированный псевдограф,
V={v1, v2, ... , vn}, по i-й строке и по i-му столбцу соответственно равны δ+(vi), δ– (vi).
3) Пусть G – ориентированный мультиграф с непустым множеством дуг. Тогда:
а) сумма строк матрицы I(G) является нулевой строкой;
б) любая строка матрицы I(G) является линейной комбинацией остальных строк;
в) ранг матрицы I(G) не превосходит n–1;
г) для любого контура матрицы G сумма столбцов матрицы I(G), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.
4) Пусть G – мультиграф с непустым множеством ребер. Тогда при покоординатном сложении по модулю 2:
а) сумма строк матрицы I(G) является нулевой строкой;
б) любая строка матрицы I(G) является суммой остальных строк;
в) для любого цикла в G сумма столбцов матрицы I(G), соответствующих ребрам, входящим в этот цикл, равна нулевому столбцу.
Для того чтобы подсчитать все варианты, которые могли бы здесь возникнуть, заметим, что можно рассматривать или граф G, или ориентированный граф (орграф) D, в котором разделяются. Сеть N можно определить как граф или орграф, рассматриваемый вместе с функцией, приписывающей каждому ребру некоторое положительное действительное число. Если G — произвольный планарный (р, орграф и р^З, то а^Зр — 6. Ориентированный граф, или орграф, D состоит из конечного непустого множества V вершин и заданного набора X упорядоченных пар различных вершин.
Направленный граф — это орграф, не имеющий симметричных пар ориентированных ребер.
Матрица смежностей помеченного орграфа D определяется аналогично: Л =Л (D)—||а^-||, где а^=1, если дуга v{V] принадлежит D, и ац=0 в противном случае. Из определения матрицы A (D) следует, что матрицу смежностей данного графа можно также рассматривать как матрицу смежностей симметрического орграфа. Если D — орграф с линейными подграфами DI, » = 1, 2,. Любому графу G поставим в соответствие орграф D, в котором вершины vt и V) соединены дугами vtVj и VjVt только в том случае, если эти вершины смежны в G. Компоненты линейного подграфа графа G, являющиеся отдельными ребрами, взаимно однозначно соответствуют 2-контурам линейного подграфа орграфа D, а компоненты, являющиеся простыми циклами графа G, соответствуют двум простым контурам орграфа D.
Далее, каждой дуге орграфа D (F), скажем идущей из вершины fi в вершину fj, приписывается цвет, связанный с элементом /71// группы F. Чтобы построить граф G, группа (автоморфизмов) Г (G) которого изоморфна F, он заменяет каждую дугу fifj орграфа D (F). Для р^г 4 не существует таких орграфов D, чтоГ(/})==А^. Для орграфов нужно использовать редуцированную упорядоченную парную группу Sp2. По определению группа 5р2 действует на множестве V^ как индуцированная группой Sp: каждая подстановка а из Sp индуцирует такую подстановку а' из 5р2', что а' (i, /) = (ai, а/) для (г,/) из 1^4 Применяя теорему Пойа к цикловому индексу группы S[P2 получаем многочлен dp(x), в котором коэффициент при х9 равен числу орграфов с q ориентированными ребрами.
Свойства орграфов, которые отличают их от графов. Сформулировав принцип ориентированной двойственности, мы перейдем к изучению матриц, связанных с орграфами, и затем приведем аналог матричной теоремы о деревьях в графах.
Орграфы и соединимость
Орграф D состоит из конечного множества V вершин и набора упорядоченных пар различных вершин. В орграфе (ориентированным) маршрутом называется чередующаяся последовательность вершин и дуг v9, хг, uit. Средние вершины совпадают; основной маршрут содержит все вершины. Поскольку граф может быть либо связным, либо нет, то существуют три различных способа определения связности орграфа и каждый из них имеет свою собственную идиосинкразию). Ясно, что каждый сильный орграф — односторонний, а каждый односторонний орграф — слабый, но обратные утверждения не верны.
Орграф называется несвязным, если он даже не слабый. Заметим, что тривиальный орграф, состоящий только из одной вершины, является (по определению) сильным, поскольку в нем нет двух различных вершин. Сформулируем теперь необходимые и достаточные условия, обеспечивающие орграфу одну из этих трех типов соединимости. Орграф сильный тогда и только тогда, когда он имеет остовный замкнутый маршрут; односторонний тогда и только тогда, когда он имеет основной маршрут; слабый тогда и только тогда, когда он имеет основной полупуть. Для орграфа определены три типа компонент (связности). Сильной компонентой орграфа называется максимальный сильны л подграф, односторонней компонентой — максимальный односторонний подграф и слабой компонентой — максимальный слабый подграф. Это, в частности, демонстрирует способ построения по сильным компонентам орграфа D нового орграфа, который хотя и проще D, но сохраняет некоторые его структурные свойства. Конденсацией l) D* орграфа D называется орграф, множеством вершин которого служит множество {Si, 52,. , Sn} всех сильных компонент орграфа D, а дуга идет из St к Sj, если в орграфе D имеется по крайней мере одна дуга, идущая из некоторой вершины компоненты St к вершине компоненты Sj.
Орграф и его конденсация
Из максимальности сильных компонент следует, что в конденсации D* любого орграфа D нет контуров. Очевидно, что конденсация каждого сильного орграфа есть тривиальный орграф. Можно показать, что орграф является односторонним тогда и только тогда, когда его конденсация имеет единственный остовный путь.
Ориентированная двойственность и бесконтурные орграфы
Орграф D', обратный к данному орграфу D, имеет те же вершины, что и D, a дуга ии принадлежит D' тогда и только тогда, когда дуга ии принадлежит D. Другими словами, орграф, обратный к орграфу D, получается изменением ориентации каждой дуги орграфа D.
Для любой теоремы об орграфах можно сформулировать соответствующую двойственную теорему, заменив каждое понятие на обратное к нему. Бесконтурным орграфом называется орграф, не