При этом граничное условие, которое заключается в том, что блоки "Начало" и "Конец" обрабатываются в точности один раз, эквивалентно отношению

Ео = 1. (7)

Выше было показано, как получить все решения с помощью закона Кирхгофа. Этот же метод можно применить не только для блок-схем, но и для анализа электрических цепей (именно так поступил и сам Кирхгоф). Естественно было бы спросить, не являются ли законы Кирхгофа наиболее полным возможным набором уравнений, которые можно было бы предложить для описания блок-схем программ. Иначе говоря, можно ли утверждать, что при каждом выполнении программы от блока "Начало" до блока "Конец" можно получить набор величин Ei, £2,...,£27, которые соответствуют количеству проходов по каждому ребру, причем эти величины подчиняются закону Кирхгофа. Но существуют ли решения уравнений Кирхгофа, которые не отвечают никаким вариантам вьшолнения ко.мпьютерной программы? (Здесь предполагается, что об этой программе ничего, кроме блок-схемы, неизвестно.) Если имеются решения, которые удовлетворяют уравнениям Кирхгофа, но не соответствуют реальному выполнению программы, то можно потребовать выполнения более строгих условий, чем законы Кирхгофа. Для электрических цепей Кирхгоф сформулировал следующий второй закон [Ann. Physik und Chemie 64 (1845), 497-514]: сумма падений напряжения в фундаментальном цикле должна быть равна пулю. Но этот закон не применим к данной задаче.

Существует еще одно очевидное условие, которому должны удовлетворять величины Е, если они соответствуют некоторому реальному пути в блок-схеме от блока "Начало" до блока "Конец", а именно: они должны быть целыми числами, точнее, неотрицательными целыми числами. Это вовсе не тривиальное условие, так как нельзя просто приписать произвольные неотрицательные числа независимым переменным Ео, Еь, - , Е2ъ- Например, если взять £2 = 2 и JSg = О, то на основании (6) и (7) получится, что Ег = -1. (Таким образом, нельзя выполнить программу с блок-схемой, представленной на рис. 31, с двойным проходом ребра 62 без обхода ребра eg хотя бы один раз.) Условие неотрицательности значений Е не является достаточным. Рассмотри.м, например, решение, в котором £"9 = 1, Е2 = Е = = Еп = £20 = Е21 = Е2ь = 0. Тогда здесь не существует ни одного пути с проходом по ребру Cig, минуя ребро ехь- Это необходи.мое и достаточное условие является ответом на вопрос, поставленный в предыдущем абзаце: для произвольных значений Е2, Е5,..., JS25 определим Ei,Ez, .., Е27 согласно (6) и (7). Предположим, что все Е - неотрицательные целые числа, а граф с ребрами Cj, для которых Ej > О, и вершинами, которые соединены такими ребрами Cj, является связным. Тогда существ}ет путь от блока "Начало" до блока "Конец", в котором ребро Cj проходится в точности Ej раз. Это утверждение доказывается в следующем разделе (см. упр. 2.3.4.2-24).

Подытожим все приведенные выше рассуждения в следующей теореме.

Теорема К. Если блок-схема (такая, как на рпс. 31) содержит блоков (в том числе блоки "Начало" и "Конец") и т стрелок, то можно найти т-п + 1 фундаментальных циклов и такой фундаментальный путь от блока "Начало" до блока "Конец", что любой путь от блока "Начало" до б.пока "Конец" будет эквивалентен (в отношении количества прохождения каждого ребра) одному обходу фундаментального пути и

единственным образом определенному количеству прохождений каждого фундаментального цикла. (Фундаментальный путь и фундаментальный цикл могут включать несколько ребер, прохождение которых совершается в направлении, обратном тому, которое показано стрелкой на этом ребре. В таком случае будем считать, что прохождение ребер осуществляется -1 раз.)

И наоборот, для любого обхода фундаментального пути и фундаментальных циклов, в которых общее количество прохождений каждого ребра неотрицательно и в которых вершины и ребра, соответствующие положительному количеству прохождений, образуют связный граф, существует по крайней мере один эквивалентный путь от блока "Начало" до блока "Конец".

Поиск фундаментальных циклов осуществляется в результате выбора свободного поддерева, аналогичного показанному на рис. 32. Если выбрать другое поддерево, то в общем случае получим другой набор фундаментальных циклов. Существование т -n-h I фундаментальных циклов следует из теоремы А. Причем модификации, которые выполнялись для схемы, показанной на рис. 31, чтобы получить схему на рис. 32, после добавления ребра ео не изменяют значения т - п + I, хотя при этом могут возрасти значения тип. Такое построение можно было бы обобщить с тем, чтобы полностью избавиться от тривиальных модификаций (см. упр. 9).

