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

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

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

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

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

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

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

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

А:            ~X_ij -> X_i1. 

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

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

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

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

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

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

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

Рассмотрим подграф G₂ графа G, включающий вершины 1 и 2 с инцидентными им и только им дугами X₁₁, X₁₂, X₂₂, X₂₁ (рис. 3,а). Этому подграфу поставим в соответствие ЛБГ L₂ (рис.3,б), описываемому БФ вида: . Данный ЛБГ L₂ однозначно соответствует подграфу G₂ с учетом ранее указанных условностей. В обеспечение канонизации преобразования графа в ЛБГ и БФ соединим ЛБГ L₂ (рис. 3,б) с ЛБГ L₁ , описывающим начальную вершину, согласно рис. 4. Полученной композиции взаимно однозначно соответствует ЛБГ , которому взаимно однозначно соответствует БФ вида . Последняя описывает G₁₂ (рис. 3,а).

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

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

Рассмотрим следующий этап синтеза БФ F₃ для подграфа G₃, включающего вершины 1, 2, 3 и дуги, инцидентные вершине 3 и вершинам 1, 2, за исключением уже представленных в строящейся БФ дуг X₁₂, X₂₂. Дуги X₂₁ и X₁₁ необходимы в обеспечение синтеза ЛБГ и БФ согласно ранее представленных условностей. Подграф G₃ изображен на рис. 5,а; соответствующий ему ЛБГ L₃ - на рис. 5,б.

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

Из рассмотрения L₃ и F₃ следует, что перечисляются дуги X₁₃, X₂₃, X₃₂, X₃₁, X₃₃ графа G. Построенная часть ЛБГ L, покрывающего граф G, описывается БФ вида .

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

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

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

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

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

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

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

Б:       ~X_ij ->X_ii.

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

F = X₁₂X₂₃X₃₄X₄₅X₅₁.

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

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

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

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

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

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

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

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

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

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

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

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

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

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