представляет отдельный шаг вычислений, а буква или число внутри него - количество вычислений, KOTopbte выполнялись на этом шаге во время работы программы, согласно обозначениям из раздела 1.3.3. Стрелка между блоками указывает на возможность перехода в Программе. Все они отмечены символами ei,сг,..., 627. Теперь задача заключается в том, чтобы на основе закона Кирхгофа найти все отношения между величинами А, В, С, D, Е, F, G, Я, J, К, £, Р, Q, R и S, а. также глубоко проникнуть в суть общей задачи. {Замечание. Некоторые упрощения этой задачи у*е внесены непосредственно на рис. 31. Например, блок между С и Е уже содержит число "1", что является следствием закона Кирхгофа.)

Пусть Ej обозначает количество попыток обхода ветви Cj во время выполнения данной программы. По закону Кирхгофа

сумма величин Е на входе в блок = значение внутри блока . ,

= сумма величин Е на выходе из блока.

Например, для блока К получим

£19 + £20 = К = Ei8 + Е21 (2)

В дальнейшем неизвестными будем считать Ei,E2,. .£27, а не А, В,... ,S.

Блок-схему на рис. ЗТможно представить в еще более абстрактном виде, т. е. в виде графа G, как показано на рис. 32. Блоки превратились в вершины, а стрелки 61,62,... теперь представляют собой ребра графа. (Строго говоря, ребра графа не указывают направления, а потому направление стрелок следует игнорировать при рассмотрении теоретических свойств графа G. Однако, как будет показано ниже, стрелки понадобятся при использовании закона Кирхгофа.) Дополнительно ребро ео, которое проходит от вершины "Начало" до вершины "Конец", вводится для удобства, чтобы закон Кирхгофа был одинаково применим для всех частей графа. В схеме на рис. 32 также внесено несколько изменений по сравнению с блок-схемой, показанной на рис. 31. Дополнительная вершина и ребро добавлены для разбиения стрелки ехз на две, и е/з, чтобы соблюдалось основное определение графа (две вершины могут соединяться только одним ребром). Такому же разбиению подверглась и стрелка ejg. Аналогичную модификацию схемы следовало бы сделать также для любой вершины со стрелкой, указывающей на эту же вершину.

Некоторые ребра, представленные на рис. 32, выделены более жирным начертанием по сравнению с остальными. Они образуют свободное поддерево данного графа, соединяющее все его вершины. В графе блок-схемы всегда можно найти свободное поддерево, поскольку такие графы должны быть связными и согласно п. (Ь) теоремы А, если связный граф G не является свободным деревом, в нем можно удалить ребро и получить граф без потери связности. Этот процесс можно повторять до тех пор, пока не будет получено искомое поддерево. Другой алгоритм поиска свободного поддерева рассматривается в упр. 6. В любом случае прежде всего следует устранить ребро ео (которое проходит от вершины "Начало" до вершины "Конец"). Таким образом, можно предположить, что ео в выбранном поддереве отсутствует.

Пусть G - свободное поддерево графа G, найденное таким образом. Рассмотрим произвольное ребро V - V графа G, которое отсутствует в графе G. Тогда можно от.метить важное следствие из теоремы А: граф G и его новое ребро V - V содержат цикл. Действительно, и.меется в точности один цикл вида {V, V,... ,V),

Рис. 32. Граф со свободным поддеревом, соответствующий блок-схеме на рис. 31.

поскольку существует уникальный простой путь от вершины V до вершины V в графе С. Например, если С является свободным деревом, показанным на рис. 32, то, добавив ребро ег, получим цикл, который сначала проходит через ребро ег, а затем (в противоположном направлении по отношению к указанным стрелкам) через ребра и ез. Этот цикл можно записать в алгебраическом виде "ег - е4 - ез", используя знаки "плюс" и "минус" для обозначения направления обхода, когда он совпадает или не совпадает с направлением стрелок.

Если вьшолнить этот процесс для каждого ребра, которое не входит в свободное дерево, получатся так называемые фундаментальные циклы {fundamental cycles), которые для схемы, показанной на рис. 32, выглядят так:

Со + ei + ез + е4 + Сб + ет + eg + ещ + ец -I- еаг + ец,

e-i - Ci- ез,

еь-ет - 66,

eg + ез -I-е4 -I-ее +€7,

= 12

+ е\з.

Со Сг Cs Cs

Сп: 617 + 622 + ег4 + ег7 + ец -I- eis -I- eie, CiV е19 + eg -I- е,9, Сго: его + ei8 + 622 + егз,

Сг1: 621 - ei6 - ei5 - ец - ег7 - ei - сгг - cis,

С25: 625 + 626 - 627-

Очевидно, что ребро Cj, которое не входит в свободное поддерево, будет представлено только в с15упдаментальных циклах, а именно - в циклах Cj.

Теперь мы вплотную приблизились к кульминационному моменту этого построения. Каждый фундаментальный цикл представляет решение уравнений Кирхгофа. Например, решение, соответствующее циклу Сг, выглядит как = +1, Ец = -1, Ез - -1, а соответствующие всем остальным циклам - как Е - 0. Ясно, что

коэффициенты вдоль цикла в графе всегда удовлетворяют условию (1) закона Кирхгофа. Более того, уравнения Кирхгофа являются "однородными", так. что сумма или разница решений уравнений (1) также является решением. Следовательно, можно сделать вывод, что Ео,Е2,-Е,Е2ь являются независимыми в следзющсм смысле.

Если хо,Х2,. ,Х2ь-произвольные действительные числа (по одному Xj для каждого ребра Cj, которое не входит в свободное поддерево G), то существует такое решение уравнен1п"1 Кирхгофа (1), что Ео = xq, Е2 - Х2,

Е2Ь = Х2Ь-

Данное решение получено за счет хо-разового обхода цикла Со, х-д-разового обхода цикла Со и т. д. Более того, значения остальных переменных Е\,Ег,Е<1 полностью зависят от значений переменных Ео, £2, - , Е25.

Упомянутое в (4) решение является единственным. (5)

Если бы существовало два таких решения уравнений Кирхгофа, при которых Ео = Xq,..., Е25 = Х25, можно было бы вычссть ОДНО рсшенио из другого и таким образом получить решение, в котором Ео = Е2 = Е5 = • • = Eos = 0. Но тогда все Ej должны быть равны нулю, так как нетрудно видеть, что нельзя получить ненулевое решение уравнений Кирхгофа для графа, который является свободным деревом (см. упр. 4). Следовательно, два предполагаемых решс1шя до.пжпы быть тождественны. Таки.м образом, доказано, что все решения уравнений Кирхгофа могут быть представлены в виде линейной комбинации реше1шй, полученных на основе фундаментальных циклов.

Применяя эти замечания для графа, показанного па рис. 32, получи.м следующее общее решение уравнений Кирхгофа на основе независимых перемен-

(6)-

Чтобы получить эти уравнения, досгато1Ц10 для каждого ребра Cj поздерсва перечислить все такие Ef., для которых ребро Cj в.ходит в цикл Ck, с соответствук>щим знаком. [Итак, матрица коэфс15ициентов системы уравнений (6) является транспонированной по отлошеншо к матрице коэффициентов cbcto.mjj у])авпсций (3).]

Строго говоря, цикл Со не стоит называть фу11дамент;ип>ным, поскольку он содержит особое ребро ео. Цикл Со без ребра со можно было бы назвать фундаментальным путем {fundamental path) от вершины "Hauojio до вершины "Конец".