AOP_Tom1 (1021736), страница 165
Текст из файла (страница 165)
Теперь будем переставлять строки и столбцы матрицы Ае до тех пор, пока они не будут соответствовать прямому порядку вершин. Так как одна и та же перестановка применяется как к строкам, так и к столбцам, детерминант матрицы остается неизменным. Полученная в результате матрица является треугольной со значениями +1 по диагонали. (Ь) Можно допустить> что ае„= О для всех у, так как выходящие из вершины 1е дуги не могут входить в состав ориентированного поддерева. Можно также предположить, что аы > О для всех ! > 1, поскольку в противном случае во всей 7-й строке содержатся нули и ориентированных поддеревьев, очевидно, не существует. Далее воспользуемся методом индукции по количеству дуг.
Если а, > 1, то пусть е — некоторая дуга, выходящая из 1Б пусть Ве — матрица, подобная Ае, но в которой удалена дуга е, и пусть Се — матрица, подобная Ае, но в которой удалены все дуги, эа искам ~своем дуги е, выходящей из вершины Ъм Лример. Если Ае = ( э ~), ! = 1 и е — дуга от Ъ; к Ъо, то Ве = (, э), ь е Се = (, э ). В целом, получим бег Ае — — бе! Во+ бес Се, так как в этих матрицах совпадают все строки, эа исключением 7-й строки, а 1-я строка матрицы Ае равна сумме 7-х строк матриц Ве и Се.
Более того, количество ориентированных поддеревьев графа С равно количеству поддеревьев, в которые не входит ребро е (а именно, по индукции оно равно бес Ве), плюс количество поддеревьев, в которые етодиги ребро е (а именно, с)еС Се). Замечания. Матрица А часто называется лапласианем (Вар!ас!ап) этого графа, по аналогии с подобным поннтием из теории дифференциальных уравнений с частными производными.
При удалении любого множества Я строк из матрицы А и такого же множества столбцов детерминант полученной в итоге матрицы будет равен количеству ориентированных деревьев, корни которых являются вершинами (1гь ! !г б В) и дуги которых принадлежат данному дигрэфу. Теорема о матрице, соответствующей дереву, впервые была сформулирована без доказательства для ориентированных деревьев Дж. Дж. Сильвестром (Л.
3. Яу!тагес) в 1857 году (см, уцр. 28), а затем надолго забыта, пока не была повторно исследована В. Т. Тутте (%'. Т. Тесте) (Ргос. Сатбпс!8е РЬ!!. Бос. 44 (1948), 453-482, 33). Ее доказательство для особого случая неориенглироеаннмх графов, когда матрица А является симметричной, было впервые опубликовано К.
В. Борхардтом (С. Ж. Вог<Ьагбс) (Сге!!е 57 (18бО), 1П-12Ц. Некоторые авторы приписывают доказательство этой теоремы Кирхгофу, но он доказал совершенно другой (хотя и близкий) результат. 20. Используя упр. 18, получим В = АтеАе. Или, используя упр. 19, получим, что матрица  — это матрица Ае ориентированного графа С', в которой каждое ребро заменено двумя дугами (по одной для каждого направления). Каждое свободное поддерево графа С соответствует единственному ориентированному поддереву графа С' с корнем Рш так как направления дуг определяются выбором корня. 21. Постройте матрицы А и А так же, как в упр. 19.
Например, для графов С н С*, показанных на рис. Зб и 37, получим [00) [10] [20) [ОЦ [ОЦ [2Ц [12) [12) [22) 2 0 0 — 1 -1 0 О 0 0 -1 3 0 — 1 — 1 0 0 0 0 — 1 0 3 — 1 -1 0 0 0 0 [00) [10) [20] А= -1 3-2 [ОЦ 0 -1 0 3 0 0 -1 -1 0 0 — 1 0 0 3 0 — 1 — 1 О 0 — 1 0 0 0 3 -1 — 1 0 А' = [ОЦ [2Ц [12! ΠΠ— 1 0 О -1 3 Π— 1 0 0 — 1 0 0 — 1 0 3 — 1 0 0 — 1 0 0 — 1 0 0 2 [12) [22] Сложите неопределенную величину Л с элементом в верхнем левом углу матриц А и А' (в данном примере получим 2 + Л вместо 2), Если С(С) и 1(С*) — количество ориентированных поддеревьев в графах С и С соответственно, то получим 1(С) = Л '(и+ 1) бес А, 1(С ) = Л 'тп(н+1) <наес А'.
(Количество ориентированных подлеревьев сбалансированного графа одинаково для любого выбора корня согласно упр. 22.) Если сгруппировать вершины г".ь для равных к, то матрицу А можно разделить так, как показано выше. Пусть Вьь — подматрица матрицы А*, которая состоит из строк для вершины Ъэь и столбцов лля вершины 1' и для всех таких у и у', что 1)ь и Ъ' ь принадлежат графу С'. Складывая 2-й, ..., т-й столбец каждой подматрипы с первым столбцом, а затем вычитая первую строку каждой подматрнцы из 2-й, ..., т-й строки, матрицу А' можно привести к такому виду: аы + Лбье — Лбьо пь . 0 в„ аы 0 0 ...
0 Вьь =... дляй~й~, 0 0 ... 0 -Лбье 0 " гл ОтСЮда СЛЕдуст, Чта ОЕС А" В ПГм1" П раэ бОЛЬШЕ дЕтЕрМИНаНта МатрИцЫ Л+аее * е ... е ае1 ... ае„ вЂ” Л гп 0 ... 0 0 ... 0 -Л 0 О .. т О ... 0 а1а е е ... е ап .. а1„ ае е ь ... е а1 ... а„„ В этих выкладках символ Ы" обозначает величины, которые не имеют отношения к данной задаче, причем все они равны нулю, за исключением одной звездочки в каждом столбце, которая равна — 1. Сложим последние и строк с верхней строкой и разложим детерминант по первой строке, чтобы получить пг" < и+ ' бес А — (гп — 1) ш" 1 и ь з бес А. Эти рассуждения можно обобщить для определения количества ориентированных поддеревьев графа С*, когда граф С является произвольным ориентированным графом (см.
Н, Г)апэоп аеб 1. б, Сооб, Апп. Лбасп. Ясак 28 (1957), 946 — 93б; П. Е. Кваса,,Уопгпа) оГ СотЬшасоНа! ТЬеогу 3 (1967), 309 — 314). Альтернативное и чисто комбинаторное доказательство предложено Дж. Б. Орлином [1. В. Огйп, Лоигпа! оУ Сотб!пасох!а! ТЬеогу В26 (1978), 187-198]. 22. Общее количество цепей Эйлера равно числу (о~ + . + о„), которое умяожено на количество цепей Эйлера, начинающихся с данного ребра ем где !и!л(е~) = !'л.
Каждая такая цепь определяет ориентированное поддерево с корнелл !'л согласно лемме Е, а для каждого из Т ориентированных поддеревьев существует П,",(сл, — 1)! путей, которые удовлетворяют трем условиям теоремы 1), соответствующим различному порядку входа дУг (е ] ~ше(е) = Рю е )4 еЯ], е эе ел) в Р. (В УпР. 14 пРиводитсЯ пРостой пРимеР такой ситуации.) 23.
Постройте ориентированный граф Сл с тл ' вершинами, как в указании, и используйте обозначение [хл,..., хл] для упомянутой в нем дуги. Для каждой функции, которая имеет максимальный период, можно определить единственную соответствующую цепь Эйлера, предполагая, что 7(хм..., хл) = хлэл, если за дугой [хл,..., хл] следует дуга [хл,..., хлел!. (Цепи Эйлера считаются одинаковыми, если одна из них является результатом циклической перестановки другой.) Теперь Сл —— Сл, согласно обозначениям из упр. 21, поэтому Сл ~-нл имеет в тп ~ раз больше ориентированных поддеревьев, чем Сл л. По индукции 1 — л граф Сл имеет т ' ориентированных поддеревьев и т деревьев с заданным корнем.
Следовательно, согласно ответу к упр. 22 количество функций с максимальным периодом, а именно — количество цепей Эйлера графа Сл, которые начинаются с заданной л-1 дуги, равно пл '(т!), [Для т = 2 этот результат приводится в работе С. г!уе Яа!плеМапс, й'!в!естес)(шге л)ее Масйетаг(с!епэ 1 (1894), 107 — 110.] 24. Определите новый ориентированный граф, который имеет Е„копий е, для 0 < 7 < т. Этот граф является сбалансирояанным, следовательно, по теореме С он содержит цепь Эйлера (ее,...). Искомый ориентированный путь можно получить, удалив ребро ее из пепи Эйлера.
25. Заладим произвольный порядок для всех дуг в ллножествах Тл = (е [ шй(е) = $;) и Е~ = (е [ йп(е) = Ъ;). Для каждой дуги е в ул пусть АТАС(е) = 0 и А11МК(е) = е', если е' расположено за е в упорядочении множества Ам а также пусть АТАС(е) = 1 и АЬ1МК(е) = е', если е — последний элемент множества Тл и е' — первый элемент множества Рр Пусть в послелнем случае А11МК(е) = Л, если множество Г, пусто. Определим ВЬ1КК и ВТАС согласяо тем же правилам, лишь меняя роли пп! и Яп. Примеры (каждый набор дуг расположен в алфавитном порядке). и лл ж лл н л н м м л л" 3 л м лл м лл ч ю ю 4 л 3 л а Ь а е ю а с 0 Ь 1 г й а И 1 Ь О с Ь а 1 И 0 Ь Л 1 с 0 с е 0 а 1 с 7' 1 т 1 л( Ь 0 !" 0 И Л 1 е 0 е Ь е д 0 ! 1 4 е 7 е Л 1 а 1 д о У Л ! с д с 1 Ь 0 г а 1 Л 1 ! Ь Ь ! 7 О е ! Л 1 Замечание.
Если в представлении ориентированного дерева добавить другую лугу от Н к пей самой, то возникнет интересная ситуация. будут получены либо стандартные условия 2.3.1-(8) с езапмной заменой полей ЬЬ1МК, ЬТАС, КЬТМК, КТАС в заголовке списка, либо (если новая дуга располагается последней в данном упорядочении) стандартные условия, за исключением АТАС = 0 в узле, который соответствует корню этого дерева. Настоящее упражнение основано на идее, которую автору сообщил В. Ч.
Линч (11!. С. Пулей). Можно ли, используя такое представление, обобщить алгоритмы обхода деревьев, подобные алгоритму 2.3.18, для классов диграфов, которые не являются ориентированными деревьями? 27. Пусть ао — сумма вероятностей р(е) для всех дуг е от 12 к 1',. Следует доказать, что !ч = 2', ач1, длЯ всех !. Так как 2, а„= 1, необходимо доказать, что 2, ап1„= 2, ап1,. Но это не так уж и трудно, поскольку обе стороны равенства представляют сумму всех произведений р(е~)...
р(е„), взятую по всем подграфам (еп, е„) такого графа С, что ! пй(е,) = (р, и в нем существует единственный ориентированный цикл, который содержится в (еп,.,, е ) и включает вершину 1',. Удалив любую дугу этого цикла, можно получить ориентированное дерево. Левую сторону равенства можно получить, разложив по дугам, выходящим из вершины 1;, тогда как правая сторона равенства соответствует разложению по дугам, входящим в 1;.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