Теорема К обнадеживает, поскольку в ней говорится, что закон Кирхгофа (который состоит из п уравнений для т неизвестных Ei, Ег,..., Ет) обладает лишь одной "избыточной переменной": эти п уравнений позволяют исключить тг-1 неизвестных. Однако неизвестные переменные в приведенных выше рассуждениях обозначали количество прохождений ребер, а не количество входов в каждый блок блок-схемы. В упр. 8 показано, как построить другой граф, ребра которого соответствуют блокам блок-схемы, так что описанная выше теория может быть использована для определения истинного числа избыточных переменных.

Способы применения теоремы К в программном обеспечении, используемом для оценки производительности программ на языках программирования высокого уровня, рассмотрены Томасом Боллом (Thomas Ball) и Джеймсом Р. Ларусом (James R. Larus) в работе АСМ Trans. Prog. Languages and Systems 16 (1994), 1319-1360.

УПРАЖНЕНИЯ

1. [Ц] Перечислите все циклы от вершины В до вершины В, которые содержатся в графе, показанном на рис. 29.

2. [М20] Докажите, что если в графе существует путь от вершины V до вершины V, то между этими вершинами также имеется простой путь.

3. [15] Какой Путь от блока "Начало" до блока "Конец" является эквивалентным (в смысле теоремы К) одному проходу фундаментального пути плюс один проход цикла Сг на рис. 32?

► 4. [М20] Пусть С является конечным свободным деревом, в котором стрелки нарисованы на ребрах ei,...,en-i. Пусть Ei,..., En-i-это числа, удовлетворяющие закону Кирхгофа (1) в С. Покажите, что Ei - = En-i = 0.

5. [20] Используя уравнения (6), выразите значения А, В,..., S, которые находятся внутри блоков на рис. 31, с помощью независимых переменных Е2, Еь,..., Е2ь-

► 6. [М27] Допустим, чтограф содержит п вершин Vl,V„ и m ребер ei,... ,ет. Каждое ребро е между вершинами Va и Vi, представлено парой целых чисел (а,Ь). Создайте

максимально эффективней алгоритм, который использует в качестве входного потока пары чисел (ai, bi), ..., (om, bm), a на выходе распечатывает подмножество ребер, которые образуют свободное дереве;. Если это невозможно, алгоритм должен выдать сообщение об ошибке.

7. [22] Выполните описанное в этом разделе построение для блок-схемы

используя для этого свободное поддерево иэ ребер ei, ег, ез, 64, eg. Найдите фундаментальные циклы и выразите Ej, Е2, Ез, Е4, Eg на основании переменных Es, Ее, Ет и Ев-

► 8. [М25] Того, кто применяет закон Кирхгофа для программирования блок-схемы, обычно интересуют потоки через вершины {vertex flows) (т. е. количество прохождений каждого блока для данной блок-схемы), а не потоки через ребра. Например, на схеме в упр. 7 потоки через вершины равны А = Е2 + Е, В = Es, С - Ез + Ет + Eg, D = Ев + Eg.

Если сгруппировать некоторые вершины, рассматривая их как одну "супервершину", можно объединить потоки ребер, которые соответствуют одному и тому же потоку вершины. Например, в показанной выше блок-схеме ребра ег и 64 можно объединить, если Совместить вершины В и D:

(Здесь также от вершины "Начало" до вершины "Конец" проведено ребро ео) Продолжая этот процесс, можно объединить сначала ребра 63+67, затем - (ез +67) -beg и ее 4-eg, пока не получится приведенная блок-схема с ребрами s = ei, а = ег 4- 64, Ь = 65, с = ез -I-67 -l-es, d = ее -I- eg, < = ео, где на каждую вершину исходной блок-схе.мы приходится в точности по одному ребру:

ZJ.4, В, D, Конец Ь

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

Докажите, что процесс приведения блок-схемы можно обратить в том смысле, что любое множество потоков {а,Ъ,...}, которое удовлетворяет закону Кирхгофа в приведенной блок-схеме, может быть "расщеплено" на набор потоков ребер {eo,ei,...} в исходной блок-схеме. Эти потоки ej удовлетворяют закону Кирхгофа, и, если их объединить, можно получить потоки {а,Ь,...}. Причем некоторые из них motjt быть отрицательны.ми. (Хотя здесь показан процесс приведения только для одной частной блок-схемы, данное Доказательство должно выполняться в общем случае.)