AOP_Tom1 (1021736), страница 163
Текст из файла (страница 163)
Ташеп) ]ТЬеве (Рапэ, 1951)] с помощью друюго способа (см. упр. б.2.3-32). РАЗДЕЛ 2.3.4.1 1. (В, А, С,Р,В), (В, А, С,Р, Е,В), (В,Р, С, А, В), (В,Р, Е,В), (В, Е,Р,В), (В, Е, Р, С, А, В). 2. Пусть (Ъщ )г»,..., 1о) — путь с минимально возможной длиной от вершины г' к вершине Ъ". Если бы Ъ) = Кв для некоторого 1 ( lс, то путь ()чщ, р;, рл~.г,..., рл) был бы еще короче. 3. (Фундаментальный путь проходит один раз через ребра ев и е», а цикл Сг проходит через них — 1 раз, что в сумме дает нуль,) Путь проходит через такие ребра: е», ег, ев, ег, ев, ело, егц еы, еы. 4. Если утверждение задачи не выполняется, то допустим, что С" является таким подграфом для графа С, который получен в результате удаления каждого ребра е,, для которого Е, = О.
Тогда С" является конечным графом без циклов и с минимул» одним ребром. Поэтому согласно теореме А существует по крайней мере одна такая вершина л', что она является смежной в точности для одной вершины Ъ"'. Пусть е, — ребро, соединяющее вершины 1" и 1', тогда уравнение Кирхгофа (1) для вершины И выглядит как Е, = О, что противоречит определению С . 5. А = 1 + Ев, В = 1 + Ев — Ег, С = 1 + Ев, Р = 1 + Ев — Ев, Е = 1 + Еы — Егц Г = 1 + Е»г + Еы — Ею, С = 1 + Егв, Н = Еы — Ем,,1 = Еы, К = Е(о + Ею, ь = Е~г + Ело+ Его — Егл, Р = Е»в+ Его — Ею, О. = Ею, В = Еы — Еы, Я = Егл.
Замечание. В этом случае с помощью переменных А, В,..., 5 можно выразить также значения Ег, Ел,, Егв. Следовательно, имеется девять независимых решений, и именно поэтому из упр. 1.3 3 — (8) были исключены шесть переменных. 6. (Следующее решение основано на идее о том, что распечатывать л»ажно каждое ребро, которое не образует цикл с предыдущими ребрами.) Используйте алгоритм 2.3.3Е, в котором каждая пара (а„6,) представляет соотношение а; ш 6, в обозначениях этого алгоритма.
Единственное внесенное изменение заключается в печати пар (а„6,), если у ВВ 6 на шаге Е4. Чтобы показать справедливость данного алгоритма, нужно доказать, что (а) алгоритм не выводит на печать ребра, которые образуют цикл, (Ь) если граф 6' содержит по крайней мере одно свободное поддерево, то данный алгоритм распечатает и — 1 ребер. Определим отношение 1 = 6, если существует путь от вершины 1 г до вершины 1'л нли если соблюдается условие у = й. Очевидно, что это отношение эквивалентности, причел» у ш )о тогда и только тогда, когда оно может быть выведено из отноп»ений эквивалентности а» = 6»,..., а ш 6 Утверждение (а) справедливо, потому что алгоритм не выводит на печать ребра, которые образуют цикл с прежде распечатанными ребрами, а утверждение (Ь) справедливо, потому что Рййййт[)») = О только для одного й, если все вершины являются эквивалентныл»и.
Более эффективный алгоритм, однако, должен быть основан на поиске в глубину (см. алгоритм 2.3.5А и раздел 7.4.1). 7. Фундаментальные циклы: Со = ео + е» + е» + ео (фундаментальным путем будет е» + е» + ео); Сл = ев + ев + ег; Св = ев — ег + е»; Сг = ег — е» вЂ” ев; Св = ев — ео — е» вЂ” ег. На основании этого получим Е» —— 1, Ег = Ев -Ев, Ег = Ев — Ег — Ев, Е» = 1+ Ег — Ег — Ев, Ео =1 — Ев 8. На каждом шаге процедуры приведения объединяются две стрелки е.
и е„которые выходят из одного и того же блока, а потому достаточно доказать, что эти действия можно обратить. Таким образом, если состояние ребер е; + ег после их объединения известно, необходимо указать состояние для ребер е; и е. до объединения. При этом люгут существовать три разных случая.
Случай 1 Случай 3 Случай 2 Состояние до е; о О' А В д е д' о е, а' А В д еэ Состояние после а' о" '~АД вЂ” ~ В~ Здесь А, В и С вЂ” вершины или супервершины, а и и )3 — другие потоки, отличные от потока е, + е;. Эти потоки могут быть распределены среди нескольких ребер, хотя здесь показана только одна вершина.
В случае 1 (ребра е, и е, направлены к одному и тому же блоку) можно произвольным образом выбрать ребро е„и тогда ез +- (е, + е;) — е.. В случае 2 (е, и сз направлены к разным блокам) обязательно получим е, е- 8' — а', е, е-,)" — и". В случае 3 (ребро е, является циклом, а е, — нет) обязательно получим е, +- Д' — а', е, 4 — (е, + ег) — еэ. таким обРазом, пРоцедУРа объединениа обРащена во всех трех случаях. Результат выполнения этого упражнения доказывает,что количество фундаментальных циклов в приведенной блок-схеме равно минимальному количеству потоков вершин, измерив которые, можно определить все потоки.
В рассматриваемом примере приведенной блок-схемы достаточно вычигзить только три потока вершин (например, а, с, И), тогда как исходная схема из упр. 7 имеет четыре независимых потока ребер. Всякий раз, когда возникает случай 1, одно измерение можно сэкономить. Аналогичная процедура приведения может быть основана на объединении стрелок, которые направлены на данный блок, а не из него Можно показать, что подобным образом получаеги такую же приведенную блок-схему, но с другими именами супервершин.
Данное построение основано на идеях Армена Нахапетяна (Аппеп Хайарес!ап) и Ф. Стивенсона (Р. Ягегепвоп). Более подробно этот вопрос рассматривается в работе (П. Е. Кпв1й апб Г. Бгегепвоп, В1Т 13 (1973), 313-322]. 10. Если все выводы соединены в единую сеть, то соответствуюший ей граф должен быть связным. При этом сеть с минимальным количеством соединений не будет включать циклов, а потому получится свободное дерево. По теореме Л свободное дерево содержит и — 1 соединений, а граф с и вершинами и п — 1 ребрами является свободным деревом тогда и только тогда, когда ои является связным. 9.
Каждое ребро, выходящее из вершины и сразу же замыкающееся на ней, называется совершенно отдельным фундаментальным циклом. Если существует й + 1 ребер е, е',...,е~ ~ между вершинами Г и Г', построим к фундаментальных циклов е' ш е, ..., бб е~ У х е (выбирая "+" или "—" в зависимости от того, совпадает ли направление обхода (ь)' ребра с направлением стрелки), а затем продолжим работу так, как будто существует только ребро е. Действительно, эту ситуацию можно существенно упростить, если определить граф таким образом, чтобы в ием допускалось наличие нескольких ребер между одинаковыми вершинами, а также определить ребра, концы которых могут замыкаться на одном узле, причем пути и циклы определять на основе ребер, а не вершин, Такая формулировка позволяет дать определение ориентированного дерева, которое приводится в разделе 2.3А.2.
11. Достаточно доказать, что когда и > 1 и минимальное значение с(л, и) равно с(и — 1, и), то существует по крайней мере одно дерево с минимальной ценой, в котором вывод Т„ соединен с Т . (Действительно, для любого дерева с лвинимальной ценой, в котором имеется и > 1 концевых узлов, и с выводом Т л, соединенным с выводом Т„, должно существовать и дерево с минимальной ценой с и-1 концевыми узлами, если расслгатривать выводы Т„л и Т„как "один обобщенный вывод", используя упомянутое в этом алгоритме соглашение.) Для доказательства приведенного выше выражения предположим, что имеется дерево с минимальной ценой, в которолг вывод Т л "не спаян" с Т . Если добавить связующее звено Т л — Т„, то получится цикл, причем в нем можно удалить любое другое связующее звено.
Удалив связующее звено, которое касается вывода Т„, получим другое дерево, общая цена которого не выше исходной цены и в которолг содержится связующее звено Т вЂ” Т. 12. Создайте две вспомогательные таблицы а(л) и Ь(л) для 1 < л < и, в которых Тл|0— самое дешевое соединение между выводом Т, и выбранным выводом, а а(л) — его стоимость. В исходном состоянии а(л) = с(л, и) и Ь(л) = и. Затем выполните следующие операции и — 1 раз: найдите такое значение л, что а(в) = пиал«„а(2); соедините Т, с Тлб>, .для 1 < 1 < и, если с(л, Я < а(г), установите а(1) в — с(л, 1) и Ь(2) +- л; установите а(л) +- со. Здесь с(л, у) означает с(1, л), когда у < л. (В определенной степени эффективнее было бы использовать не оо, а однонаправленный связанный список для таких л, которые еще не были отобраны.
С учетом или без учета этого прямолинейного подхода для выполнения алгоритма потребуется около 0(иэ) операций.) См. также работы Е. 1Ч. Еб)эйвсга, Ргос. г7ег)егб Айасй (Уегепвсй. А63 (1960), 196-199; П. Е. Копей, ТЬе Явапгогс) СгарЛВэве (Вен Уогрс АСМ Ргеш, 1994), 460 — 497. Более совершенные алгоритмы поиска дерева с минимальной ценой рассматриваются в разделе 7.5.4. 13. Если не существует никакого пути от вершины г', до вершины 1'„для некоторого л ~ 1, то никакое произведение транспозиций не сможет переместить л на место 11 Поэтому, если генерируются все перестановки, граф должен быть связным. И наоборот, если граф является связным, при необходимости удаляйте ребра до тех пор, пока не получите дерево.
Затем перенумеруйте вершины так, чтобы вершина Г была смежной только для одной другой вершины, а именно — для 1' л (см. доказательство теоремы А), Теперь все транс- позиции, кроме (и-1 и), образуют дерево с и — 1 вершинами. Поэтому по методу индукции, если я является перестановкой (1, 2,..., и) с фиксированным расположением и, л можно представить в виде произведения этих транспозиций.
Если я переллещает и в положение у) то я(~ и-1)(и-1 и) = р фиксирует положение и. Следовательно, я = р(и-1 и)(у и — 1) можно представить как произведение заданных транспозиций. РАЗДЕЛ 2.3.4.2 1. Пусть (ем,, ., е„) — ориентированный путь от $' к Г'с минимально возможной длиной. Если теперь (пй(е,) = 'шй(ел) для 1 < Ь, то (ен, ..,е; л,ел,,е ) будет кратчайшим путем, и аналогичный аргумент можно использовать, если Йп(ез) = Йп(ел) для 1 < й. Следовательно, путь (еи, е„) является простым. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
