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

УПРАЖНЕНИЯ

1. [М20] Докажите, что если V и V-вершины ориентированного графа и если существует ориентированный путь от V к V, то существует простой ориентированный путь от V к V.

2. [15] Какие из десяти "фундаментальных циклов" (3) из раздела 2.3.4.1 являются ориентированными циклами в ориентированном графе на рис. 32 из того же раздела?

3. [16] Нарисуйте схемы для ориентированного графа, который является связным, но не корневым.

► 4. [М20] Понятие топологическая сортировка (topological sorting) для любого конечного ориентированного графа G можно определить как такое линейное упорядочение его вершин Vl V2 ... Vn, в котором init(e) предшествует fin(e) для всех ребер е графа G (см. раздел 2.2.3, рис. 6 и 7). Известно, что ее можно выпо.г1Нить не для всех конечных ориентированных графов. Для каких графов ее можно осуществить? (Для ответа используйте терминологию из этого раздела.)

5. [М16] Пусть G - ориентированный граф, который содержит ориентированный путь (ei,...,en) с fin(en) = init(ei). Докажите, что G не является ориентированным деревом, используя предложенную в этом разделе терминологию.

6. [М21] Справедливо ли следующее утверждение: "Ориентированный граф, который является корневым и не содержит циклов и ориентированных циклов, является ориентированным деревом"?

► 7. [М22] Справедливо ли следующее утверждение: "Ориентированный граф, удовлетворяющий условиям (а) и (Ь) из определения ориентированного дерева и не имеющий ориентированных циклов, является ориентированным деревом" ?

8. [НМ4О] Изучите свойства группы автоморфизмов (automorphism groups) ориентированных деревьев, т. е. групп, состоящих из всех перестановок тг вершин и дуг, для которых init(en-) = init(e)n-, fin(en-) = fin(e)n-.

9. [18] Указывая направления ребер, нарисуйте схему ориентированного дерева, которое соответствует свободному дереву, показанному на рис. 30, где G - это корень.

10. [22] Ориентированное дерево с вершинами Vi,..., Vn можно представить в компьютере с помощью таблицы Р[1];..., Р[п] следующим образом. Если Vj - корень, то P[j] = 0; в противном случае P[j] = к, если дуга e[Vj] проходит от Vj к Vk- (Таким образом, Р[1],..., Р[п] - это такая же таблица, как "родительская" таблица, используемая в алгоритме 2.3.ЗЕ.)

В настоящем разделе показано, как свободное дерево может быть преобразовано в ориентированное с помощью выбора произвольной вершины в качестве корня. Следовательно, ориентированное дерево с корнем Я можно, пренебрегая направлениями дуг, преобразовать в свободное дерево, а затем задать для них новые направления, получив в итоге ориентированное дерево с корнем в некоторой произвольно выбранной вершиной. Создайте алгоритм, который выполняет такое преобразование заданной таблицы Р[1],..., Р[п], представляющей ориентированное дерево, в результате которого таблица Р

будет представлять это же свббодное дерево, но с корнем в вершине Vj, где j - заранее заданное целое число, 1 < j < п.

► 11. [28] Используя условия упр. 2.3.4.1-6, но с учетом того, что (ofc,bfc) - это дуга от Va,, к Vbi., создайте алгоритм, который распечатывал бы содержимое не только свободного поддерева, но и фундаментальных циклов. [Указание. Можно использовать алгоритм из ответа к упр. 2.3.4.1-6 в сочетании с алгоритмом из предыдущего упражнения.]

12. [МЮ] В соответствии с предложенным здесь определением ориентированного дерева и его определением, данным в начале раздела 2.3, можно ли отождествить степень узла дерева со степенью входа или степенью выхода соответствующей вершины?

► 13. [М24] Докажите, что если R - корень, возможно, бесконечнбго ориентированного графа G, то G содержит ориентированное поддерево с теми же вершинами и корнем Я. (Отсюда следует, что в блок-схемах, аналогичных блок-схеме на рис. 32 из раздела 2.3.4.1, всегда можно выбрать свободное поддерево, которое действительно является ориентированным. Именно такое поддерево было бы показано на этой схеме, если бы мы выбрали е/з, ei9> его и ей вместо eis, eig, егз и eis-)

14. [21] Пусть G - сбалансированный диграф, показанный на рис. 36, а G-ориентированное поддерево с вершинами Voi Vi, V2 и дугами eoi, ezi. Найдите, начиная с дуги ei2, все пути Р, которые удовлетворяют условиям теоре.мы D.

15. [М20] Справедливо ли следующее выражение; "Ориентированный, связный и сбалансированный граф является строго связным" ?

