5.5. Ориентированные остовы и ориентированные эйлеровы цепи

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

Пусть — вершины графа, G. Рассмотрим ориентированную эйлерову цепь С графа G. Пусть — дуга графа G, заходящая в вершину . Для любого будем считать, что обозначает первую дугу С, входящую в вершину после прохождения дуги Например, рассмотрим ориентированную эйлерову цепь графа, представленного на рис. 5.10. Если мы выберем , то . Пусть — подграф графа G на множестве дуг

Лемма 5.1. Пусть С — ориентированная эйлерова цепь ориентированного эйлерова графа G. Подграф Н, определяемый цепью С описанным способом, является ориентированным остовом с корнем

Доказательство. Очевидно, что в подграфе для всех . Допустим, что он содержит цикл С. Тогда вершина не входит в цикл С, иначе или для некоторой другой вершины цикла С. По этой же причине цикл С является контуром. Поскольку для всякой вершины v в цикле С, никакая из дуг, не принадлежащих С, не входит ни в какую вершину С. Это означает, что дуга , являющаяся первой после прохождения дугой цикла С, входящей в вершину цикла С, не принадлежит подграфу Н, что противоречит его определению. Следовательно, подграф Н на имеет циклов.

Теперь из п. 5 теоремы 5.4 следует, что подграф Н — ориентированный остов графа

Пусть — корень ориентированного остова ориентированного эйлерова графа G без петель на вершинах, — дуга, заходящая в вершину графа G. Пусть — дуга, входящая

в вершину подграфа Н. Опишем метод построения ориентированной эйлеровой цепи

1) Начать с вершины проходя назад по любой дуге, входящей в вершину отличной от (если такая дуга существует), или по , если нет альтернативы;

2) По достижении вершины оставить ее, проходя назад по дуге, которая еще не была пройдена и, если возможно, отличной от Остановиться, если не осталось непройденных дуг среди входящих в вершину

В этой процедуре каждый раз, когда достигается вершина будет существовать непройденная дуга, входящая в вершину поскольку полустепень захода всякой вершины графа G равна полустепени исхода. Следовательно, процедура закончится только в вершине после прохождения всех заходящих в нее дуг.

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

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

Поскольку в каждой вершине возможны различных вариантов последовательности выбора заходящих дуг — последняя), то число различных ориентированных эйлеровых цепей, которые можно построить по данным ориентированному остову подграфа Н и дуге , определяется выражением

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

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

Таким образом, мы доказали следующую теорему, принадлежащую де Брёйну и ван Аардену — Эренфесту [5.3].

Теорема 5.9. Число ориентированных эйлеровых цепей в ориентированном эйлеровом графе G без петель равно где — число ориентированных остовов графа G с корнем

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

Следствие 5.9.1. Число ориентированных остовов ориентированного эйлерова графа имеет постоянное значение, не зависящее от выбора корня.

Формула для нахождения числа выводится в разд. 6.9.