так как 1/„ = Vq- Значит, ориентированное дерево является свободным деревом, если не учитывать направления дуг.

Следует отметить, что этот процесс можно обратить. Если начать с такого непустого свободного дерева, как на рис. 30, то можно в качестве корня R выбрать любую вершину и задать направления для ребер. Если представить себе, что граф "подвесили" за вершину R и встряхнули, то стрелки ребер в нем будут направлены вверх. Более строгая формулировка выглядит так.

Заменить ребро V - V дугой от V к V тогда и только тогда, когда простой путь от V к R проходит через V, т. е. когда он имеет вид (Vq, к,..., V„), где n>0,Vo = V,Vi= V, Vn = R.

Для проверки справедливости этого построения нужно доказать, что для каждого ребра V - V указано направление V <- V (или V V). И это действительно легко сделать, если {V, Vi,... ,R) и {V, V,... ,R) являются простыми путями, т. е. цикл существует всегда, за исключением случаев, когда V = V{ или = V. Такое построение демонстрирует, что направления дуг в ориентированном дереве полностью определяются расположением корня, а потому их можно не урсазывать на схемах, на которых корень обозначен явным образом.

Таким образом, установлена связь между тремя типами деревьев: (упорядоченным) деревом, которое имеет принципиапьное значение в компьютерных программах, как показано в начале раздела 2.3, ориентированным (или неупорядоченным) и свободным деревом. Два последних типа деревьев также встречаются при изучении компьютерных алгоритмов, но не так часто, как первый. Основное различие между этими типами древовидных структур заключается только в объеме структурной информации, которая считается существенной. Например, на рис. 35 показаны три дерева, которые различны, только если рассматривать их как упорядоченные деревья (с корнем вверху). А если их рассматривать как ориентированные деревья, то идентичными являются первые два, поскольку порядок поддеревьев "слева направо" здесь не существен. Наконец, если считать деревья свободными, то все они на рис. 35 идентичны, так как корень не определен.

д* д* bh *д *Л

Рис. 35. Три древовидные структуры.

Цепью Эйлера {Eulerian circuit) в ориентированном графе является такой ориентированный путь (61,62, ,ет), что каждая дуга ориентированного графа встречается в этом пути только один раз и fin(em) = init(ei). Она представляет собой "полный обход" дуг диграфа. (Цепь Эйлера названа в честь Леонарда Эйлера (Leonhard Euler), который в 1736 году рассмотрел знаменитую задачу о том, что

невозможно обойти во время воскресной прогулки семь мостов Кенигсберга, посетив каждый из них в точности один раз. Он также рассмотрел аналогичную задачу для неориентированных графов. Цепи Эйлера не следзет путать с цепями Гамильтона (Hamiltonian circuits), т. е. ориентированными циклами, в которых каждая вершина встречается только один раз; см. гл. 7.)

Ориентированный граф называется сбалансированным (balanced) (рис. 36), если каждая вершина V имеет равные по величине степени входа и выхода, т. е. сколько существует ребер, для которых вершина V является начальной, столько же существует ребер, для которых вершина V является конечной. Это условие тесно связано с законом Кирхгофа (см. упр. 24). Если ориентированный граф имеет цепь Эйлера, то очевидно, что он должен быть связным и сбалансированным, за исключением случаев, когда он имеет изолированные вершины (isolated vertices), т. е. вершины с равными нулю степенями входа и выхода.

Рис. 36. Сбалансированный ориентированный граф.

Итак, в настоящем разделе дано довольно много определений (ориентированный граф, дуга, начальная вершина, конечная вершина, степень выхода, степень входа, ориентированный путь, простой ориентированный путь, ориентированный цикл, ориентированное дерево, цепь Эйлера, изолированная вершина, а также строгая связность, наличие корня и сбалансированность), но приведено лишь несколько связанных с ними результатов. Теперь мы готовы приступить к изучению более сложного материала. Первым основным результатом является теорема И. Дж. Гуда [I. J. Good, J. London Math. Soc. 21 (1947), 167-169], который показал, что цепи Эйлера существуют всегда, кроме случаев, когда они очевидно невозможны.

Теорема G. Конечный ориентированный граф без изолированных вершин содержит цепь Эйлера тогда и только тогда, когда он связанный и сбалансированный.

Доказательство. Предположим, что граф G сбалансирован и

Р = (ei,...,em)

представляет собой ориентированный путь максимально возможной длины, в котором ни одна дуга не проходится дважды. Тогда, если V = fin(e,„) и если к - степень выхода вершины V, то путь Р должен включать все к дуг е с начальной вершиной init(e) = V. В противном случае можно было бы добавить е и получить более длинный путь. Но если init(ej) = V и j > 1, то fin(ej i) = V. Следовательно, так как граф G сбалансирован, получим

init(ei) = V = fin(em); в противном случае степень входа вершины V должна быть не меньше к + 1.

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

Между цепями Эйлера и ориентированными деревьями существует следующая важная взаимосвязь.

Лемма Е. Пусть цепь Эйлера (ei,...,em) ориентированного графа G не имеет изолированных вершин и пусть R = Ап(е„г) = init(ei). Пусть для каждой вершины V ф R ребро e[V] является последним выходом нз V в этой цепи, т. е.

e[V]=ej, если init(ej) = V, и тИ{ек)фУ для j < к < т. (1)

Тогда вершины графа G с дугами e[V] образуют ориентированное дерево с корнем R.

Доказательство. Свойства (а) и (Ь) определения ориентированного дерева, очевидно, удовлетворяются. Согласно результату упр. 7 достаточно только показать, что среди e[V] не существует ориентированных циклов. Но доказательство этого можно получить сразу же, так как если fin(e[F]) = V = init(e[y]), где e[V] = ej и e[V] = ej, то j < f. I

Эту лемму, возможно, будет легче понять, если рассмотреть ее в обратном направлении, т. е. рассмотреть "первые входы" в каждую вершину. Первые входы образуют неупорядоченное дерево, в котором все дуги направлены от R. Лемма Е имеет следуюшую удивительную и очень важную обратную формулировку, справедливость которой доказана Т. ван Аардене-Эренфест и Н. Г. де Брейном [Т. van Aardenne-Ehrenfest and N. G. de Bruijn, Simon Stevin 28 (1951), 203-217].

Теорема D. Пусть G-конечный, сбалансированный, ориентированный граф, а G -ориентированное дерево, состоящее пз вершин графа G п нескольких дуг графа G. Пусть R - корень дерева G, а e[V] -дуга дерева G с начальной вершиной V. Пусть 61 -произвольная дуга графа G с init{ei) - R. Тогда ориентированный путь Р = (ei, 62,..., бт) будет цепью Эйлера, если для него выполняются следующие условия:

i) никакая дуга не проходится более одного раза, т. е. ej Ф е для j Ф к;

ii) e[V] не используется в Р, за исключением единственного случая, который удовлетворяет условию (i), т. е. если ej = e[V] и если е -дуга с init{e) = V, то е = Ck для некоторого к < j;

iii) путь Р заканчивается, только если он не может быть продолжен по правилу (i), т. е. если init{e) = fin(em), то е = для некоторого к.

Доказательство. Согласно условию (iii) и доказательству теоремы G получим, что fin(em) = init(ei) = R. Теперь, если е-дуга, которая не входит в состав пути Р, допустим, что V = fin(e). Так как граф G является сбалансированным, значит, V - это начальная вершина некоторой дуги, не входящей в состав пути Р, а если Уф R, то согласно условию (ii) получим, что e[V] не входит в состав пути Р. Используем теперь те же доводы с е = e[V] и в конечном итоге получим, что R - начальная вершина некоторой дуги, не входящей в состав этого пути, что противоречит условию (iii). I