AOP_Tom1 (1021736), страница 104
Текст из файла (страница 104)
Тогда можно отметить важное следствие из теоремы А; граф С' и его новое ребро à — 1" содержат цикл. Действительно, имеется в тиочности один цикл вида (1; Г',..., 1'), Рис. 32. Граф со свободным поддеревом, соответствующий блок-схеме иа рис. 31. поскольку существует униквлъный простой путь от вершины Рч до вершины К в графе С'. Например, если С' является свободным деревом, показанным на рис. 32, то, добавив ребро ег, получим цикл, который сначала проходит через ребро ег, а затем (в противоположном направлении по отношению к указанным стрелкам) через ребра е4 и ег. Этот цикл можно записать в алгебраическом виде "ег — е4 — ег ', используя знаки "плюс" и "минус" для обозначения направления обхода, когда он совпадает или не совпадает с направлением стрелок.
Если выполнить этот процесс для каждого ребра, которое не входит в свободное дерево, получатся так называемые фундаментааьиме циклы (уппдатепса( срс1ев), которые для схемы, показанной иа рис. 32, выглядят так: Со: ео+е1+ез+е4 Сг: ег — е4 — ег Св' ев — ет — ев, СВ. .ев + ев + ев + ев и . л С12 е12+ егг+е12 С1т1 е1 т + егг + ег4 + л и Ф 191 Е19 + Е19 + Е19 Сго: его + етв + егг + Сг11 ЕШ вЂ” Ега — ЕШ— Сгв: егв + егв — егт. + ее+ ет+ев+ето+ем +егг+ем, +ет, (3) егт + е„+ е1 в + етв „ Егг Е!1 Е27 Е24 Е22 Е19 Очевидно, что ребро е, которое не входит в свободное поддерево, будет представлено только в фундаментальных циклах, а именно — в циклах С..
Теперь мы вплотную приблизились к кульминационному моменту зтого построения. Кансдый фундаментальный цикл представляет решение уравнений Кирхгофа. Например, решение, соответствующее циклу Сг, выглядит как Ег = +1, Е4 = — 1, ЕВ = — 1, а соответствующие всем остальным циклам — как Е = О. Ясно, что коэффициенты вдоль цикла в графе всегда удовлетворяют условию (1) закона Кирхгофа. Более того, уравнения Кирхгофа являются "однородными", так.что сумма или разница решений уравнений (1) также является решением. Следовательно, можно сделать вывод, что Ео, Ез;Ев,..., Егв являются независимыми в следующем смысле.
Если хо,хз,...,хзв — произвольные действптелы»ые числа (по одному хг для каждого ребра е., которое не входит в свободное поддерево С'), то существует такое, решение уравнений Кпрхгофа (1), что Ео = хо, Ег — — хз, ..., Езв — хзв. (4) Данное решение получено за счет хо-разового обхода цикла Со, х.-разового обхода цикла С и т. д.
Более того, значения остальных переменных Ег, Ез, Е».... полно- стью зависят от значений переменных Ео, Ег,, Егз (6) Упомянутое. в (4) роше»»ггс является едннственныл». Ем— Еш = Е|в = (6) Езо - Езм Езо ~ Егв = Чтобы полу шть эти уравнения, достаточно для каждого ребра гг поддерева перечислить все такие Ев, для которых ребро е входит в цикл Св, г соответствуя щим знаком.
(Итак, матрица козффициентов системы уравнений» (6) является транспонированной по отношению к матрице коэффициентов системы у»элвпег»ий (3).) Строго говоря, цикл Со не стоит называть фундалигнзильным, поскольку он содержит особое ребро ео. 1(икл Со без ребра го можно было бы назвать Фундамснтальнмг» тгу»ггем ()и»г»(атепза( рай) от першин»» "На"»ало' до верши»»ы "Конец". Если бы существовало два таких решения уравнений Кирхгофа, прн которых Ео —— хо,, Езв — — хзв, можно было бы вычесть одно решение из другого и таким об- разом получить решение, в котором Ео = Ез = Ез = .
—— Езз — — О. Но тогда осе Е должны быть равны нулю, так как нетрудно видеть, что нельзя получить ненулевое решснис уравнений Кнрхгофа для графа, который является своГюд»»ым деревом (см. упр. 4). Следонятелыю, два предполагаемых решения должны быть тождественны. Таким образом, доказано, что все решения уравнений К»1>хго»)га могут быть пред»тавлены в виде линейной комбинации решений, полученных на основе фундаментальных циклов. Применяя зтн замечания для графа, показанного па рис.
32, полу'шм сле- дующее общее решение уравнений Кирхгофа на основе нсзависнмых перемен- ных Ео, Ег,..., Езз .' Е» = Ео, Е~» = Ео, Ез = Ео — Ез+ Ев, Ег,, Е» = Ео — Ег + Ев, Егв = Еш — Ез», Ев = Ео — Ез+Ев, Его+ Его — Е ы Ет = Еа — Ез + Ев, Е,'в = Е»в, Ев = Ео Езг = Е»т+ Ею — — Ео, Егз = Е„= Ео + Еы — Ез,, Еьч — — Е,т — Еш, Е»з = Ео+ Е~'з: Езз Ез=Е,", Езт = Ем — Е» — Езв. При этом граничное условие, которое заключается в том, что блоки 'Начало" и "Конец" обрабатываювгя в точности один раз, эквивалентно отношению (7) Ео = 1.
Выше было показано, как получить все решения с помощью закона Кирхгофа. Этот же метод можно применить не только для блок-схем, но и для анализа электрических цепей (именпо так поступил и сам Кирхгоф). Естественно было бы ю:просить, не являются ли законы Кирхгофа наиболее полным возможным набором уравнений, которые можно было бы предложить для описания блок-схем программ.
Иначе говоря, можно ли утверждать, что при каждом выполнении программы от блока "Начало" до блока "Конец" можно получить набор величин Ею, Ег,..., Егг, которые соответствуют количеству проходов по каждому ребру, причем эти величины подчиняются закону Кирхгофа. Но существуют ли решения уравнений Кирхгофа, которые не отвечают никаким вариантам выполнения компьютерной программы'? (Здесь предполагается, что об этой программе ничего, кроме блок-схемы, неизвестно.) Если имеются решения, которые удовлетворяют уравнениям Кирхгофа, но не ю:оотвотствуют реальному выполнению программы, то можно потребовать выполнения более строгих условий, чем законы Кирхгофа.
Для электрических цепей Кирхгоф сформулировал следующий второй закон (Апп. Р?юуаюй ююпю? Сйепне 64 (1845)ю 497 — 514): сумма падений напряжения в фундаментальном цикле должна быть равна нулю. Но этот 'закон не применим к данной задаче. Существует еще одно очевидное условие, которому должны удовлетворять величины Е, если они соответствуют некоторому реальному пути в блок-схеме от блока "Начало" до блока "Конец", а именно: опи должны быть целыми числами, точнее, неотрицательными целыми числами. Это вовсе не тривиальное условие, так как нельзя просто приписать произвольные неотрицательные числа независимым переменным Ег,Е;....,Егв. Например. если взять Е = 2 и Еэ = О, то на основании (6) и (7) получится, что Ег = — 1. (Таким образом, нельзя выполнить программу с блок-схемой, представленной на рис. 31, с двойным проходом ребра ег без обхода ребра еэ хотя бы один раз.) Условие неотрицательности значений Е не является достаточным.
Рассмотрим, например, решение, в котором Е",э = 1, .Ег = Еэ = . ' = Ею! = Его = Ег! = Егь — — О. Тогда здесь не суюцествует ни одного пути с праходом по ребру. еюю минуя ребро ець Это необходимое и достаточное условие является ответом на вопросю поставленный в предыдущем абзаце: для ююроизвазью!ых значений Ег, Ьв,..., Егз определим Ею, Егю ., ., Ег! сюнласно (6) н (7). Предположим, что все Š— неотрицательные целые числа, а граф с ребрами ею, для которых Е.
) О, и вершинами, которые соединены такими ребрами е, является свлаююмм. Тогда существует путь от блока "Начало" до блока "Конец", в котором ребро е проходится в точности Е; раз. Это утверждение доказывается в следующем разделе (см. упр. 2.3.4.2-24). Подытожим все приведенные выше рассуждения в следующей теореме. Теорема К.
Если блок-схема (такая. как на рпс. 31) годержюютп блоков (в том числе блоки "Начало" п "Конец" ) п т, стрелок, то можно найти т-тю+1 фундаментальных циклов п такой фундаментальньюй юп ть от блока "Начало" до блока "Конец", что любой путь от блока "Начало" до блока "Конец" будет эквивалентен (в отнопюешпю количества прохождешш каждого ребра) одноююу обходу фундаментального ююупю п единственным образом определенному количеству прохолСденнй каждого фундаментального цикла, (Фундаментальный путь и фундаментальный цикл могут включать несколько ребер, прохождение которых совершается в направлении„обратниом тому, которое показано стрелкой на этом ребре.
В таком случае будем считать, что прохождение ребер осуществляется — 1 раз.) И наоборот, для любого обхода фундаментального пути я фундаментальных циклов, в которых общее количество прохождений каждого ребра неотрицательио я в которых вершины и ребра, соответствуюгдпе положительному количеству прохождений, образуют связный граф, существует по крайней мере один эквивалентный путь от блока "Начало" до блока Конец". $ Поиск фундаментальных циклов осуществляется в результате выбора свободного поддерева, аналогичного показанному на рис.
32. Если выбрать другое поддерево, то в общем случае получим другой набор фундаментальных циклов. Существование т — и + 1 фундаментальных циклов следует из теоремы А. Причем модификации, которые выполнялись для схемы, показанной на рис. 31, чтобы получить схему на рис. 32, после добавления ребра ее не изменяют значения гп — и + 1, хотя при этом могут возрасти значения т и и. Такое построение можно было бы обобщить с тем, чтобы полностью избавиться от тривиальных модификаций (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
