AOP_Tom1 (1021736), страница 107
Текст из файла (страница 107)
Пусть цель Эйлера (еы...,е ) ориентированного графа С не. имеет изолированных вершин н пусть В = бп(е„,) = 1пй(е1). Пусть для каждой вершины $'ф В ребро еЩ является последним выходом из г' в этой цепи, т. е. е]1'] = е, если 1п11(е ) = 1', и 1шс(еь) ф 1' для у' < Й < т. (1) Тогда вершины графа С с дугамл е('г'] образуют ориентированное дерево с корнем В.
Доказательство. Свойства (а) и (Ь) определения ориентированного дерева, очевидно, удовлетворяются. Согласно результату упр. 7 достаточно только показать, что среди е[Ц не существует ориентированных циклов. Но доказательство этого можно получить сразу же, так как если бп(е(1']) = г' = 1шт(е(1л]), где е]г'] = е. и е]Г]=ей,тоу <у'. ! Эту лемму, возможно, будет легче понять, если рассмотреть ее в обратном направлении, т.
е. рассмотреть "первые входы" в каждую вершину, Первые входы образуют неупорядоченное дерево, в котором все дуги направлены от В. Лемма Е имеет следующую удивительную и очень важную обратную формулировку, справедливость которой доказана Т. ван Аардене-Эренфест и Н. Г. де Брейном ]Т, тап Аатоеппе-ЕЬгешевс апо Х. 6.
пе Вгп|)п, Яипоп Ясег1п 28 (1951), 203 — 217]. Теорема 1У. Пусть С вЂ” конечный, сбалансированный, ориентированный граф, а С' — ориентированное дерево, состоящее нз вершин графа С и нескольких дуг графа С. Пусть Й вЂ” корень дерева С', а е]ь'] — дуга дерева С' с начальной вершиной 10 Пусть е1 — произвольная дуга графа С с ~ш1(е~ ) = В. Тогда ориентированный путь Р = (еыет,...,е ) будет цепью Эйлера, если для него выполняются следующие условия: 1) никакая дуга не проходится более одного раза, т, е, е ~ еь для 7' ф Й; й) е~Ь'] не используется в Р, за ясключенлем единственного случая, который удовлетворяетусловию (1), т. е.
если е = е]1'] н если е — дуга с1шй(е) = 1; то и = еь для некоторого Й < у; 1И) путь Р заканчивается, только если он не может быть продолжен по правилу (1), т. е. если 1п1с(е) = бп(е ), то е = еь для некоторого Й. Доказательство. Согласно условию (ш) и доказательству теоремы С получим, что бп(е ) = 1п11(е~) = В. Теперь, если е — дуга, которая не входит в состав пути Р, допустим, что 1' = бп(е). Так как граф С является сбалансированным, значит, г'— это начальная вершина некоторой дуги, не входящей в состав пути Р, а если 1'ф Л, то согласно условию (й) получим, что еЩ не входит в состав пути Р.
Используем теперь те же доводы с е = е]1г] и в конечном итоге получим, что  — начальная вершина некоторой дуги, не входящей в состав этого пути, что противоречит условию (ш). $ Суть теоремы П заключается. в том, что она демонстрирует простой способ построения цепи Эйлера в сбалансированном ориентированном графе для заданного ориентированного поддерева этого ярафа (см. пример в упр.
14). Действительно, теорема Р позволяет подсчитать точное количество цепей Эйлера в ориентированном графе. Этот результат и друтие важные <щедствия идей, изложенных в данном разделе, излагаются в приведенных ниже упражнениях. УПРАЖНЕНИЯ 1. [М20] Докажите, что если И и 1' — верьзины ориентированного графа и если существует ориентированный путь от И к И', то существуег простой ориентированный путь от И к 1". 2.
[10] Какие из десяти "фундаментальных циклов" (3) из раздела 2.3.4,1 являются аривигаирвваннмми циклами в ориентированном графе на рис 32 из того же раздела? 3. [10] Нарисуйте схемы для ориентированного графа, который является связным, но не корневым. 4. [М20] Понятие твпвлвгическал сартиравка (гара!ад(са(авгбпд) для любого конечного ориентированного графа С можно определить как такое линейное упорядочение его вершин 1'~ Ъю .. 'г'„, в котором 1шз(е) предшествует бп(е) для всех ребер е графа С (см. раздел 2.2.3, рис. б и 7). Известно, что ее можно выполнить не для всех конечных ориентированных графов. Для каких графов ее можно осуществить? (Для ответа используйте терминологию из этого раздела.) б.
[М1б] Пусть С вЂ” ориентированный граф, который содержит ориентированный путь (ем, .., е„) с йп(в„) = шн(е~). Докажите, что С не является ориентированным деревом, используя предложенную в этом разделе терминологию. 6. [М21] Справедливо ли следующее утверждение. "Ориентированный граф, который является корневым и не содержит циклов и ориентированных циклов, является ориентированным деревом" ? 7. [М22] Справедливо ли следующее утверждение: "Ориентированный граф, удовлетворяющий условиям (а) и (Ь) из определения ориентированного дерева и не имеющий ориентированных циклов, является ориентированным деревом"? 8. [НМ40] Изучите свойгтва группы авшвмарфизмвв (аи1ататрямт дгвира) ориентированных деревьев, т е. групп, состоящих из всех перестановок г вершин и дуг, для которых шй(ег) = шй(е)х, Йп(ех) = бп(с) а.
9. [1В] Указывая направления ребер, нарисуйте схему ориентированного дерева, которое соответствует свободному дереву, показанному на рис. ЗО, где 0 †э корень. 1О. [22] Ориентированное дерево с вершинами Ъ'и..., г'„можно представить в компьютере с помощью таблицы Р[Ц, ..,, Р[п] следующим образом.
Если Ъ' -- корень, то Р[А = О; в противном случае Р[1] = lс, если дуга е[1',] проходит от 1', к Ъы (Таким образом, Р[Ц,, Р[п] — это такая же таблица, как "родительская" таблица, используемая в алгоритме 2.3.ЗЕ.) В настоящем разделе показано, как свободное дерево может быть преобразовано в ориентированное с помощью выбора произвольной вершины в качестве корня. Следовательно, ориентированное дерево с корнем 1? можно, пренебрегая направлениями дуг, преобразовать в свободное дерево, а затем задать для них новые направления, получив в итоге ориентированное дерево с корнем в некоторой произвольно выбранной вершиной. Создайте алгоритм, который выполняет такое преобразование заданной таблицы Р[Ц,..., Р[п], представляющей ориентированное дерево, в результате которого таблица Р будет представлять это же свцболное дерево, но с корнем в вершине $'м где !' — заранее заданное целое число, 1 < !' < и. ь 11.
[28) Используя условия уп)Э. 2.3.4.1-6, но с учетом того, что (аз, Ьз) — - это дуга от У „ к Узз, создайте алгоритм, который распечатывал бы содержимое не только свободного полдерева, но и фундаментальных Шзклов. [Указание. Можно использовать алгоритм из ответа к упр. 2.3.4 1-6 в сочетании с алгоритмом из предыдущего упражнения.) 12. [М!О) В соответствии с предложенным здесь определением ориентированного дерева и его определением, данным в начале раздела 2.3, можно ли отождествить сглепснь узла дерева со сглепенью входа или сшепенью выхода соответствующей вершины? ь 13. [МО4] Докажите, что если  — корень, возможно, бескопечнвго ориентированного графа С, то С' содержит ориентированное поддерево с теми же вершинами и корнем Й.
(Отсюда следует, что в блок-схемах, аналогичных блок-схеме на рис. 32 из раздела 2.3.4 1, всегда можно выбрать свободное поддерево, которое действительно является ориентированным. Именно такое поддерево было бы показано на этой схеме, если бы мы выбрали л н езз е',з, езо и еы вместо е|з е,з, езз и еш ) 14. [21) Пусть С вЂ” сбалансированный диграф. показанный иа рис.
36, а С' — ориентированное поддерево с верпзипами Ъ~, 1''н Из и дугами ещ, езь Найдите, начиная с дуги еш, все пути Р, которые удовлетворяют условиям теоремы П. 15. [МОО] Справедливо ли следующее выражение: "Ориентированный, связный и сбалансированный граф является строго связным"" ь 16. [М84) В популярном пасьянсе "Часы" обычная колода из 52 карт располагается лицевой стороной вниз в 13 стопках по четыре карты в каждой; причем 12 стопок располагаются по кругу, а стопка 13 — в центре, что, в общем, напоминает циферблат часов. Затем пасьянс раскладывается следующим образом: карта в центральной стопке переворачивается и, если ее значение равно?с, размещается возле стопки Л. (Значения 1,2,...,13 соответствуют тузу, 2, ..., 10, валету, даме, королю.) Раскладывание продолжается таким образом: верхняя карта из стопки ?с переворачивается и располагается рядом с ее стопкой и т. д, до тех пор, пока не будет достигнут момент, когда продолжать игру уже невозможно, так как в очередной указанной стопке больше нет карт, которые можно было бы перевернуть.
(Игрок не обладает правом выбора варианта продолжения игры, так как эти правила полностью диктуют ход игры.) Игра считается выигранной, естн к этому моменту все карты повернуты лицевой стороной вверх. [См. Е. П. СЛепеу, Рабепге (Вощоп: Еее 3г БЛераг0,.1870), 62 — 65; как говорится в книге М. %!исшоге !опез. Сашез о! Рабепсе (Еопбозз: 1.. 1!рсоы Сй!, 1900), СЛарзег 7, в Англии этот пасьянс называется "Пасьянсом путешественника".) Покажите, что игра выиграна тогда и только тогда, когда следующий ориентированный граф является ориентированяым деревом: Ум 1',.... Ъ;з — вершины, ем ег,, е1з— дуги, где е„проходит от 1'' к Им если 1 — самая нижняя карта в стопке ! после сдачи карт. (В частности, если самой нижней картой в стопке ! является карта "у' для ! Ф 13, то легко видеть, что игра, определенно, будет проигрышной, так как эта карта никогда не сможет быть повернута лицевой стороной вверх.
Доказанный в настоящем упражнении результат позволяет гораздо быстрее раскладывать такой пасьянс!) 17. [МЯО) Какова вероятность выигрыша при раскладывании пасьянса "Часы" (который описан в упр. 16) прн условии, что колода тщательно перетасована? Какова вероятность того, что в точности Л карт остаются повернутыми лицевой стороной вниз в момент прекращения игры? 18.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
