Глава 4 . Конструктивные описания графов

Основные понятия и представления

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

Используется конструктор графов, включающий вместе с каждым графом его изоморфные копии. К графам применяется набор операций. Рассматриваются бинарные операции склейки, при выполнении которых производится отождествление изоморфных подграфов  и  графов-операндов  и . Операция склейки называется тривиальной, если  и (или) . В общем случае операция склейки не является однозначной. Для результирующих графов G используется обозначение , где - граф, изоморфный отождествляемым подграфам  и , называемый подграфом склейки.

При фиксированных графах-операндах  и  граф  может зависеть от вида подграфа склейки  (рис.4.1.1), выбора отождествляемых под-

                                                                                        

                                                        

                             

                              

                                                                          

Рисунок 4.1.1

                                                                     

                          

                                                                   

                             

                                               

Рисунок 4.1.2

                                                                              

                                                                               

                                                                  

                                                                               

                                                                              

 

Рисунок 4.1.3.

 графов  и  в графах-операндах (рис. 4.1.2) и способа их отождествления (рис. 4.1.3).

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

Пусть Á множество графов, обладающих некоторым характеристическим свойством. Граф G называется суперпозицией графов из Á, если G Î Á или G можно получить путем последовательного применения операций - склейки к графам из Á и к графам, полученным из Á с помощью операций - склейки. При выполнении каждой операции - склейки вид отождествляемых подграфов, их выбор в графах-операндах и способ отождествления определяются, в общем случае, независимо. Процесс построения графа G из графов множества Á с помощью операций - склейки задает операцию - суперпозиции графов из Á (операцию - суперпозиции над Á). Если в операции - суперпозиции хотя бы один из графов-операндов каждой операции склейки принадлежит исходному множеству Á, то операция - суперпозиции называется канонической.

Приведем достаточное условие реализуемости графов каноническими суперпозициями. Рассмотрим операции склейки по пустым подграфам (операции H _Æ  - склейки).

Лемма 4.1.1. Если граф G реализуем некоторой H _Æ  -суперпозицией над Á, то он реализуем и произвольной канонической H _Æ  -суперпозицией над Á.

Доказательство. Любой операции суперпозиции над Á, реализующей граф G, можно поставить в соответствие некоторое покрытие G графами из Á. Так как элементы покрытия, соответствующие H _Æ  - суперпозиции, пореберно не пересекаются, то любое изменение порядка покрытия, то есть порядка сборки графа, может повлиять лишь на число вершин, включаемых в отождествляемые пустые подграфы тех или иных операций склейки, и не выводит из класса H _Æ  - суперпозиций. При этом, в частности, можно получить любую каноническую H _Æ  - суперпозицию над Á.                                                              ð

Множество всех графов, полученных из Á с помощью операций - суперпозиции, обозначается через [ Á ] _H. Класс Á называется - замкнутым, если [ Á ] _H = Á. Подмножество графов  образует полную систему графов - замкнутого класса Á, если [ ] _H = Á. Минимальная по включению полная система графов  образует элементный базис -замкнутого класса Á.

Операции с изоморфными подграфами склейки  относятся к одному типу. Множество, содержащее минимальное по включению число типов операций - склейки, достаточное для построения из  всех графов - замкнутого класса Á образует его операционный базис B_o. Операционный базис B_o задается множеством графов, изоморфных подграфам склейки . Элементный и операционный базисы называются порождающими базисами. Вместе с системой ограничений H они задают конструктивное описание - замкнутого класса графов. О порождающих базисах известно [5] следующее.

Теорема 4.1.1. Каждый H – замкнутый класс графов имеет единственный элементный базис.

Доказательство. Рассмотрим произвольный -замкнутый класс графов P. Сопоставим ему ориентированный граф , вершины которого соответствуют графам из P, а дуга проводится тогда и только тогда, когда граф G_i, соответствующий вершине v_i,  является графом-операндом хотя бы одной нетривиальной операции - склейки, реализующей граф G_j, соответствующий вершине v_j. Так как при проведении дуг графа   учитываются только нетривиальные операции - склейки, то  и (или) . Из конечности графов G_i   и G_j, соответствующих вершинам графа , следует, что все пути, ведущие в любую вершину графа , содержат конечное число разных вершин. В графе  не может быть контуров, поскольку графы-операнды любой операции - склейки изоморфны подграфам результирующего графа и графы, соответствующие вершинам одного контура, были бы изоморфны друг другу. Таким образом, все пути, ведущие в любую вершину графа , имеют конечную длину. Отсюда следует, что множество вершин графа  с полустепенями захода равными нулю не пусто и графы. соответствующие таким вершинам, образуют элементный базис -замкнутого  класса P, поскольку ни один из таких графов не может быть выражен в виде - суперпозиции других графов из P. Отсюда же следует и единственность элементного базиса.                                                                                                   ð

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

Из теоремы 4.1.1 получаем

Следствие 4.1.1. Каждый замкнутый класс графов имеет единственный элементный базис.

Теорема 4.1.2. Существуют замкнутые классы графов со счетными элементными базисами.

Доказательство. Достаточно выделить бесконечную последовательность графов, каждый из которых не может быть получен с помощью суперпозиции из других графов этой последовательности. Замыкание  этой последовательности образует искомый класс. Примером такой последовательности может служить последовательность простых циклов C_i, i =1,2,…. Поскольку графы-операнды операций склейки изоморфны подграфам результирующего графа, то в суперпозиции, реализующей простой цикл C_n, не могут использоваться ни циклы C_i, i > n,ни циклы C_j, j < n.                                                                    ð

Логическим следствием теоремы 4.1.1 является

Теорема 4.1.3. Мощность множества всех замкнутых классов графов континуальна.

Доказательство. Число замкнутых классов множества всех графов Â оценивается сверху числом всех подмножеств графов из Â. Так как Â содержит счетное множество графов, то число подмножеств в Â имеет мощность континуума.

Для оценки сверху числа замкнутых классов достаточно заметить, что мощность континуума имеет множество замкнутых классов, элементными базисами которых являются всевозможные подмножества бесконечной последовательности простых циклов C_i, i =1,2,… .                                                         ð

Так как каждый замкнутый класс является и - замкнутым классом, то из теорем 4.1.2 и 4.1.3 получаем

Следствие 4.1.2. Существуют замкнутые классы графов со счетными элементными базисами.

Следствие 4.1.3. Мощность множества всех H – замкнутых классов графов континуальна.

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