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

Орграф D', обратный к данному орграфу D, имеет те же вершины, что и D, а дуга uv принадлежит D' тогда и только тогда, когда дуга vu принадлежит D. Другими словами, орграф, обратный к орграфу D, получается изменением ориентации каждой дуги орграфа D. Мы уже сталкивались с другими «обратными» понятиями, такими, как полустепень захода и полустепень исхода. Относительно ориентации все эти понятия связаны между собой довольно мощным принципом. Этот принцип представляет собой классический результат в теории бинарных отношений.

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

Проиллюстрируем теперь, как этот принцип порождает новые результаты. Бесконтурным орграфом называется орграф, не содержащий контуров.

Теорема. Бесконтурный орграф содержит, по крайней мере одну вершину с нулевой полустепенью исхода.

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

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

Теорема. Бесконтурный орграф D содержит, по крайней мере одну вершину с нулевой полустепенью захода.

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

Теорема. Следующие свойства орграфа D эквивалентны:

(1) D - бесконтурный орграф;

(2) D* изоморфен D;

(3) каждый маршрут орграфа D есть путь;

(4) вершины орграфа D можно упорядочить таким образом, что матрица смежностей A (D) будет верхней треугольной матрицей.

Особый интерес представляют два двойственных типа бесконтурных орграфов. Источником в орграфе D называется вершина, из которой можно достичь все другие вершины орграфа; сток определяется двойственным образом. Выходящее дерево - это орграф с источником, не имеющий полуконтуров; входящее дерево - двойственный ему орграф

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

Теорема. Слабый орграф является входящим деревом тогда и только тогда, когда точно одна его вершина имеет нулевую полустепень исхода, а у всех остальных вершин полустепень исхода равна 1.

Рассмотрим теперь некоторые орграфы, тесно связанные с определенными выше. В функциональном орграфе каждая вершина имеет полустепень исхода, равную 1; двойственный к нему орграф называется контрафунщиональным орграфом. В следующей теореме и двойственной к ней дается характеризация структуры этих орграфов.

Теорема. Для слабого орграфа D следующие утверждения эквивалентны:

(1) D — функциональный орграф;

(2) в D точно один такой контур, что удаление его дуг приводит к. орграфу, в котором каждая слабая компонента является входящим деревом;

(3) в D точно один такой контур, что удаление любой его дуги приводит к образованию входящего дерева.

Минимальный набор вершин, из которого достижимы все вершины орграфа D, называется вершинной базой орграфа. Таким образом, множество S вершин орграфа D является вершинной базой тогда и только тогда, когда каждая вершина орграфа D достижима из некоторой вершины множества S и ни одна из вершин множества S не достижима из любой другой вершины этого множества.

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

Следствие (а). Любая вершинная база орграфа D содержит точно одну вершину из каждой сильной компоненты орграфа D, принадлежащей вершинной базе конденсации D* орграфа D.

1-базой называется минимальный набор S таких попарно несмежных вершин, что любая вершина орграфа D или принадлежит S, или смежна из некоторой вершины множества S. Каждый орграф имеет вершинную базу, но не каждый имеет 1-базу. Например, ни один из контуров нечетной длины не имеет 1-базы. Критерий существования 1-базы у произвольного орграфа еще не найден. В теореме Ричардсона обобщается следствие (а), полученное фон Нейманом и Моргенштерном при исследовании ими теории игр.

Теорема. Каждый орграф, не содержащий контуров нечетной длины, имеет 1-базу.

Следствие (а). Каждый бесконтурный орграф имеет 1-базу.