AOP_Tom1 (1021736), страница 108
Текст из файла (страница 108)
[МОО) Пусть С вЂ” граф с п -Ь 1 вершинами 1е, Гц..., Ъ'„зз т ребрами ем..., е,. Преобразуел~ граф С в ориентированный граф, задав пронзволыюе направление для каждого ребра, а затем построим матрнпу Л размера т х (и+ 1) Н +1, если!ше(е,) ='11; ас. = -1, еглн бп(е;) = Ъ'; О в противном случае. Пусть Ао — матрица А размера т х и с удаленным О-м столбцом. а) При ги = и покажите, что детерминант матрицы Ао равен О, если С не является свободным деревом, и равен х1, если С лвллеплся свободным деревом.
Ь) Для произвольного ли покажите, что детерминант матрицы АоАо равен числу сваг бодных поддеревьев графа С (а нменно. количеству вариантов выбора и ребер из т ребер таким образом, чтобы полученный граф был свободным деревом). (Указание. Используйте условие (а) и результат упр, 1.2.3-46.] 19. (МИ] (Теорема о матрице, соогавегасплвующей дереву) Пусть С вЂ” ориентированный граф с и -~- 1 вершинами Ъш 1гы, 'гю Пусть А — матрица размера (и -> 1) х (и+ 1) с элементами а; -( ' — к, если л ф 3 и существует (с дуг от И к У; з ЕСЛИ Л = 1 И СУЩЕСтВУЕт Е ДУГ От 1гг К ДРУГИМ ВЕРШИНаМ.
(Отсюда следует, что а о+а,л ж +а, = О для О < л < и.) Пусть Ао — это та же матрица, в которой удалены 0-я строка и О-й столбец. Например, если С является ориентированным графом, который показан на рис. 36, получим — 3 — 2), а) Покажите, что если аоо = О и ам = 1 для 1 < з' < и и если С не имеет дуг, начинающихся и заканчивающихся в одной и той же вершине, то с1ес Ло = (С— ориентированное дерево с корнем Уо].
Ь) Покажите, что в общем случае бес Ао равно количеству ориентированных поддеревьев графа С с корнем 1"а (т. е. количеству способов выбора и дуг из всех дуг графа С, поэтому полученный в результате ориентированный граф является ориентированным деревом с корнем го). (Указание. Используйте метод индукции по количеству дуг] 20. (ЛЫ1] Если С вЂ” неориентнрованный граф с и + 1 вершинами 1о,..., Им пусть В— матрица размера и х п, которая для 1 < л,у < и определяется следующим образом: если л = з и есть 1 ребер, которые соприкасаются с вершиной 1м Ьч = -1, если л ф у и вершина И смежна с вершиной 1В ч ж О в противном случае. Например, если С вЂ гр, показанный на рис.
29, с (Го,"гы 1гз, Ип 1а) = (А, В, С,В,Е),то получим =Г Покажите, что количество свободных поддеревьев графа С равно с1ес В. [Указание. Используйте упр. 18 или 19.] 21. (НМ38] (Задача Т. ван Аардене-Эренфест и Н. П де Брейна.) На рис. 36 приведен пример ориентировашюго графа, который является не только сбалансированным, но и регулярным (геди(аг). Это означает, что все вершины имеют одинаковые степени входа и выхода. Пусть С вЂ” регулярный диграф с п+ 1 вершинами Уе, 1~и..., 'гю кюкдая вершина которого имеет степень входа и выхода, равную нь (Следовательно, в общем, существует (н+ 1)ш дуг.) Пусть С', граф с (и+ 1)гл вершинами, которые соответствуют дугам графа С, и пусть Ъ'ь — вершина графа С, соответствующая дуге от г) к 1ь в графе С.
Дуга проходит от $~~ь к 1з ь в графе С* тогда и только тогда, когда х = у( Например, если С вЂ” ориентированный граф, показанный на рис. 36, то граф С' представлен на рис. 37. Цепь Эйлера в графе С является цепью Гамильтона в графе С" > и наоборот. докажите, что количество ориентированных поддеревьев графа С в тш "П~ П раз больше количества ориентированных поддеревьев графа С.
]Указание. Используйте результат упр. 19,] Рис. 3Т. Диграф с дугами, который соответствует рис. 36 (см. упр. 21). ь 22. ]Мйб] Пусть С вЂ” сбалансированный, ориентированный граф с вершинами 1ы Ъз, ..., И без изолированных вершин. Пусть багз равно степени выхода вершины Ъ'. Покажите, что количество цепей Эйлера лдя графа С равно (, +, +... + „)Ту(о, — 1)), З см где à — количество ориентированных поддеревьев графа С с корнем К. Замечание. Множитель (о~ + + о„), который равен количеству дуг графа С, можно опустить, если цепь Эйлера (еы..., е ) считается равной (ее,...,е,еы...,еь ~) ] ° 23.
(Муу] (Задача Н. Г. де Брейна.) Для каждой последовательности неотрицательных целых чисел хп...,хь, меньших, чем т, допустим, что у(хп..., хь) — неотрицательное целое число, меньшее, чем щ. Определим бесконечную последовательность таким образом: Л! = Хз =. = Х! = О; Л +4+! = ДХ+ю...,Х4!), где и > О. Для какого количестваиз этих т возможных функиий 1 последовательность будет периоднчной с максимальным периодом гпь? (Указание. Постройте ориентированный граф с вершинами (хг,..., хь-!) дЛя ВСЕХ О < В; < т И С дуГаМИ От (Х4гяз,...,яз !) К (Хз,...,зь 4,Х!); ПРИМЕинтс результаты упр. 21 н 22.) ь 24. [М20] Пусть С вЂ” связный диграф с дугами ео,е4,...,е .
Пусть Ео,Е!,...,Е множество положительных целых чисел, которые удовлетворяют закону Кирхгофа для графа С, т. е. для каждой вершины 1", Е,= ~ Е,. )лщ )=!' е 4 )=!' Также предположим, что Ео = 1. Докажите, что в графе С существует такой ориентированный путь от бп(со) к!и!4(ео), что ребро е содержится в нем Е! раз для 1 < ) < т, тогда как ребро ее не входит в него вообще, (Указание. Примените теорему С к соответствующему ориентированному графу.) 26. (26) Создайте компьютерное представление ориентированных графов, которые обобщают представление дерева в виде правопрошитого бинарного дерева. Используйте два поля связи АНТИК„ ВВ1КК и два однобитовых поля АТАС.
ВТАС так, чтобы зто представление обладало следующими свойствами: (!) для каждой дуги (а не каждой вершины) ориентированного графа существует один узел; (й) если ориентированный граф является ориентированным деревом с корнем Я н если добавить дугу от Н к новой вершине Н, то представление ориентированного графа будет точно таким же, как представление этого ориентированного дерева в виде правопрошнтого бинарного дерева (с некоторым порядком.
накладываемым на детей каждой семьи) в том смысле, что поля А11МК, В11ВК, ВТАС соответствуют полям 1.11ВК, В11КК, ВТАС из раздела 2 3 2; (ш) представление является сшзмегр4шным в том смысле, что обмен полей АО1ВК и АТАС с В).1КК и ВТАС эквивалентен изменению направления всех дуг ориентированного графа.
2 26. (НМЗ9) (Анализ случайного алгориглма.) Пусть С вЂ” ориентированный граф с вершинами У4, Гз,...,1' . Допустим, что С представляет блок-схему алгоритма, где 1!— вершина блока "Начало" и 1'„— вершина блока "Конец". (Следовательно, вершина 1'„— корень графа С.) Предположим, что каждой дуге е графа С приписана вероятность р(е), которая удовлетворяет условиям О<р(е) <1; р(е)=1 для)<9< ы и )=4! Рассмотрим случайный путь, который начинается в вершине Тг!, а дуга е графа С последовательно выбираются с вероятностью р(е) до тех пор, пока не будет достигнута вершина 1'; причем выбор дуги на каждом этапе не зависит от сделанных ранее выборов.
Рассмотрим, например, граф из упр. 2.3.4.1-7 и присвоим вероятности 1, 2, —, 2, 1, 4, з 4., -, — дугам е4, ег,..., еэ. Тогда путь 'Начало — А-В-С-А — Р—  — С-Конец" будет выбран ! ! ! с вероятностью 1 — 1 — — — 1 з, ! з 2 2 2 4 4 424' Такие случайные пути называются цеплмв Маркова (Магйоо сйагнз) в честь русского математика Андрея Андреевича Маркова, который первым провел интенсивные исследования подобных стохастических процессов. Эту ситуацию можно применять для моделирования некоторых алгоритмов, хотя используемое условие выбора каждой дуги независимо от предыдущего пути является чрезвычайно сильным предположением.
Назначение данного упражнения заключается в анализе времени вычигчения алгоритмов такого типа. Этот анализ можно упростить, если рассмотреть матрицу А = (ао) размера и х и, где а,т = 2.' р(е) и сумма вычисляется по всем таким дугам е, которые проходят от вершины 14 к вершине 1'.
Если таких дуг нет, то а; = О. В рассмотренном выше примере матрица А выглядит так: Отсюда сразу же следует, что (А") о — это вероятность того, что путь, который начинается в вершине Гт„закончится в вершине Ьт после Ь шагов. Докажите справедливость приведенных ниже утверждений для произвольного ориентированного графа С указанного типа. а) Матрица (Š— А) не является сингулярной. [Указание. Покажите, что не существует такого ненулевого вектора х, для которого хА" = х.[ Ь) Среднее количество появлений вершины 1', в этом пути равно (Š— А), ' = со(асгогт1(1 — А)/г)ег(Š— А) для 1 < 1 < и, где соГасгогм (Š— А) — принятое здесь и далее обозначение алгебраического дополнения элемента в 1-й строке и Гг-м столбце матрицы (Š— А), [Таким образом, в рассмотренном примере показано, .что вершины А, В, С, Р в среднем проходятся —, з, —, з раз.) 1з т т з с) Вероятность тога, что вершина 1т встречается в этом пути, равна а = со(асгогт1(Š— А)/соГасгогтэ(Š— А); причем а = 1, а потому данный путь с вероятностью "единица" прекращается спустя конечное количество шагов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