► 16. [М24] В популярном пасьянсе "Часы" обычная колода из 52 карт располагается лицевой стороной вниз в 13 стопках по четыре карты в каждой; причем 12 стопок располагаются по кругу, а стопка 13-в центре, что, в общем, напоминает циферблат часов. Затем пасьянс раскладывается следующим образом: карта в центральной стопке переворачивается и, если ее значение равно к, размещается возле стопки к. (Значения 1,2, ...,13 соответствуют тузу, 2, ..., 10, валету, даме, королю.) Раскладывание продолжается таким образом: верхняя карта из стопки к переворачивается и располагается рядом с ее стопкой и т. д. до тех пор, пока не будет достигнут момент, когда продолжать игру уже невозможно, так как в очередной указанной стопке больше нет карт, которые люжно было бы перевернуть. (Игрок не обладает правом выбора варианта продолжения игры, так как эти правила полностью диктуют ход игры.) Игра считается выигранной, если к ЭТОМ} моменту все карты повернуты лицевой стороной вверх. [См. Е. D. Cheney, Patience (Boston: Lee & Shepard,. 1870), 62-65; как говорится в книге М. Whitmpre Jones, Games of Patience (London: L. Upcott Gill, 1900), Chapter 7, в Англии этот пасьянс называется "Пасьянсо.м путешественника".]

Покажите, что игра выиграна тогда и только тогда, когда следующий ориентированный граф является ориентированным деревом: Vi, Vo,..., Vn -вершины, ei, ег,..., ей - дЗги, где Cj проходит от Vj к 14, если к - самая нижняя карта в стопке j после сдачи карт.

(В частности, если самой нижней картой в стопке j является карта "j" для j ф 13, то легко видеть, что игра, определенно, будет проигрышной, так как эта карта никогда не сможет быть повернута лицевой стороной вверх. Доказанный в настоящем упражнении результат позволяет гораздо быстрее раскладывать такой пасьянс!)

17. [М32] Какова вероятность выигрыша при раскладывании пасьянса "Часы" (который описан в упр. 16) при условии, что колода тщательно перетасована? Какова вероятность того, что в точности к карт остаются повернутыми лицевой стороной вниз в момент прекращения игры?

18. [МЗО] Пусть G - граф с п -I-1 вершинами Fo, F,..., Vn am ребрами ei,..., en- Преобразуем граф G в ориентированный граф, задав произвольное направление для каждого

ребра, а затем построим матрицу А размера m х (п + 1)

{+1, если init(ei) =V; ; 1, если fin(ei) = Vj ; О в противном случае.

Пусть Ао - матрица А размера т х п с удаленным 0-м столбцом.

a) При тп = п покажите, что детерминант матрицы Ао равен О, если G не является свободным деревом, и равен ±1, если G является свободным деревом.

b) Для произвольного т покажите, что детерминант матрицы АоАо равен числу свободных поддеревьев графа G (а именно, количеству вариантов выбора п ребер из m ребер таким образом, чтобы полученный граф был свободным деревом). [Указание. Используйте условие (а) и результат упр. 1.2.3-46.]

19. [М31] (Теорема о матрице, соответствуюией дереву.) Пусть G - ориентированный граф с 71 + 1 вершинами Vo, Vi, ..., V„. Пусть А - матрица размера (тг + 1) х (тг + 1) с элементами

если i ф j и существует к дуг от Vi к Vj; если i = j и существует t дуг от Vj к другим вершинам.

(Отсюда следует, что a,o -t-Oii + • • -t-Oin = О для О < г < тг.) Пусть Ло -это та же матрица, в которой удалены 0-я строка и О-й столбец. Например, если G является ориентированным графом, который показан на рис. 36, получим

/2-2 0\

(-к,

-1 3 -2 V-1 -1 2/

Ао =

3 -2\ -1 2)

a) Покажите, что если ооо = О, и Ojj = 1 для 1 < j < тг и если G не имеет дуг, начинающихся и заканчивающихся в одной и той же вершине, то det Ло = [G-~ ориентированное дерево с корнем Vo].

b) Покажите, что в общем случае det Ао равно количеству ориентированных поддеревьев графа G с корнем Vo (т. е. количеству способов выбора п дуг из всех дуг графа G, поэтому полученный в результате ориентированный граф является ориентированным деревом с корнем Vo)- [Указание. Используйте метод индукции по количеству дуг.]

20. [М21] Если G - неориентированный граф с тг -- 1 вершинами Vb,., Vk, пусть В - .матрица размера п х п, которая для 1 < г, J < тг определяется следующим образом:

{t, если i = j и есть t ребер, которые соприкасаются с вершиной Vj; - 1, если i ф i а вершина У, смежна с вершиной V}; О в противном случае.

Например, если G - граф, показанный на рис. 29, с (Vo, 14, V2, Va, V4) = (A,B,C,D,E), то получим

/3 0-1 -1\ 0 2-10 -1 -1 3 -1 \-1 О -1 2/

Покажите, что количество свободных поддеревьев графа G равно det В. [Указание. Используйте упр. 18 или 19.]

21. [НМ38] (Задача Т. ван Аардене-Эренфест и Н. Г. де Брейна.) На рис. 36 приведен пример ориентированного графа, который является не только сбалансированным, но и регулярным (regular). Это означает, что все вершины имеют одинаковые степени входа и