644 ОТВЕТЫ К УПРАЖНЕНИЯМ 2.3.4.2

будет строкой нулей. Поэтому, если граф G не является свободным деревом, детерминант матрицы Ао равен нулю.

Но, если граф G является свободным деревом, его можно рассматривать как упорядоченное дерево с корнем Vo, а строки и столбцы матрицы Ао переупорядочить так, чтобы столбцы располагались в прямом порядке и к-я строка соответствовала ребру от к-й вершины (столбца) к ее родителю. Тогда матрица будет треугольной с элементами ±1 по диагонали и ее детерминант будет равен ±1.

(Ь) По формуле Бине-Коши (см. упр. 1.2.3-46) получим

detAjAo= Е (detAi,..л„)

l<tl<.-.<t„<m

где Aii...i„-матрица из строк ii,...,i„ матрицы Ао (таким образом, соответствующая некоторому выбору п ребер графа G). Тогда ответ следует из (а).

[См. S. Okada and R. Onodera, Bull, yamagata Univ. 2 (1952), 89-117.]

19. (a) Условия аоо = О и Ujj = 1 представляют собой условия (а) и (Ь) из определения ориентированного дерева. Если G не является ориентированным деревом, то существует ориентированный цикл (согласно результату упр. 7), а строки матрицы Ао, соответствующие вершинам ориентированного цикла в сумме дадут строку нулей; следовательно, det Ао = 0. Если G - ориентированное дерево, зададим произвольный порядок для детей каждой семьи и рассмотрим G как упорядоченное дерево. Теперь будем переставлять строки и столбцы матрицы Ао до тех пор, пока они не будут соответствовать прямому порядку вершин. Так как одна и та же перестановка применяется как к строкам, так и к столбцам, детерминант матрицы остается неизменным. Полученная в результате матрица является треугольной со значениями 4-1 по диагонали.

