Д. Кнут - Искусство программирования том 1 (1119450), страница 104
Текст из файла (страница 104)
е. рассматриваемое свойство не только "слабее" свойства "строго связный", но и еще слабее, чем свойство "корневой"). Ориентированное дерево (огееп1ед 1гее) (рис. 34), иногда называемое некоторыми авторами корневым деревом, представляет собой ориентированный граф с такой вер- В шиной В, что: так как еь = 1'о.
Значит, ориентированное дерево является свободным деревом, есан не учитывать направления дуг. Следует отметить, чэо этот процесс можно обратить. Если начать с такого непустого свободного дерева, как на рис. 30, то можно в качестве корня В выбрать любую вершину и задать направления для ребер. Если представить себе, что граф "подвесили" за вершину В и встряхнули, то стрелки ребер в нем будут направлены вверх. Более строгая формулировка выглядит так. Заменить ребро à — Ро дугой от !' к Г' тогда и только тогда, когда простой путь от е' к В проходит через е', т.
е, когда он имеет вид (1'о,\'ы,..,Ъ'„), где и) О, Ио — — Ъ; К~ — — Ъ", $'„=В. Для проверки справедливости этого построения нужно доказать, что для каждого ребра И вЂ” Рч указано направление И +- 1" (или Г -э 1"). И это действительно легко сделать, если (1; 1'ы..., Л) и (1", 1,..., Л) являются простыми путями, т. е. цикл существует всегда, за исключением случаев, когда 1х = У или 1; = 1~'. Такое построение демонстрирует, что направления дуг в ориентированном дереве полностью определяются расположением корня, а потому их можно не указывать на схемах, на которых корень обозначен явным образом.
Таким образом, установлена связь между тремя типами деревьев: (упорядоченным) деревом, которое имеет принципиальное значение в компьютерных программах, как показано в начале раздела 2.3, ориентированным (или неупорядоченным) и свободным деревом. Два последних типа деревьев также встречаются при изучении компьютерных алгоритмов, но не так часто, как первый. Основнос различие между этими типами древовидных структур заключается только в обвеме структурной информации, которая считается суи1ественпой.
Например, на рис. 35 показаны три дерева, которые различны, только если рассматривать их как упорядоченные деревья (с корнем вверху). А если их рассматривать как ориентированные деревья, то идентичными являются первые два, поскольку порядок поддеревьев "слева направо" здесь не существен. Наконец, если считать деревья свободными, то все они на рис. 35 идентичны, так как корень не определен.
Рис. 35. Три древовиднь1е структуры. Цепью Эйлера (Еи!вгзап сппсий) в ориентированном графе является такой ориентированный путь (еыез,...,е ), что каждая дуга ориентированного графа встречается в этом пути только один рвз и бп(е,„) = 1п!1(е1). Она представляет собой "полный обход" дуг диграфа. (Цепь Эйлера названа в честь Леонарда Эйлера (Ьеоппап1 Еп1ег), который в 1736 году рассмотрел знаменитую задачу о том, что невозможно обойти во время воскресной прогулки семь мостов Кенигсберга, посетив каждый из них в точности один раз.
Он также рассмотрел аналогичную задачу для неориентированных графов. Цепи Эйлера не следует путать с цепями Гамильтона (Нагп1!!оп!ап с1гспйз), т. е. ориентированными циклами, в которых каждая вершина встречается только один раз; см. гл. 7.) Ориентированный граф называется сбалансированным (Ьа!ангес!) (рис. 36), если каждая вершина T имеет равные по неличине степени входа и выхода, т.
е. сколько существует ребер, для которых вершина 1г является начальной, столько же существует ребер, для которых вершина 1г является конечной. Это условие тесно связано с законом Кирхгофа (см. упр. 24). Если ориентированный граф имеет цепь Эйлера, то очевидно, что он должен быть связным н сбалансированным, за исключением случаев, когда он имеет изолированные вершины (!зо!а!ей аег!!ссз), т. е. вершины с равными нулю степенями входа и выхода. Рис. 36. Сбалансированный ориентированный граф. Итак, в настоящем разделе дано довольно много определений (ориентированный граф, дуга, начальная вершина, конечная вершина, степень выхода, степень входа, ориентированный путь, простой ориентированный путь, ориентированный цикл, ориентированное дерево, цепь Эйлера, изолированная вершина, а также строгая связность, наличие корня и сбалансированность), но приведено лишь несколько связанных с ними результатов.
Теперь мы готовы приступить к изучению более сложного материала. Первым основным результатом является теорема И. Дж. Гуда [1. Л. Соос), Х Ьопдоп Маса. Эос. 21 (1947), 167-169), который показал, что цепи Эйлера существуют всегда, кроме случаев, когда они очевидно невозможны.
Теорема С. Конечный ориентированный граф без изолированных вершин содержит цепь Эйлера тогда и только тогда, когда он связанный и сбалансированный. Доказательство. Предположим, что граф С сбалансирован и Р = (еы...,е,„) представляет собой ориентированный путь максимально возможной длины, в котором ни одна дуга не проходится дважды. Тогда, если 1г = йп(е„,) и если !с— степень выхода вершины у', то путь Р должен включать все !с дуг е с начальной вершиной !шс(е) = $'.
В противном случае можно было бы добавить с и получить более длинный путь. Но если 1п!!(е ) = 1' и у' ) 1, то бп(е ~) = К Следовательно, так как граф С сбалансирован, получим !п1!(ес) = !' = Йп(е ); в противном случае степень входа вершины )г должна быть не меньше !с + 1. Теперь, выполнив цикрическую перестановку в Р, получим, что любая дуга е вне этого пути не имеет общих начальных и конечных вершин с любой дугой этого пути. Поэтому, если Р не является цепью Эйлера, граф С не является связным. 3 Между цепями Эйлера и ориентированными деревьями существует следующая важная взаимосвязь.
Лемма Е. Пусть цепь Эйлера (еы..., е ) ориентированного графа С не имеет изааированных вершин и пусть В = Йп(е„,) = ш1г(е,). Пусть для каждой вершины )г ~ В ребро с[И] является последним выходом нз Г в этой цепи, г. е. е[1'] = е,, есшг 1пй(е,.) =1', и 1пй(еь) ф1' дляу < к < т. (1) Тогда вершины графа С с дугами е[Ъ'] образуют ориентнроваииоедерево с корнем Я. Доказательство. Свойства (а) и (Ь) определения ориентированного дерева, очевидно, удовлетворяются. Согласно результату упр. 7 достаточно только показать, что среди еЯ не существует ориентированных циклов. Но доказательство этого можно получить сразу же, так как если бп(с[И]) = Рч = 1пЫ(с[И']), где с[И] = ез и е[$"] = еу, то у < у'. 3 Эту лемму, возможно, будет легче понять, если рассмотреть ее в обратном направлении, т.
е. рассмотреть "первые входы" в каждую вершину. Первые входы образуют неупорядоченное дерево, в котором все дуги направлены от В. Лемма Е имеет следующую удивительную и очень важную обратную формулировку, справедливость которой доказана Т. ваи Аардене-Эренфест и Н. Г, де Врейном [Т. хап Аагс(еппе-Ейгеп(езг апб Х. С. Йе Вгпцп, Яшоп Ягелп 28 (1951), 203-217].
Теорема 11. Пусть С вЂ” конечный, сбалансированный, орпеятпрованный граф, а С' — ориентированное дерево, состоящее пз вершин графа С и нескольких дуг графа С. Пусть й — корень дерева С', а е[И] — дуга дерева С' с начальной вершиной г'. Пусть е| — произвольная дуга графа С с тп(е,) = В. Тогда ориентированный путь Р = (е„ез,...,е ) будет цепью Эйлера, есля для него выполняются следующие условия; 1) никакая дуга ие проходится более одного раза, п е, е . ф еь для у' ~ Й; й) е['г'] не используется в Р, за исключением едтгствениого случая, который удовлетворяет условию (Ц, т.
е, если е. = е[Ч] н если е — дуга с!шс(с) = 1~, то е = еь для некоторого й < 1; ш) путь Р заканчивается, только если ои не может быть продолжен по правилу (1), т. е. если 1шй(е) = Яп(е ), то е = еь для некоторого Й. Доказательство. Согласно условию (ш) и доказательству теоремы 6 получим, что бп(е ) = 1шс(е~) = Л. Теперь, если е — дуга, которая не входит в состав пути Р, допустим, что Г = бп(е). Так как граф С является сбалансированным, значит, г— это начальная вершина некоторой дуги, не входящей в состав пути Р, а если И ~ 17, то согласно условию (й) получим, что е[)г] не входит в состав пути Р.
Испальзуем теперь те же доводы с е = е[Г] и в конечном итоге получим, что Я вЂ” начальная вершина некоторой дуги, не входящей в состав этого пути, что противоречит условию (ш). 3 Суть теоремы г) заключается, в том, что она демонстрирует простой способ построения цепи Эйлера в сбалансированном ориентированном графе для заданного ориентированного поддерева этого прафа (см.
пример в упр. 14). Действительно, теорема П позволяет подсчитать точное количество цепей Эйлера в ориентированном графе. Этот результат и другие важные следствия идей, изложенных в данном разделе, излагаются в приведенных ниже упражнениях. УПРАЖНЕНИЯ э. [М20] Докажите, что если У и У' — вершины ариентираваннога графа и если существует ориентированный путь от У к У', то существует простой ориентированный путь атУкрг. 2. [15] Какие из десяти "фундаментальных циклов" (3) из раздела 2.3.4.1 являются ориентированными циклами в ориентированном графе на рис. 32 из того же раздела? 3.
[1б] Нарисуйте схемы для ориентированного графа, который является связным, но не корневым. 4. [М20] Понятие гпополагическая соргпиравко (горо?ад?са1 эагеапд) для любого конечного ориентированного графа С можно определить как такое линейное упорядочение его вершин И Уэ... 11м в котором 1п11(е) предшествует Йп(е) для всех ребер е графа С (см. раздел 2.2.3, рис. б и 7). Известно, чта ее можно выполнить не для всех конечных ориентированных графов. Для каких графов ее можно осуществить? (Для ответа используйте терминологию из этого раздела.) б. [М1б] Пусть С вЂ” ориентированный граф, который содерясит ориентированный путь (ег,...,е„) с Йп(е ) = 1а!с(ег). Докажите, что С не является ориентированным деревам, используя предложенную в этом разделе терминологию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
