Ориентированная двойственность и бесконтурные орграфы

Орграф D, обратный к данному орграфу D, имеет те же вершины, что и D, a дуга ии принадлежит D тогда и только тогда, когда дуга ии принадлежит D. Другими словами, орграф, обратный к орграфу D, получается изменением ориентации каждой дуги орграфа D.

Для любой теоремы об орграфах можно сформулировать соответствующую двойственную теорему, заменив каждое понятие на обратное к нему. Бесконтурным орграфом называется орграф, не содержащий контуров. Бесконтурный орграф содержит по крайней мере одну вершину с нулевой полустепенью исхода. В соответствии с обозначением D орграфа, обратного к D, будем также отмечать штрихами двойственные результаты. Бесконтурный орграф D содержит по крайней мере одну вершину с нулевой полустепенью захода. Ранее было указано, что конденсация любого орграфа есть бесконтурный орграф, а приведенные выше утверждения дают некоторую информацию о бесконтурных орграфах. Дадим теперь несколько характеризаций орграфов. Следующие свойства орграфа D эквивалентны: (1) D -- бесконтурный орграф; (2) D* изоморфен D; (3) каждый маршрут орграфа D есть путь; (4) вершины орграфа D можно упорядочить таким образом, что матрица смежностей" A (D) будет верхней треугольной матрицей. Особый интерес представляют два двойственных типа бесконтурных орграфов. Источником в орграфе! Выходящее дерево *)--* это орграф с источником, не имеющий полуконтуров; входящее дерево -- двойственный ему орграф. Слабый орграф является выходящим деревом тогда и только тогда, когда точно одна его вершина имеет нулевую полустепень захода, а у всех остальных вершин полустепень захода равна 1. Слабый орграф является входящим деревом тогда и только тогда, когда точно одна его вершина имеет нулевую полустепень исхода, а у всех остальных вершин полустепень исхода равна 1. В функциональном орграфе каждая вершина имеет полустепень исхода, равную 1; двойственный к нему орграф называется контрафункциональным орграфом.