Графы и программы

18

В. Евстгенев

Графы и программы

Теория графов оформлясь как самостоятельная ветвь математики в середине тридцатых годов и продолжает интенсивно развивать по сея день. Большой интерес к теории графов сегодия основан в первую очередь на ее широких и плодотворных применениях к проектированию и анализу сложных систем самой различной природы: трансportных сетей, электрических цепей, электронных схем, механических систем, химических реакций, управляющих систем, социальных групп и коллективов и т. д.

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

Графы и ориентированные графы

Граф — это набор элементов, неокторые пары которых выделены. Граф $G$, таким образом, определяется двумя множествами:

$$G = (X, U);$$

первое состояние из элементов произвольной природы (они называются вершинами), а второе — из всех выделенных пар вершин. Если каждая выделенная пара упорядочена, граф $G$ называется ориентированным графом или орерафом, пары называют дуемами; говорят, что дуга $(x, y)$ направлена от своего начала $x$ к своему концу $y$ и пишут

$$U \ni u = (x, y).$$

В этом случае говорят еще, что дуга и исходит (выходит) из $x$ и заходит (входит) в $y$. Изображают орграф на плоскости в виде точек, соединенных дугами со стрелками (рис. 1). Заметьте на этом рисунке, что дуга, выходящая из вершины $x_3$, заходит в нее же; такая дуга называется netлей.

Если пары $(x, y)$ не упорядочены, то их называют ребрами, вершины ребра $u = \{x, y\}$ называются концами, а сам граф $G = (X, U)$ называется неориентированным графом или протего графом. Пример такого графа — так называемый граф Петерсона — показан на рисунке 2.

Граф данной программы

Пусть дна неоктора программы $P$, например, в виде блок-схемы («Алгебра 8», п. 50). Сопоставим каждому блоку вершину графа и соединним вершины в соответствий с последовательностью действия (указанной стрелками) в блок-схеме. Полученный орграф называем operафом проекции $P$ или $p$-графом.

Упражнение 1. Нарисуйте $p$-граф, отвечающий блок-схемы программных сортировки шаров, показанной на рисунке 3.

Если программа $P$ записана на каком-либо алгоритмическом языке,

Рис. 1.

Рис. 2.

19

то ей тоже можно сопоставить некоторый $p$-граф: каждый оператор отвечает вершина, две вершины $a$ и $b$ соединяются другой $(a, b)$, если управление передается от оператора, изображенного вершиной $a$, к оператору, изображенного вершиной $b$.

Еще один пример $p$-графа показан на рисунке 4. Обратите внимание на две особые вершины: $x_{0d}$ ($s$) (соответствующий входным данным программмы), в которых не заходит ни одна дуга, и $b_{1x0d}$ ($t$) (соответствующий выходным данным программмы), из которого не исходит ни одна дуга.

На данной $p$-графе $G = (X, U)$ (и вообще на любом орграфе) часто рассматривается путем, если в нем вершины не повторяются, контуром, если $a = b$, и простым контуром, если $a = b$, но других повторений вершин нет. Так, на рисунке 4 путь $(x_1, x_3, x_6, t)$ — простой, $(x_1, x_4, x_6, x_3, x_6, t)$ — не простой путь, $(x_3, x_6, x_3)$ — простой контур, $(x_3, x_6, x_3, x_6, x_3)$ — контур, но не простой, $(x_2, x_7, x_6)$ — даже не путь.

Рис. 3.

Рис. 4.

Уражнение 2. Перечислите все простые пути и все простые контуры $p$-графа, построенного при решении упражнения 1.

Все ли пути ведут в Рим?

В $p$-графе, отвечающем хорошо составленной программы, «все пути ведут в Рим», то есть любой путь с началом в $s$ можно продолжить до выхода $t$, обозначающего конец работы программы. Поэтому $p$-граф естественно называется правильным, если любая вершина лежит на пути (не обязательно простом), ведущем из $s$ в $t$.

Конечно, правильность $p$-графа еще не гарантирует успешную работу программы: если в нем есть хотя бы один контур, из которого не выходит ни одна дуга, программа может зациклиться, то есть крутится по этому контуру. Но так как не существует общого алгоритма, проверяющего правильность работы программы (об этом мы рассскажем в «Кванте» в другой раз), важно проверять хотя бы правильность $p$-графа.

Как проверить правильность $p$-графа? В простых случаях это легко делается «вручную».

Уражнение 3. Проверите правильность $p$-графа программы сортировки шаров (см. упражнение 1). Удостоверться в неправильности $p$-графа на рисунке 5, найти неем «тупики», «тупиковые контуры» и «недоступные контуры».

В сложных же случаях, например, в современных больших программах,ручная проверка слищом трудемка и ненадежна — приходит прибегать к помощи ЭВМ. Поэтому необходимо иметь подходящие для этой цели алгоритмы. Задачу о построении таких алгоритмов мы сформулируем в виде трех упражнений (4—6) и для первого из них подскажем решение.

20

Рис. 5.

Уражнение 4. Найти все простые пути, соединяющие вход $p$-графа с его выходом.

Один из наиболее красивых алгоритмов для решения этой задачи основан на последовательном устройении вершин $p$-графа. На рисунке 6 показано его применение к $p$-графу из рисунка 4. На каждом шагуSTRAЯЕТСЯ одна из вершин $x \in X$ (отличная от $s$ и $t$); вместе простых путей, соединяющих вершины, соседние с $x$ и проходящие через $x$, строится новая дуга (рядом с которой записьается название удаленной вершины). Возникающие в этом процессе петли отбрасываются. В результате получается набор дуг, соединяющих $s$ с $t$, притом на каждой из этих дуг последовательно выписаны вершины, через которых разделяется найти алгоритмы, решающие управнения 5, 6. Записать их можно в виде блок-схемы, в таблином виде («Алгебра 8», п. 49) или, для учащихся ЗШП, на языке Рапира.

