SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Учебный процесс
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


Орграфы и булевы формулы


© 2003 г. Б. П. Кузнецов

(С.-Петербург, НПО "Аврора", kbp@rednet.ru)

Традиционным не графическим формализованным способом задания орграфов считается матричное представление. Попытка формульного описания орграфа, названного "правильной скобочной структурой" представлена в [1]. Однако, это частный случай описания поиска в глубину орграфа без петель. Другой частный случай показан в [2], где так называемый линейный бинарный граф (ЛБГ) взаимно однозначно описывается булевой формулой (БФ) в базисе И, ИЛИ, НЕ. ЛБГ - строго упорядоченная структура и также не содержит петель. Кроме того, там же представлены и алгоритмы получения ортогональной дизъюнктивной нормальной формулы (ОДНФ) как из ЛБГ, так и из БФ. В [3] показано, что ОДНФ представляет собой минимальный набор тестов, проверяющих программу, реализующую БФ (ЛБГ).

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

Будем рассматривать только такие орграфы, каждая вершина которого содержит петлю (это вполне соответствует графам переходов конечных автоматов, используемых при программировании [4]).

Возможны два подхода к представлению орграфа БФ: на базе дизъюнкций и на базе конъюнкций. Вначале рассмотрим первый подход на примере орграфа, показанного на рис. 1. Этот граф: G(V,X), V = {1,2,3,4,5}, X = {Xij}, (i,j = 1,…,5) - сильно связен, то есть имеет все дуги, связывающие каждую вершину с каждой другой вершиной и самое с собой. Для подобных графов из произвольного числа вершин предложим канонический метод синтеза БФ. В обеспечение этого подхода введем некоторые условности.

f01.gif

На рис.2,а показана вершина i графа G, а на рис. 2,б - фрагмент ЛБГ дизъюнкции, реализующий только две дуги из этой вершины. Дуге "0" ЛБГ соответствует дуга Xij графа G, но дуге "1" ЛБГ назначено отрицание дуги Xij, которому условимся приписывать дугу Xi1, полагая 1 - начальная вершина графа G, то есть, имеем условность вида 

А:            ~Xij -> Xi1

Ниже эта условность обретет свой смысл.

f02.gif

ЛБГ и соответствующую БФ, описывающую граф G, будем строить посредством поэтапной декомпозиции. Начнем с рассмотрения подграфа G1 графа G, состоящего из единственной начальной вершины 1 с единственной дугой - инцидентной этой вершине петлей X11. Сопоставим ей фрагмент ЛБГ из единственной вершины с дугами "0" и "1", помеченными, как следует из введенной условности так: нулевая дуга - X11, а единичная - ~X11 . Этому фрагменту ЛБГ, который обозначим как L1, соответствует БФ вида F1 = ~X11.

Каждый последующий этап заключаются в: 

- выделении нового подграфа, содержащего уже рассмотренные вершины и одну новую вершину с дугами, инцидентными всем включенным в подграф вершинам, 

- получении соответствующего фрагмента ЛБГ и фрагмента БФ, 

- конкатенации этих фрагментов с ранее полученными, соответственно, ЛБГ и БФ. 

Рассмотрим эти построения подробно.

Рассмотрим подграф G2 графа G, включающий вершины 1 и 2 с инцидентными им и только им дугами X11, X12, X22, X21 (рис. 3,а). Этому подграфу поставим в соответствие ЛБГ L2 (рис.3,б), описываемому БФ вида: e01.gif. Данный ЛБГ L2 однозначно соответствует подграфу G2 с учетом ранее указанных условностей. В обеспечение канонизации преобразования графа в ЛБГ и БФ соединим ЛБГ L2 (рис. 3,б) с ЛБГ L1 , описывающим начальную вершину, согласно рис. 4. Полученной композиции e02.gif взаимно однозначно соответствует ЛБГ e03.gif, которому взаимно однозначно соответствует БФ вида e04.gif. Последняя описывает G12 (рис. 3,а).

f03.gif
f04.gif

Поясним полученный результат путем преобразования ЛБГ L12 в эквивалентную дизъюнкцию ОДНФ БФ и ее инверсии, перечисляющей все пути в этом ЛБГ [3]:

e05.gif

Данная ОДНФ естественно избыточна, в частности, может быть опущен предпоследний член дизъюнкции. Из рассмотрения O12 следует, что каждая дуга G12 и, естественно, каждая вершина упомянуты хотя бы один раз, то есть, ЛБГ L12 покрывает подграф G12.

Рассмотрим следующий этап синтеза БФ F3 для подграфа G3, включающего вершины 1, 2, 3 и дуги, инцидентные вершине 3 и вершинам 1, 2, за исключением уже представленных в строящейся БФ дуг X12, X22. Дуги X21 и X11 необходимы в обеспечение синтеза ЛБГ и БФ согласно ранее представленных условностей. Подграф G3 изображен на рис. 5,а; соответствующий ему ЛБГ L3 - на рис. 5,б.

f05.gif

При этом БФ F3 принимает следующий вид:

e06.gif

Из рассмотрения L3 и F3 следует, что перечисляются дуги X13, X23, X32, X31, X33 графа G. Построенная часть ЛБГ L, покрывающего граф G, описывается БФ вида e07.gif.

