§ 4. Алгебраическая форма представления графа

Основные принципы теории графов используются для построения математической модели, возникающей при проектировании и анализе сетей ЭВМ. Графовая структура является наиболее удобной формой представления модели сети для пользователя. Естественным представляется сделать такую форму технологичной и для машины.

Такая модель должна обладать следующими свойствами:

- компактность представления информации о графе;

- привязка к распространенному математическому аппарату;

- наличие эффективных методов анализа графовых отношений;

- возможность аналитического описания функций и структур.

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

Ориентированный граф есть множество вершин Н = {H₁, H₂, … , H_i , … , H_k }, которые связаны между собой отношениями, идентифицируемыми совокупностью дуг Е = {E₁, E₂, … , E_r, … , E_n }, где каждая дуга задается конкатенацией двух соединенных между собой вершин и обозначается в виде или , или E_i & E_j , или E_i · E_j , или E_iE_j .

Ориентированная дуга H_i & H_j , связывающая две вершины в графе, где H_i – исток, а H_j – сток, называется импликативным отношением.

Если - множества вершин или дуг, принадлежащих графу G , то есть дизъюнкция или объединение этих множеств.

Рассмотрим построение формул в алгебраической форме представления графа (АФПГ):

1. Символ есть формула АФПГ;

2. Символ 1 есть обозначение псевдовершины и является также формулой АФПГ;

3. Если формулы АФПГ, то и также являются формулами;

4. Формулы используют открывающую и закрывающую скобки;

5. Упорядоченная совокупность вершин, соединенная знаками импликации, называется термом АФПГ.

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

Для АФПГ выполняются следующие аксиомы абстрактной математической решетки:

Аксиома 1. Коммутативность:

Последнее равенство верно для неориентированных графов.

Аксиома 2. Ассоциативность:

Аксиома 3. Дистрибутивность:

Аксиома 4. Идемпотентность:

Аксиома 5. Аксиома о единичном элементе:

Для целей структурного анализа и синтеза графов полезными являются следующие тождества:

Тождество 1. Правило поглощения (минимизации) фрагмента графа.

Если есть выражения АФПГ, описывающих два фрагмента графа, то действительными являются следующие уравнения:

На основании аксиомы о единичном элементе и дистрибутивного закона для первого равенства имеем

Аналогично доказывается справедливость второго равенства.

Следствие. Если вершины графа, то дуга поглощает любую вершину, входящую в данную дугу.

Тождество 2. Правило конкатенации (подстановки, сцепления).

Если есть выражения АФПГ, то действительно следующее уравнение:

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

Тождество 3. Правило разложения (декомпозиции).

Если есть выражения АФПГ, являющиеся компонентами или буквами терма, то его можно разложить на два терма по любой букве (переменной), входящей в исходное выражение:

Действительно, первое и последнее равенства истинны согласно правилу поглощения. Второе верно вследствие применения правила конкатенации.

Теорема. Если есть произвольные формулы АФПГ, то истинным является выражение

.

Доказательство: На основании правила конкатенации имеем , а с учетом аксиомы коммутативности получаем После этого, используя опять правило конкатенации, получаем требуемое выражение .

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

Следствие. Если в терме (пути) существует вершина , входящая в терм дважды, то все вершины, находящиеся между вершинами и совместно с вершиной образуют контур или замкнутый путь (цикл).

Терм, в котором существуют только две одинаковые вершины и и не существует других вершин, называется единичным термом.

Терм, состоящий из вершин, образующих контур, называется контурным.

Длина контура, задаваемого контурным термом, определяется числом входящих в него букв минус единица.

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

.

Лемма. Каждая пара смежных дуг неориентированного графа представлена в АФПГ контуром длины, равной 2.

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

Следствие. Для алгебраической формы представления неориентированного графа выполняется аксиома коммутативности относительно операции конкатенации (конъюнкции)

.

Замечание. АФПГ есть универсальный математический аппарат для аналитического (компактного) представления графовых структур, включающих фрагменты с ориентированными, неориентированными дугами или без них.

Пример.

□ Граф G , представленный на рис. 4.14 и отображающий топологию

Рис. 4.14

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

которое на основании правила конкатенации можно записать:

■

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

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

Например, для структуры, представленной на рис. 4.15, решение такой

Рис. 4.15

задачи приводит к следующему конечному результату:

который определяет в качестве термов все пути, в данном случае длиной 4 , в графе от вершины – истока Н₁ к вершине – стоку Н₇ .