Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 111
Текст из файла (страница 111)
Таким образом, если прибавить 2 к каждому элементу в строке 1, то получим строку, которую следует рассматривать как матрицу-строку, обозначая ее А' = (2,4,оо,5, оо), так что Аз1(1) — вес пути длины 2, или 2-пути из вершины ьа к вершине огр Если рассматривать Аз = (2,0,4, оо,1), строку 2 матрицы А как матрицу-строку, тогда Аз(~) — вес пути длины 1 из вершины из к вершине о .
Поскольку нас интересует кратчайший путь для каждого г', заменяем строку 2 матрицы А на Аз д Аз —— (2,4, оо,5, оо) л (2,0,4, оо,1) = (2,0,4,5,1). Аналогичным образом, в строке 4 первого столбца находится число 3. Таким образом, существует ребро из вершины иг к вершине о| весом 3. Если в строке 1 на позиции (1, 1) имеется целое число т, то существует ребро из вершины и4 к вершине о, весом гп. Тогда 3+ пт — вес 2-пути из вершины ь4 к вершине и.. Следовательно, если прибавить 3 к каждому элементу в строке 1, то получим строку, которую следует рассматривать как матрицу-строку, обозначая ее Аг — — (3,5,оо,6, оо), так что А44(~) — вес 2-пути из о4 к и~. Если рассматривать Аг = (3, оо,6,0,3), строку 4 матрицы А как матрицу-строку, тогда А4(~) — вес пути длины 1, или 1-пути из вершины и4 к вершине о,.
Поскольку нас интересует кратчайший путь для каждого (, заменяем строку 4 матрицы А на Аг д А4 — — (3,5,оо,6, оо) Л (З,со,6,0,3) = (3,5,6,0,3). И т.к. в других строках столбца 1 больше нет положительных целых чисел, первый этап завершен, в результате которого имеем 0 2 оо 3 оо 2 0 4 5 1 оо 4 0 6 2 3 5 6 0 3 оо 1 2 3 0 АОО = 0 2 6 3 3 2 0 4 5 1 6 4 0 6 2 3 5 6 0 3 3 1 2 3 0 АОО Теперь используем второй столбец матрицы АП>. Если в строке г столбца 2 имеется число й, то существует ребро из вершины и, к вершине оз весом /с.
Если в строке 1 на позиции (2,1) имеется целое число т, то существует ребро из вершины оз к вершине о, весом т. Тогда к+ пт — вес пути из и; к о . Следовательно, если прибавить число й к каждому элементу в строке 2, то получим строку, которую следует рассматривать как матрицу-строку, обозначая ее А~, так что Аз(1) — длина 2-пути из вершины о, к вершине и . Если рассматривать А„ строку 1 матрицы АОО как матрицу-строку, тогда А,(~) — длина пути из вершины и, к вершине и . Поскольку нас интересует кратчайший путь для всех у, заменяем строку г' матрицы АОО на А~ л А,.
Во втором столбце имеется число 2 в строке 1, число 4 — в строке 3, число 5 — в строке 4 и число 1 — в строке 5. Используя этот процесс для каждой из указанных строк, получаем РЯЗДЕЛ 145. Взвешенные графы и алгоритмы поиска кратчайшего пути 621 Рассмотрим теперь третий столбец матрицы А(з). Для каждой позиции (3, )) матрицы А(з), на которой имеется положительное целое число, прибавляем это число к третьей строке матрицы А(з), получая матрицу-строку Аз, после чего положим А равной )-ой строке матрицы А(З). Далее заменяем 1-ю строку матрицы А(з) на Аз л А, и получаем О 2 6 3 3 2 О 4 5 1 6 4 О 6 2 3 5 6 О 3 3 1 2 3 О Теперь рассмотрим четвертый столбец матрицы А(з).
Для каждого положительного элемента на позиции (4,1) матрицы А(з) добавляем это значение к четвертой строке матрицы А(з), чтобы получить Аг и положить А., равной )-ой строке матрицы А(з). Далее заменяем )-ю строку матрицы А(з) на А4 д А и получаем О 2 6 3 3 2 О 4 5 1 6 4 О 6 2 3 5 6 О 3 3 1 2 3 О Наконец, рассмотрим пятый столбец матрицы А(4). Для каждого положительного элемента на позиции (5, )) матрицы А(4) прибавляем это значение к пятой строке матрицы А(4), получая Аз, и полагаем Аз, равной )'-ой строке матрицы А(4). далее заменяем )-ю строку матрицы А(4) на Аз д Аз и получаем О 2 5 3 3 2 О 3 4 1 5 3 О 5 2 3 4 5 О 3 3 1 2 3 О Второй метод использует то же самый процесс, записанный в псевдокоде, включая соглашения относительно оо, принятые выше. Единственная разница состоит в том, что в отличие от метода, изложенного выше, в данной ситуации допускается, что Аг» может не быть положительным целым числом.
11-й алгоритм Флойда-Уоршолла Цикл по й от 1 до ьп Цикл по ( от 1 до гц Цикл по ) от 1 до ги Аз = А, д(Аш+Аь ). 622 ГляВА 74. некоторые специальные вопросы теории графов ° УПРАЖНЕНИЯ 1. Используйте алгоритм Дейкстры для нахождения в приведенных ниже графах кратчайшего расстояния между вершинами ио и о. а) б) в) г) д) в 3~г 1 4 "Г~ б 2. Используйте алгоритм Флойда-Уоршолла для нахождения кратчайшего расстояния между вершинами каждого графа из упражнения (1). 3. Используйте алгоритм Дейкстры для нахождения в приведенных ниже графах кратчайшего расстояния между вершинами ио и и.
РАЗДЕЛ 14.5. Вэеешенные графы и алгоритмы поиска кратчайшего пути 623 а) б) б мг 4 " '~чЗ 1~к ~д ° г "о ~ч2 ° гр в) г) г "г гг д) 2 .л "о ° 1 4. Используйте алгоритм Флойда-Уоршолла для нахождения кратчайшего расстояния между вершинами каждого графа из упражнения 3. Ряздел т5. я свойства деревьев 625 ТЕОРЕМА 16.2. Для ориентированного графа С следующие утверждения экви- валентны.
а) С вЂ” корневое ориентированное дерево. б) С имеет единственный такой элемент ео, что для любой вершины а графа С существует единственный ориентированный путь из ео в а. в) Соотнесенный граф графа С связен, и С содержит единственный элемент е' такой, что 1пбей(е') = О, и для любой другой вершины а графа С имеем, 1пс1ец(а) = 1. г) Соотнесенный граф графа С связен, и С содержит единственный элемент ео такой, что для любой вершины а графа С существует единственный путь изео во. ДОКАЗАТЕЛЬСТВО. (а) — (б) Поскольку С вЂ” корневое ориентированное дерево, то существует ориентированный путь из корня ео в любую заданную вершину а, и в силу того, что С вЂ” ориентированное дерево, этот путь единственный.
Корень только один, и если вершина ео обладает тем же свойством, тогда существует путь р из ео в ео и путь р' из ео в ео. Но в таком случае путь рр'р — еще один путь из ео в ео, и между ео и ео существует более чем один путь. (б)- (в) Пусть и' — тот единственный элемент ео, о котором идет речь в пункте (б).
Тогда )идея(е') = О, но если 1пдек(е') ~ О, для некоторой вершины а существует ребро (а,е'). Отсюда существует также путь р из е' в а, и р(а,е')р также является путем из р в а, поэтому между р и а существует более одного пути. Вершина е' — единственная вершина, степень входа которой равна О. Если существует другая вершина е, у которой 1пс(ец(е) = О, тогда между е' и е не существовало бы пути, что противоречит пункту (б). Каждая другая вершина имеет степень входа 1, потому что если вершина е имеет степень входа больше чем 1, тогда для двух различных вершин а и Ь существует ориентированное ребро из а в е и ориентированное ребро из Ь в е. Но существует путь р из е' в а и путь о из е' в Ь, так что р(а, е) и д(Ь, е) — различные пути из е' в е, что противоречит пункту (б).
Соотнесенный граф графа С связный, поскольку для заданных вершин а и Ь существует путь из е' в а и из е' в 6, и, следовательно, в соотнесенном графе существует путь из а в е' и путь из е' в Ь, т.е. существует путь из а в 6. (в)- (г) Очевидно, ео = е'. Согласно пункту (в) для любой вершины графа а существует путь из ео в а. Предположим, что для некоторой вершины а сушествует два пути из ео в а. Пусть Ь вЂ” первая вершина, начиная с которой оба пути из Ь в а совпадают.
Ею может быть и сама вершина а. В этом случае 1пдеК(6) > 1, что противоречит пункту (в). (г) — (а) Предположим, что соотнесенный граф С' содержит два неориентированных пути из вершины е' в вершину а. Если оба пути ориентированы из е' в а, это противоречит гипотезе. Если один путь есть ориентированный путь р из а в е, а другой путь — ориентированный путь о из е' в а, то ярд — также ориентированный путь из е' в а, что противоречит условию единственности пути. Остается только предположить, что один из связных путей из е' в а не является ориентированным путем.
В этом случае в одном из путей для некоторой вершины с существует ребро (Ь,с) и ребро (а,с). Но поскольку существует ориентированный путь р' из е' в 6 и ориентированный путь ре из е' в а, существуют 626 ГЛАВА 15. Деревья различные пути р'(Ь,с) и р"(г(,с) из о' в с, что опять является противоречием. Поэтому неориентированный путь из вершины о' в вершину а единственный. Неориентированный путь из любой вершины а в любую вершину Ь должен быть единственным, так как если бы существовали два пути из а в Ь, то существовали бы два различных пути из о' в а и в Ь или, другими словами, два различных пути из и' в Ь, что неверно. Поэтому С вЂ” ориентированное дерево и, поскольку о" удовлетворяет определению корня, С вЂ” корневое ориентированное дерево.
° В оставшейся части книги рассматриваются только корневые ориентированные деревья; следовательно, под всеми ориентированными деревьями следует понимать корневые ориентированные деревья. Некоторые из приведенных ниже определений для удобства изложения повторены. Обращаем внимание читателя, что во многих учебниках эти определения сформулированы по-другому. ОПРЕДЕЛЕНИЕ 15.3. В ориентированном дереве уровень вершины и — это длина пути от корня дерева до вершины о. Высота ориентрованного дерева — это длина самого длинного пути от корня до листа.
ОПРЕДЕЛЕНИЕ 15.4. т-арным ориентированным деревом назывется такое ориентированное дерево, в котором оп1с(ей(о) ( т для каждой его вершины ш Таким образом, родитель имеет не более т сыновей. Полным т-арным ориентированным деревом назывется такое ориентированное дерево, в котором опЫея(о) = т для каждой его вершины ш не являющейся листом, и каждый лист находится на одном и том же уровне. Таким образом, каждый родитель имеет в точности т сыновей. ОПРЕДЕЛЕНИЕ 15.5. т-арное ориентированное деревом высоты Ь назывется сбалансированным (полным, или почти полным), если уровень каждого листа равен Ь или Й вЂ” 1.
ТЕОРЕМА 15.6. Если полное т-арное ориентированное дерево имеет и вершин и и — 1 г внутренних вершин, то и = тг+ 1. Решая относительно г, получаем 1 = ДОКАЗАТЕЛЬСТВО. Каждая вершина, за исключением корня, является сыном внутренней вершины. Поскольку имеется 1 внутренних вершин и каждая внутренняя вершина имеет т сыновей, всего имеется ат сыновей.
Если учесть корень, то общее число вершин равно ту+ 1. ТЕОРЕМА 15.7. Если полное т-арное ориентированное дерево имеет п вершин, 1 внутренних вершин и 1 листьев, то 1 = (т — 1)1+ 1. Решая относительно г, 1 — 1 получаем г = т — 1 ДОКАЗАТЕЛЬСТВО. По предыдущей теореме число вершин равно и = тг'+ 1. Вычитая 1 внутренних вершин из и = т1+ 1, получаем 1 = п — г = тг'+ 1 — г = (гп — 1)1+ 1 листьев. РАЗДЕП 7З.П Свобства деревьев 627 л~-~ ТЕОРЕМА 15.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
