Д. Кнут - Искусство программирования том 1 (1119450), страница 102
Текст из файла (страница 102)
Следовательно, можно сделать вывод, что Ео, Ез;Ез,..., Езз являются неэависимыяли в следующем смысле. Если хо,хз,...,хзз — произвольные действительные члсоа (по одному хг для каждого ребра е, которое не входит в свободное поддерево С'), то сУШсствУет такое Решение УРавнешгй КпРхгофа (1), и о Ео = хо, Ез — — хг, ~ Е28 х28. Данное решение получено за 1чет хо-разового обхода цикла Со, х -разового обхода цикла С и т. д. Более того, значения остальных переменных Е1,Ез, Е4.... полно- стью завислт от значений псРеменных Ео, Ег,..., Езз.
(б) Упомянутое в (4) решенно являетсд едпнствснньм1. Если бы существовало два тьких решения уравнений Кирхгофа, прн которых Ео-- хо,..., Едо = хгз, можно было бы вычесть одно решение из другого и таким обРазом полУчить Решение, в котоРом Ео = Ез = Ез = . = Егз — — О. Но тогДа асе Е должны быть равны нулю, так как нетрудно видеть, что нельзя получить ненулевое решение уравнений Кирхгофа для графа, который является свободным деревом (см.
упр. 4). Следовательно, два предполагаемых решения дцожпы быть тождественны. Таким образом, доказано, что все решения уравнений Кархгофа могут быть представлены в виде линейной комбинации решений, полученных па основе фундаментальных циклов. Применяя этн замечания для графа, показанного па рис. 32, получим следующее общее решение уравнений Кирхгофа на основе независимых переменных Ео, Ег,, Езд: (6)' Егд = Егз, Езт = Егт — Еш — Езз. Чтобы полу шть эти уравнения, достаточно для каждого ребра с поддерева пере- ЧИСЛНтЬ ВСЕ тЬКПЕ. Еги дпя КОтОрЫХ рЕбрО Е ВХОднт В ЦИКЛ СЛ, С СООтнстетауК1щнМ знаком. [Итак, матрица коэффициентов системы уравнений (6) является транспонированной по отношеншо к лзатрице коэффициентов системы уравнений (3).[ Строго гоооря, цикл Со не стоит яазывать фундамензпльным, поскольку он содержит особое ребро ео.
Пикл Со без ребра со можно было бы назвать Фуилгамснталыгым пупгеял (гипггаигсп1а1 ра04) олп вершины "Начало" лго вершины "Конец". Ео, Ео — Ез + Ез, Ео — Ег+ Ею Ео — Ез + Ез Ео — Ез + Ез Ео Ео, Ео + Еы — Езы Ео+ Егз: Е1':» Е1 Ез Е4 Ед Ет Ед Его = Ем = Егг = Е[з = Е 4 Егз = Е18 Е1 8 Егд = Е22 = Езз = Егз = Ео, Еы — Егг, Е,т — Еш, Е",д + Езо — Ею, Ем + Езо Е21 Е20, Ег 2 — Ею, При этом гранячное условие., которое заключается в том, что блоки "Начало" и "Конец" обрабатываются в точности один рвз, эквивалентно отношению (7) Выше было показано, как получить все решения с помощью закона Кирхгофа. Этот же метод можно применить не только для блок-схем, но и для анализа электрических цепей (именно так поступил и сам Кирхгоф).
Естественно было бы спросить, не являются ли законы Кирхгофа наиболее полным возможным набором уравнений, которые можно было бы предложить для описания блок-схем программ. Иначе говоря, можно ли утверждать, что при каждом выполнении программы от блока "Начало" до блока "Конец" можно получить набор величин ЕмЕз,...,Езт, которые соответствуют количеству проходов по каждому ребру, причем эти величины подчиняются закону Кирхгофа.
Но существуют ли решения уравнений Кирхгофа, которые не отвечают никаким вариантам выполнения компьютерной программы? (Здесь предполагается, что об этой программе ничего, кроме блок-схемы, неизвестно.) Если имеются решения, которые удовлетворяют уравнениям Кирхгофа, но не соответствуют реальному выполнению программы, то можно потребовать выполнения более строгих условий, чем законы Кирхгофа.
Дня электрических цепей Кирхгоф сформулировал следующий второй закон (Апп. Рцуяй ипо' Сйеппе 64 (1845), .497 — 514]: сумма падений напряжения в фундаментальном цикле должна быть равна нулю. Но этот закон не применим к данной задаче. Существует еще одно очевидное условие, которому должны удовлетворять величины Е, если они соответствуют некоторому реальному пути в блок-схеме от блока "Начало" до блока "Конец", а именно: они должны быть целыми числами, точнее, неотрицательными целыми числами. Это вовсе не тривиальное условие, так как нельзя просто приписать произвольные неотрицательные числа независимым переменнгям Е,Ею...,Етю Например.
если взять Ез = 2 и Ев = О, то на основании (6) и (7) получится, что Ез = — 1. (Таким образом, нельзя выполнить программу с блок-схемой, представленной на рис. 31, с двойным проходом ребра ез без обхода ребра ев хотя бы один рвз.) Условие неотрицательности значений Е не является достаточным. Рассмотрим, например, решение, в котором Е,"э — — 1, Ез = Ев — — .. — — Ем = Езо = Еш = Езв = О. Тогда здесь не существует ни одного пути с проходом по ребру е1в, минуя ребро епь Это необходимое и достаточное условие является ответом на вопрос, поставленный в предыдущем абзаце: для произвольных значений Ез, Ев,..., Евв определим Ем Ез,..., Езг согласно (6) и (7).
Предположим, что все Š— неотрицательные целые числа, а граф с ребрами ем для которых Ет > О, и вершинами, которые соединены такими ребрами ез, является связным. Тогда существует путь от блока "Начало" до блока "Конец", в котором ребро еу проходится в точности Е раз. Это утверждение доказывается в следующем разделе (см. упр, 2.3.4,2-24).
Подытожим все приведенные выше рассуждения в следующей теореме. Теорема К. Еслп блок-схема (такая. как на рлс. ЗЦ содержит и блоков (в гом чцсле блоки "Начало" ц "Конец"') ц т стрелок, то можно найтп ш — и+1 фундаментальных циклов и ~акой фундамелтальлый путь от блока "Начало" до блока "Конец", что любой путь от блока "Начало" до блока "Колец" будет эквивалентен (в отношении количества прохождений каждого ребра) одпомг обходу фундаментального лутц и единственным образом определенному количеству прохождений каждого фундаментального цикла.
(Фундаментальный путь и фундаментальный цикл могут включать несколько ребер, прохождение которых совершается в направлении, обратном тому, которое показано стрелкой на этом ребре. В таком случае будем считать, что прохождение ребер осуществляется — 1 раз.) Л наоборот, для любого обхода фундаментального пути н фундаментальных циклов, в которых общее колпчество прохождений каждого ребра неотрпцательно и в которых вершины н ребрщ ссютветствующие положительному количеству прохождений, образуют связный граф, существует по крайней мере один эквивалентный путь от блока "Начало" до блока "Конец".
э Поиск фундаментальных циклов осуществляется в результате выбора свободного поддерева, аналогичного показанному на рис. 32. Если выбрать другое поддерево, то в общем случае получим другой набор фундаментальных циклов. Существование т — п + 1 фундаментальных циклов следует из теоремы А. Причем модификации, которые выполнялись для схемы, показанной на рис. 31, чтобы получить схему на рис. 32, после добавления ребра ее не изменяют значения т — и + 1, хотя при этом могут возрасти значения т и и. Такое построение можно было бы обобщить с тем, чтобы полностью избавиться от тривиальных модификаций (см.
упр. 9). Теорема К обнадеживает, поскольку в ней говорится, что закон Кирхгофа (который состоит из и уравнений для т неизвестных Е,, Ею..., Е ) обладает лишь одной "избыточной переменной": эти и уравнений позволяют исключить п — 1 неизвестных. Однако неизвестные переменные в приведенных выше рассуждениях обозначали количество прохождений ребер, а не количество входов в каждый блок блок-схемы. В упр. 8 показано, как построить другой граф, ребра которого соответствуют блокам блок-схемы, так что описанная выше теория может быть использована для определения истинного числа избыточных переменных.
Способы применения теоремы К в программном обеспечении, используемом для оценки производительности программ на языках программирования высокого уровня, рассмотрены Томасом Боллом (Т)ьошав Ва!1) и Джеймсом Р. Ларусом (Лешев К. ?лгиэ) в работе АСМ Тгапэ. Ргок. Еапбиайеэ апь1 Еуэгетэ 16 (1994), 1319 — 1360. УПРАЖНЕНИЯ 1. (14] Перечнспите все циклы от верьпины В до вершины В, которые содержатся в графе, показанном на рис. 29. 2.
]М90] Докажите, что еглн в графе существует путь от вершины 1'до вершины $'~, то между этими вершинами также имеется простой путь. 3. (15] Какой путь от блока "Начало" до блока "Конец" является эквивалентным (в смыгле теоремы К) одному проходу фундаментального пути плюс один проход цикла Сэ на рис. 32? 4. (М20] Пусть С' является конечным свободным деревом, в котором стрелки нарисованы на ребрах ем...,е ь Пусть Ем...,Е„ь — это числа, удовлетворяющие закону Кирхгофа (1) в С'.
Покажите, что Еь = = Еь-ь = 9. 6. [20] Используя уравнения (6), выразите значения А, В,..., 5, которые находятся внутри блоков на рис, 31, с помощью независимых переменных Ег, Еь,..., Еэь. 6. (М97] Допустим, что граф содержит п вершин Ъц...,~'„ит ребер ем...,е . Каждое ребро е между вершинами И и 1ь представлено парой целых чисел (а,Ь).
Создайте максимально зффективнсяй алгоритм, который использует в качестве входного потока пары чисел (ас,Ьс), ..., (а', Ьш), а на выходе распечатывает подмножество ребер, которые образуют свободное деревц. Если это невозможно, алгоритм должен выдать сообщение об ошибке, 7. (22) Выполните описанное в этом разделе построение для блок-схемы используя для этого свободное поддерево из ребер ес, ег, ез: ев, ев. Найдите фуидаментальные циклы и выразите Ес, Ег, Ез, Ес, Ев на основании переменных Ез, Ев, Ет и Ев.
8. (Мхб] Того, кто применяет закан Кирхгофадля программирования блок-схемы, обычно интересуют потоки через еврсиины (овгтех /)овгз) (т, е. количество прохождений каждого блока для данной блок-схемы), а не потоки через ребра. Например, на схеме а упр. 7 потоки через вершины равны А = Ег + Ев, В = Ез, С = Ез + Ет + Ев, Р = Ев + Ев. Если сгруппировать некоторые вершины, рассматривая их как одну "супервершину", можно объединить потоки ребер, которые соответствуют одному и тому же потоку вершины.
Например., в показанной выше блок-схеме ребра ег и ес можно объединить, если совместить вершиссьс В и Р: (Здесь также от вершины "Начало" до веригины "Конец" проведено ребро ео ) Продолжая этот процесс, можно объединить сначала ребра ез+ет, затем — (ез+ет)+ев и ее+ее, пока не получится приведенная блок-схвзса с ребрами в = ес, а = ег + ес, Ь = ез, с = ез + ет -г ее, Н = ев т ев, Г = ео, где на каждую вершину исходной блок-схемы приходится в точности по одному ребру: По построению в приведенной блок-схеме закон Кирхгофа соблюдается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