(Ь) Можно допустить, что aoj = О для всех j, так как выходящие из вершины Vo дуги не могут входить в состав ориентированного поддерева. Можно также предположить, что Ojj > О для всех j > 1, поскольку в противном случае во всей j-й строке содержатся нули и ориентированных поддеревьев, очевидно, не существует. Далее воспользуемся методом индукции по количеству дуг. Если ojj > 1, то пусть е - некоторая дуга, выходящая из Vj; пусть Во-матрица, подобная Ао, но в которой удалена дуга е, и пусть Со - матрица, подобная Ао, но в которой удалены все дуги, за исключением дуги е, выходящей из вершины Vj. Пример. Если Ао = { 1 j = 1 и е - дуга от Vi к Уо, то Во = ( ; Со = ( J 2) • целом, получим det Ао = det Во 4- det Со, так как в этих матрицах совпадают все строки, за исключением j-й строки, а j-я строка матрицы Ао равна сумме j-x строк матриц Во и Со. Более того, количество ориентированных поддеревьев графа G равно количеству поддеревьев, в которые не входит ребро е (а именно, по индукции оно равно det Во), плюс количество поддеревьев, в которые входит ребро е (а именно, det Со).

Замечания. Матрица А часто называется лапласианом (Laplacian) этого графа, по аналогии с подобным понятием из теории дифференциальных уравнений с частными производными. При удалении любого множества S строк из матрицы А и такого же множества столбцов детерминант полученной в итоге матрицы будет равен количеству ориентированных деревьев, корни которых являются вершинами {14 /с € S} и дуги которых принадлежат данному диграфу. Теорема о матрице, соответствующей дереву, впервые была сформулирована без доказательства для ориентированных деревьев Дж. Дж. Сильвестром (J. J. Sylvester) в 1857 году (см. упр. 28), а затем надолго забыта, пока не была повторно исследована В. Т. Тутте (W. Т. Tutte) [Proc. Cambridge Phil. Soc. 44 (1948), 463-482, §3]. Ее доказательство для особого случая неориентированных графов, когда матрица А является симметричной, было впервые опубликовано К. В. Борхардтом (С. W. Borchardt) [Crelle 57 (1860), 111-121]. Некоторые авторы приписывают доказательство этой теоремы Кирхгофу, но он доказал совершенно другой (хотя и близкий) результат.

20. Используя упр. 18, получим В = AqAq. Или, используя упр. 19, получим, что матрица В - это матрица Ао ориентированного графа G, в которой каждое ребро заменено двумя дугами (по одной для каждого направления). Каждое свободное поддерево графа G соответствует единственному ориентированному поддереву графа G с корнем Vo, так как направления дуг определяются выбором корня.

21. Постройте матрицы А и А так же, как в упр. 19. Например, для графов G и G*, показанных на рис. 36 и 37, получим

[00] [10] [20] [01] [01] [21] [12] [12] [22]

Сложите неопределенную величину А с элементом в верхнем левом углу матриц А и А* (в данном примере получим 2 + А вместо 2). Если t(G) и t{G) - количество ориентированных поддеревьев в графах G я G соответственно, то получим t(G) = Х~{п + l)detA, t{G) = A"m(n4-1) det А*. (Количество ориентированных поддеревьев сбалансированного графа одинаково для любого выбора корня согласно упр. 22.)

Если сгруппировать вершины Vjk для равных к, то матрицу А можно разделить так, как показано выше. Пусть В -подматрица матрицы А, которая состоит из строк для вершины Vjk и столбцов для вершины Vjiy для всех таких j и /, что Vjk и Vjik принадлежат графу G. Складывая 2-й, ..., т-й столбец каждой подматрицы с первым

столбцом, а затем вычитая первую строку каждой подматрицы из 2-й, матрицу А можно привести к такому виду;

/Okk * *\ / akk + XSko

О О ... О -XSko

Вкк, = . . . для к ф к, Bkk =

♦

т-й строки.

V О О ... о/ \ -A<J*o О

Отсюда следует, что det А* в т""~ раз больше детерминанта матрицы

/ А 4- ООО * -А m

О О

ао\ О

аоп \ О

\ а„о * * ... * а„1 ... а„„/ В этих выкладках символ "♦" обозначает величины, которые не имеют отношения к данной задаче, причем все они равны нулю, за исключением одной звездочки в каждом столбце, которая равна -1. Сложим последние п строк с верхней строкой и разложим детерминант по первой строке, чтобы получить det А - (m - l)m"("~+"~ det А.

Эти рассуждения можно обобщить для определения количества ориентированных поддеревьев графа G*, когда граф G является произвольным ориентированным графом (см. R. Ddwson and I. J. Good, Ann. M&th. Stat. 28 (1957), 946-956; D. E. Knuth, Journal

of Combinatorial Theory 3 (1967), 309-314). Альтернативное и чисто комбинаторное доказательство предложено Дж. Б. Орлином [J. В. Orlin, Journai of Combinatorial Theory B25 (1978), 187-198].

22. Общее количество цепей Эйлера равно числу (txi 4- • • • 4- (Уп), которое умножено на количество цепей Эйлера, начинающихся с данного ребра ei, где init(ei) = Vi. Каждая такая цепь определяет ориентированное поддерево с корнем Vi согласно лемме Е, а для каждого из Т ориентированных поддеревьев существует Y[j=ii<j ~ !) путей, которые удовлетворяют трем условиям теоремы D, соответствующим различному порядку входа дуг {е I init(e) - Vj, е ф e[Vj], е / ei} в Р. (В упр. 14 приводится простой пример такой ситуации.)

23. Постройте ориентированный граф Gk с т*~ верщинами, как в указании, и используйте обозначение [xi,.. .,Xk] для упомянутой в нем дуги. Для каждой функции, которая имеет максимальный период, можно определить единственную соответствующую цепь Эйлера, предполагая, что f{xi,.. .,Хк) = Xk+i, если за дугой [xi,.. .,Хк] следует д,га [хг,.. ,а;*,+1]. (Цепи Эйлера считаются одинаковыми, если одна из них является результатом циклической перестановки другой.) Теперь Gj, - G*k i согласно обозначениям из упр. 21, поэтому Gk имеет в т™ раз больще ориентированных поддеревьев, чем Gk-i- По индукции граф Gk имеет т™ ~ ориентированных поддеревьев и т" деревьев с заданным корнем. Следовательно, согласно ответу к упр. 22 количество функций с максимальным периодом, а именно - количество цепей Эйлера графа Gk, которые начинаются с заданной дуги, равно m"*(m!)" . [Для m = 2 этот результат приводится в работе С. Flye Sainte-Marie, LIntermediaire des Afathematiciens 1 (1894), 107-110.]

24. Определите новый ориентированный граф, который имеет Ej копий Cj для О < j < т. Этот граф является сбалансированным, следовательно, по теореме G он содержит цепь Эйлера (ео,...). Искомый ориентированный путь можно получить, удалив ребро ео из цепи Эйлера.

25. Зададим произвольный порядок для всех дуг в множествах Ij = {е init(e) = Vj} и Fj = {е I fin(e) = Vj}. Для каждой дуги е в /, пусть ATAG(e) = О и ALINK(e) = е, если е расположено за е в упорядочении множества Ij, а также пусть АТАС(е) = 1 и ALINK(e) = е , если е - последний элемент множества Ij не - первый элемент множества Fj. Пусть в последне.м случае ALINK(e) = Л, если множество Fj пусто. Определим BLINK и BTAG согласно тем же правилам, лищь меняя роли iiiit и fin.

Примеры (каждый набор дуг расположен в алфавитном порядке).

Замечание. Если в представлении ориентированного дерева добавить другую дугу от Н к ней самой, то возникнет интересная ситуация: будут получены либо стандартные условия 2.3.1-(8) с взаимной заменой полей LLINK, LTAG, RLINK, RTAG в заголовке списка, либо (если новая дуга располагается последней в данном упорядочении) стандартные условия, за исключением RTAG = О в узле, который соответствует корню этого дерева.