Уражнение 5*. Найти все простые контуры $p$-графа.

Уражнение 6*. Построить систему путей (не обязательно простых), соединяющих вход $p$-графа с его выходом, покрывающим все вершины $p$-графа. Построить минимальный по числу путей) такую систему.

Оргraph арифметического выражения

При вычислении арифметических выражений на ЭВМ в произвольном порядке, когда этих выражений много и они достаточно громоздки, исходные данные и промежуточные результаты вычислений могут занять недопустимо большой объем памяти ЭВМ; как говорят программисты, «программа забивает оперативную память машины». Как с этим бороться? Здесь на помощь приходит теория графов.

Оказывается, с каждым арифметическим выражением можно свя-

ПРОСТЫЕ ПУТИ:

$s x_1 x_3 x_6 t$
$s x_1 x_4 x_6 t$
$s x_2 x_7 t$
$s x_2 x_5 x_7 t$

Рис. 6.

21

зать орграф специального вида. Например, с выражением
$$((a+b) \cdot (c-d)) / (g+f) + h = L$$
можно связать граф, показанный на рисунке 7. Если в формуле буквы не повторяются, подобные графы имеют специальное название. Ордеревом (ориентированным деревом) называется граф, в котором выделена одна вершина — корень ордерева и от любой другой вершины ордерева к корню идет единственный путь. Из корня ни в одну вершину путь нет.

Так, в нашем примере (см. рис. 7) показано ордерево с корнем $L$. Вершины $a, b, c, d, f, g, h$ называются высчиним.

Упражнение 7. Построите ордерево выражения
$$\frac{\sqrt{x+y}}{z^2+5at+7k} + \frac{b+c}{r} = L.$$

Возвращаясь к рисунку 7, представим себе, что отдельные операции производятся в момент времени, показанные красными вертикальными линиями. Тогда в памяты приходит дережать до 6 чисел одновременно. Правда, это число можно сизить до 4, если в памяти числа $g, f$ в момент времени $t=2$ (вместо $t=1$).

Нельзя ли изобразить наше выражение еще более экономным (в этом смысле) ордерево?

Протащим верблюда через игольное ушко

Рассмотрим дискретную шкалу времени $t=1, 2, 3, \dots$. Пусть вычислительной процесс организован так, что ячейки памяты заполняются (вводятся исходные данные, записываются вычисленный промежуточный результат и т. д.) в целочисленные моменты времени и оставятся занятыми в течение нескольких интервалов времени выбранной шкалы. Когда содержимое ячейки используется, она освобождается. Предположим также, что в каждой момент времени производится засылака только в одну ячейку памяты. Последнее условие позволяет занумеровать вершины соответствующего ордерева,

Идей построения укладок ордерева, шклина которых мала, была высказана А. П. Erшовым в 1958 году и оказалась чрезвычайно полезной. Для сложных задач удаются также узкие укладки, что впору готовить о протакивании верблюда через игольное ушко!

22

висячая, переходим к шагу 4, в противном случае — к шагу 5.

Шаг 4. Во втором столбце пшем 0, в третьем — x. (Таким образом, мы положили $p(x) = 0, q(x) = x$.) Переходим к шагу 3.

Шаг 5. Пусть $y_1, y_2, \dots, y_k$ — вершины ордерева, неосредственно предшествующие x, упорядоченные так, что $p(y_1) \geq p(y_2) \geq \dots \geq p(y_k)$. Найдем
$$p(x) = \max_{1 \leq s \leq k} \{p(y_s) + s - 1\}$$
$$q(x) = q(y_1)q(y_2) \dots q(y_k)x,$$
и внесем найденные значения во второй и третьий столбцы расматриваемой строки. Переходим к шагу 3.

Рис. 8.

Рис. 9.

Один из алгоритмов построения таких укладок, известный под названием alгоритма Реджеевского, мы сейчас описем.

Шаг 1. Построим таблицу с n строками и треяя стольцами, где n — число вершин ордерева.

Шаг 2. Заполним первый столбец таблицы сизу вверх, помещив в самой нижней строке корень $x_0$ ордерева, затем в произвольном порядке его предшествников, лишь бы нигде не нарушалась очередность вычислений (то есть любые данные, нужные для очередной операции, должны быть получены равше ее выполнения).

Далее через $p(x)$ и $q(x)$ мы будем обозначать записи во втором и третьем столбах строки, начинаяшейся с буквы x. Значениями функции $p$ будут числа, функция $q$ — последовательности букв. Пусть уже заполены r первых строк.

Шаг 3. Приступаем к заполнению очередной строки (предыдущие уже заполнены); обозначим через x ее первую букву. Если вершина x —

Повторяем шаги 3—5, пока не будет заполнен все таблица. Тогда в последней строке во втором столбце мы получим ширину укладки, то есть $p(x_0) = W(Y, T)$, а в третьем — саму укладку ордерева T, если вершины в последовательности $q(x_0)$ занутеровать слева направо.

Tabлица, полученная при применении алгоритма Реджеевского к ордереву на рисунке 7, показана на рисунке 8, а «уложенное» ордерево — на рисунке 9.

Упражнение 9. Примените алгоритм Реджеевского к ордереву, полученной в упражнения 7.