§ 8.6. Изменение ориентации

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

Лемма а. Любой непустой ацикличный колчан обладает источниками и стоками.

Доказательство. Предположим, что не имеет источников. Рассмотрим произвольную вершину (существующую ввиду того, что По предположению не является источником, так что существует вершина такая, что При этом, ввиду ацикличности имеем Вершина также не является источником, и поэтому найдется со свойством Если или то содержит цикл. Следовательно, Повторяя эту процедуру раз, мы, очевидно, придем к противоречию. Таким образом, в существуют источники. Доказательство существования стоков аналогично.

Следствие. Если ацикличный колчан, то его вершины можно заиндексировать элементами множества таким образом, что из следует

Доказательство. Проведем индукцию по Если то и доказывать нечего. Предположим, что и что утверждение следствия справедливо для всех колчанов с числом вершин Пусть V — множество источников в По лемме а так что По предположению индукции существует индексация множества вершин колчана такая, что для имеем Заиндексируем вершины из V элементами множества произвольным образом. Если то не является стоком. Поэтому так что если то если же то

Колчан будем называть калиброванным (standardized), если для всех пар Согласно предыдущему следствию, любой ацикличный колчан может быть калиброван, причем обычно многими способами. Отметим, что если калиброван, то 1 является источником, стоком в

Для любой вершины колчана положим где

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

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

Лемма b. Пусть калиброванный колчан на вершинах. Тогда выполняются следующие утверждения:

(i) если то является стоком, источником в колчане ;

(ii) если то является источником, стоком в колчане

Доказательство. Эти утверждения вытекают из предположения о том, что калиброван, и следующего замечания: если различные вершины колчана то том и только том случае, если реализуется одна из двух возможностей: 1) и вершины либо одновременно входят, либо не входят в множество и в точности одна из вершин входит в

Предложение. Пусть ацикличные колчаны, удовлетворяющие условию Тогда существует последовательность вершин колчана такая, что для вершина является источником в

Доказательство. Предположение о том, что означает, что причем тогда и только тогда, когда либо либо Достаточно доказать предложение для того частного случая, когда имеется в точности одно ребро со свойством т. е. Применяя этот результат несколько раз, мы получим утверждение предложения в полной общности. Положим Если записать в виде несвязного объединения связных компонент, то должны принадлежать разным компонентам. В противном случае можно было бы соединить путем в который вместе с ребром дал бы цикл в что противоречит ацикличности последнего. Таким образом, где Тогда Согласно следствию, можно предполагать, что и колчан калиброван. Пусть Если то в том и только том случае, если По лемме вершина является источником в Ввиду того что вершина является источником в

Упражнения

(см. скан)