Дальнейшие построения выполним без использования рисунков, так как алгоритм синтеза ЛБГ Li, описывающего связи вершины i с вершинами, включенными в ЛБГ Li-1 (i > 2), заключается в следующем. Размещаем вершины ЛБГ так: вначале вершину 1, затем вершину i, далее вершину 2, затем опять i, потом 3, снова i, и так далее до тех пор, пока в ЛБГ не будет включена вершина i-1. Последней вершиной ставится i. Нулевые дуги ЛБГ, образующие его остов, помечаются как Xki или Xik (k < i), согласно смежным вершинам ЛБГ, за исключением последней нулевой дуги, помечаемой как Xii. Единичные дуги ЛБГ помечаются инверсией пометки соответствующей нулевой дуги, трансформирующейся в дугу вида Xk1 (Xi1).

Таким образом, последующие шаги приводят к ЛБГ L, представленному на рис. 6.

f06.gif

Этот ЛБГ описывается итоговой БФ вида

e08.gif

Каждая i-я строка последнего выражения есть БФ Fi соответствующего ЛБГ Li, i = 1,…,5. Полученная формула взаимно однозначно описывает исходный граф G с учетом допущенной условности. По данной БФ можно получить ОДНФ и ОДНФ ее инверсии. Дизъюнкция этих ОДНФ путем упрощения и исключения избыточности дает перечисление путей, покрывающих граф G и представляющих собой тестовую последовательность, проверяющую, например, программу, реализующую граф переходов конечного автомата.

Предложенный метод представления сильно связного графа посредством канонической булевой формулы распространяется на подобные графы с произвольным числом n вершин. При этом число конъюнктивных членов БФ равно числу вершин графа, число элементов в i-й дизъюнкции (i = 1,...,n) равно 2(i-1), число H букв в БФ определяется выражением

e09.gif

Общее число S путей в соответствующем ЛБГ определяется исходя из того, что для Li число путей равно 2(i-1)+1:

e10.gif

Рассмотрим второй подход к представлению орграфа БФ на примере графа, степень исхода и захода каждой вершины которого равны двум при наличии обязательной петли (рис. 7,а). Для синтеза ЛБГ L для графа G, изображенного на указанном рисунке, обратимся к рассмотрению второй условности, суть которой представлена на рис. 2,в, а именно: вершине i ЛБГ, реализующего конъюнкцию, сопоставим две исходящих дуги: единичную дугу перехода из вершины i в вершину j - Xij и ее инверсию (нулевую дугу), которую условимся обозначать как петлю у вершины i:

Б:       ~Xij ->Xii.

f07.gif

С учетом изложенного, ЛБГ L изображен на рис. 7,б, а соответствующая БФ имеет вид конъюнкции:

F = X12X23X34X45X51.

Для подобных «кольцевых» графов с числом n вершин БФ имеет каноническую форму вида

e11.gif

Перейдем к рассмотрению орграфов, не описываемых каноническими БФ. Орграфы, представляющие собой графы переходов программно реализуемых конечных автоматов, должны иметь обязательную петлю у каждой вершины, а также обязательную дугу, исходящую из каждой вершины в начальную (в обеспечение корректной работы и во избежание «зацикливания» [4]). Пример такого орграфа, полученный исключением некоторых дуг из орграфа (рис. 1), представлен на рис. 8.

f08.gif

Рекомендуется следующий метод синтеза БФ, описывающей подобный орграф. Синтезируем каноническую БФ для сильно связного орграфа с тем же числом вершин, и исключаем из нее члены, соответствующие отсутствующим в рассматриваемом орграфе дугам. В нашем случае получим промежуточную БФ вида

e12.gif

Рассматриваем левые крайние члены дизъюнкций Fi. Если такой член не есть ~X1i, то дополняем этот член слева конъюнкцией, образованной обозначениями дуг кратчайшего пути из вершины 1 в вершину i (из подмножества дуг, использованных в предшествующих дизъюнкций БФ F). В результате, для нашего примера получим БФ вида

e13.gif

Далее, рассматриваем каждую конструкцию вида

e14.gif

Если e15.gif, то требуется выполнить следующее. Элемент ~Xij преобразуется в конъюнкцию вида XijXj1, к элементу Xkh слева добавляется конъюнкция из обозначений дуг кратчайшего пути из вершины 1 в вершину k. Для рассматриваемого примера окончательно получим БФ вида

e16.gif

Предложенный метод синтеза БФ, описывающих орграфы указанного выше вида, является строго формальным. Однако, для орграфов, имеющих петли у каждой вершины, но не содержащего дуги хотя бы из одной вершины в начальную, требуется синтезировать БФ как с элементами представленного метода, так и интуитивно. Для таких орграфов можно синтезировать БФ в виде конъюнкции, включающей обозначения дуг, образующих несколько путей из начальной вершины. Этот эвристический подход рассмотрим на примере орграфа, изображенного на рис.9.

f09.gif

Один из вариантов БФ, описывающей орграф, имеет вид

e17.gif

Регулярный синтез БФ, описывающих подобные графы, может быть основан на известных методах обхода орграфов.

 

Список литературы

1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦМНО. 1999. –  960 с.

2. Кузнецов Б.П., Шалыто А.А. Система преобразований некоторых форм представления булевых функций // Автоматика и телемеханика. 1985. № 11. С. 120 – 127.

3. Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. I. Синтез и анализ // Теория и системы управления. 1994. № 5. С. 132 – 142.

4. Кузнецов Б.П. Психология автоматного программирования // BYTE-Россия. 2000. № 11. С. 22 – 29.