Классы всех графов, мультиграфов и простых графов

Рассмотрим конструктивные описания некоторых замкнутых и - замкнутых классов графов. Множество всех графов Â является, очевидно, замкнутым классом. В работе [5] были получены следующие конструктивные описания вышеназванных классов.

Теорема 4.2.1. Замкнутый класс всех графов имеет элементный базис  и операционный базис .

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

1. Построим пустой граф, содержащий | V (G)| вершин. Это можно сделать с помощью (| V (G)|-1) операцийсклейки по O ₀ . Вначале реализуется граф , состоящий из двух изолированных вершин, а затем с помощью операций склейки текущего графа с   O ₁   по O ₀ число изолированных вершин доводится до | V (G)|.

2.  Дополним пустой граф ребрами и (или) петлями до величины равной | E (G)| с помощью операций склейки заданных пар вершин текущего графа с K ₂ по O ₂  и (или) заданных вершин текущего графа с C ₁  по O ₁.

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

операций склейки. Покажем минимальность по включению этой системы. Без операций склейки по O ₀  нельзя реализовать несвязные графы, поскольку все графы элементного базиса связны. Без операций склейки по O ₁ нельзя построить графы, вершины которых инцидентны нескольким петлям. Без операций склейки по O ₂ нельзя построить графы, содержащие кратные ребра.         ð

На основе подмножеств порождающих базисов замкнутого класса всех графов можно строить конструктивные описания для различных подклассов всех графов. В [7] построена решетка всех 35 таких нетривиальных замкнутых подклассов. Ниже приведены конструктивные описания некоторых из них

Графы, не содержащие петель, называются мультиграфами.

Следствие 4.2.1. Замкнутый класс мультиграфов имеет элементный базис  и операционный базис .

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

Следствие 4.2.2. Замкнутый класс лесов имеет элементный базис  и операционный базис .

Следствие 4.2.3. Замкнутый класс деревьев имеет элементный базис и операционный базис .

Для сохранения отсутствия в графах кратных ребер в общем случае  необходимо накладывать ограничение на выбор в графах-операндах отождествляемых подграфов, содержащих не менее двух вершин (см. рис. 4.1.2). Достаточным условием для этого может быть следующее ограничение: каждой паре несмежных в подграфе  вершин должна соответствовать пара несмежных вершин хотя бы в одном из графов-операндов  или . Соответствующую систему ограничений на операции склейки обозначим через . При этом из теоремы 4.2.1 получаем

Следствие 4.2.4. Класс простых графов - замкнут с элементным базисом  и операционным базисом .

Подграф G ’ Í G называется порожденным, если для каждой пары смежных вершин, включаемых в G ’, в подграф включается и соответствующее ребро. Подграф, порожденный вершинами V ’ Í V (G), обозначается через G (V ’).

Число вершин связного графа G, удаление которых приводит к несвязному или одновершинному графу, называется числом вершинной связности (связностью), обозначаемым через À (G). Подмножество V ’ Í V (G)   называется разделяющим множеством вершин графа G, если граф G (V \ V ’) имеет больше компонент связности, чем граф G.

Если | V (G)|> max { | V (G ₁)|,| V (G ₂)| }, то V () является разделяющим множеством вершин связного графа G = . Указанное неравенство имеет место при выполнении любой нетривиальной операции склейки по порожденному подграфу (операции < H > - склейки). Введенное ограничение на операции склейки существенно уменьшает «силу» операций, что приводит к увеличению мощности порождающих базисов.

Теорема 4.2.2. < H > - замкнутый класс простых графов имеет счетные элементный и операционный базисы.

Доказательство. Бесконечность элементного базиса следует из того, что каждый полный граф K_n, n ³ 3 не может быть получен в результате выполнения нетривиальной операции < H > - склейки. Поскольку в противном случае множество V () должно быть разделяющим в графе и его связность À ( ) £ n -2, но по определению связность полного графа À ( )= n -1.

Покажем бесконечность операционного базиса. Рассмотрим счетную последовательность графов . Каждый граф G  этой последовательности имеет связность À (G)= n -1 и поэтому G не может быть получен в результате выполнения склейки , так как при этом

À (G)< n -1. Следовательно, в операционный базис должно входить счетное множество операций < H > - склейки по K_n, n =1,2,….                                 ð

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

4.3. Классы планарных графов

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

Пусть все вершины подграфов  и  принадлежат граням  со связными границами Г₁ и Г₂ соответственно в графах G ₁ и G ₂. Преобразуем плоские укладки графов G ₁ и G ₂ таким образом, чтобы все вершины этих граней располагались вдоль окружностей, вписанных соответственно в грани Г₁ и Г₂.  Отождествим подграфы  и , выбирая пары отождествляемых вершин в соответствии с круговыми обходами этих окружностей.  Операции склейки, удовлетворяющие указанным ограничениям, обозначим как операции H ^Ä - склейки.

Теорема 4.3.1. Операции H ^Ä – склейки сохраняют планарность графов.

Доказательство. Рассмотрим плоские укладки графов G ₁ и G ₂, в которых все вершины соответственно граней Г₁ и Г₂  расположены вдоль вписанных в них окружностей. Каждую из этих окружностей можно интерпретировать как линию разреза сферы на две полусферы, на которых размещены рассматриваемые плоские укладки графов G ₁ и G ₂.

Для отождествления вершин из  с вершинами из  в соответствии с круговыми обходами граней Г₁ и Г₂  достаточно поворота одной полусферы относительно другой вдоль линии разреза с «растяжениями» или «сжатиями» в случае необходимости длин дуг окружностей, соединяющих вершины из  или , а также, быть может, зеркального отображения укладки графа на одной из полусфер (при несовпадении направлений круговых обходов граней Г₁ и Г₂). Каждое из этих преобразований сохраняет плоские укладки графов-операндов. Поскольку при отождествлении ребер из  с ребрами из  новые ребра не появляются, то результирующий граф G планарен.         ð

Конструктивные описания планарных графов с использованием различных модификаций операции H ^Ä -склейки рассматривались в [5].

Теорема 4.3.2. Класс планарных графов H ^Ä -замкнут с порождающими базисами  и .

Доказательство. Планарность графа G, реализуемого H ^Ä -суперпозицией над ,следует из планарности графов элементного базиса и сохранения планарности графов при выполнении над ними операций H ^Ä -склейки (теорема 4.3.1).

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

Минимальность по включению множеств  и  устанавливается также как и при доказательстве теоремы 4.2.1.                                                             ð

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

Если | V ()| £ 3, то любой способ отождествления вершин из  с вершинами из  соответствует круговым обходам граней Г₁ и Г₂ . Поэтому для сохранения планарности в этом случае достаточно, чтобы отождествляемые вершины принадлежали границе одной грани  в каждом из графов-операндов (операции H ^Г  - склейки).

Следствие 4.3.1. Класс планарных графов H ^Г - замкнут с порождающими базисами  и .

Следствие 4.3.2. Класс планарных мультиграфов H ^Г - замкнут с порождающими базисами  и .

Следствие 4.3.3. Класс простых планарных графов H ^Г -замкнут с порождающими базисами   и .

Если ограничиться использованием операций H ^Ä  - склейки, при выполнении которых вершины V () образуют разделяющее множество S в результирующем графе G =   (обозначим их как операции - склейки), то есть  и , то получаем следующий результат.

Теорема 4.3.3. -замкнутый класс простых планарных графов имеет порождающие базисы  и .

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

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

Если G - полный граф, то он может содержать не более 4 вершин (K ₅  не является планарным).

Если граф G не является связным, то достаточно построить все его компоненты связности, объединив их затем с помощью операций склейки по O ₀.

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

Если простой связный планарный граф G не содержит разделяющих вершин, то выберем в G вершину v_i, смежную не со всеми вершинами (такая вершина найдется, так как граф G не является полным). Обозначим через V_i множество вершин, смежных с вершиной v_i. Выделим в графе G связные подграфы   и   звезду с центром в вершине v_i и с множеством висячих вершин V_i. Если выбрать графы-операнды G ₁ и G ₂ изоморфными соответственно этим подграфам, то получаем для графа G представление , k = | V_i |. При этом используется операция - склейки, поскольку графы G ₁ и G ₂ допускают плоские укладки, в которых отождествляемые вершины принадлежат границам связных граней. Кроме того, у звезды G ₂ отождествляемые вершины попарно не смежны и обладают симметрией вращения, являясь висячими.

Так как G ₁ и G ₂ являются простыми связными планарными графами и содержат меньшее число вершин, чем граф G, то, последовательно применяя к ним все предыдущие рассуждения в итоге, придем к системе полных графов из B_e. Рассматривая этот процесс в обратном направлении, получаем задание произвольного простого планарного графа G в виде - суперпозиции графов из B_e.

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

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

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

      

                 

 

                      

                                                         

  

O₀        O₁        O₂               O₃                         O₄                         O₅

                                                       

Рисунок 4.3.1

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

При использовании операций склейки по порожденным подграфам увеличивается избыточность конструктивных описаний. Для ограничения величины избыточности  рассматривают процессы сборки простых планарных графов, когда вершины из образуют минимальное разделяющее множество вершин результирующего графа каждой операции склейки. При использовании таких операций склейки число необходимых типов операций склейки – мощность операционного базиса, увеличивается до 16. Если же потребовать, чтобы и число ребер в подграфах склейки было минимальным, то мощность операционного базиса становится равной 22 [5]. Элементный базис при этом остается неизменным и содержит полные графы.

Эйлеровы  графы

Граф G является эйлеровым тогда и только тогда, когда степени всех его вершин четны (теорема 1.3.1). Выясним, при каких ограничениях на операции склейки они сохраняют свойство эйлеровости графов-операндов.

Теорема 4.4.1. Если графы G ₁ и G ₂ эйлеровы, то граф G =  будет эйлеровым тогда и только тогда, когда степени всех вершин отождествляемых подграфов  и  четны.

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

                ,                             (4.4.1)

где - степень вершины   в графе G ₁; - степень вершины  в графе G ₂; - степень вершины   в подграфе .

Необходимость. Если графы G ₁ и G ₂ являются эйлеровыми, то степени  и  четны. При этом для четности степени в графе G необходимо, учитывая (4.4.1), чтобы четной была степень  вершины   в подграфе . Поскольку  и , то степени всех вершин отождествляемых подграфов четны.

Достаточность. Если степени вершин отождествляемых подграфов  и  четны, то четна будет и степень любой вершины  подграфа . Из эйлеровости графов G ₁ и G ₂ следует четность  степеней  и . Отсюда, учитывая (4.4.1), получаем четность степеней всех вершин, входящих в подграф . Четность степеней вершин графа G, не принадлежащих подграфу , следует из эйлеровости графов G ₁ и G ₂. ð

Следствие 4.4.1. Операции H _Æ  - склейки сохраняют эйлеровость графов. Использование операций H _Æ  - склейки по пустым подграфам упрощает конструктивное описание, минимизируя избыточность задания.

Теорема 4.4.2. Класс эйлеровых графов H _Æ  - замкнут с порождающими базисами и .

Доказательство. Каждый эйлеров граф G может быть разложен на пореберно непересекающиеся простые циклы (следствие 1.3.1).Бесконечность элементного базиса следует из того, что простые циклы С _n, n =1,2,… не содержат эйлеровых подграфов и поэтому все они входят в B_e.

Бесконечность операционного базиса следует из того, что для любого сколь угодно большого n найдется эйлеров граф G, | V (G)|= n, связность которого À (G)> n и обхват g (G) (длина кратчайшего простого цикла) удовлетворяет условию g (G) > n [8]. Покажем, что такой граф не может быть получен склейкой по O_k, k £ n. Если V () разделяющее множество вершин графа G, то поскольку | V ()| £ n, получаем связность À (G) £ n и приходим к противоречию. Если V () не является разделяющим множеством вершин графа G = , то | V ()|= min { | V (G ₁)|,| V (G ₂)| }. Так как G, | V (G)|= n, то min { | V (G ₁)|,| V (G ₂)| } £ n. Поскольку каждый из графов-операндов G ₁ и G ₂ является эйлеровым, то, по крайней мере, один из них должен содержать простой цикл C _k, k £ n. Так как графы-операнды G ₁ и G ₂ изоморфны подграфам результирующего графа G = , то его обхват g (G) £ n, что также приводит к противоречию.        ð

Следствие 4.4.2. Класс обыкновенных эйлеровых графов  - замкнут с порождающими базисами  и .

Далее ограничимся рассмотрением эйлеровых планарных графов. При этом операционный базис станет конечным и возможно использование различных базисов. В работе [9] были получены следующие результаты. 

Лемма 4.4.1. В каждом эйлеровом планарном графе найдется простой цикл, содержащий не более трех вершин степени больше двух.

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

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

В любом графе G, | V (G)|= n имеет место равенство . Поскольку в рассматриваемом графе G степень каждой вершины не меньше 4, то справедливо соотношение

                                     .                            (4.4.2)

Предположим, что утверждение леммы неверно для графа G, то есть все простые циклы графа G имеют длину не меньше 4. Рассмотрим произвольную плоскую укладку графа G. Для величины Q (G), равной общему числу рёбер вокруг всех граней графа G, получаем оценки 2 m = Q (G) ³ 4 f, откуда следует, что   m ³ 2 f. Учитывая равенство (2.2.1), получаем утверждение m £ 2 n -4, противоречащее соотношению (4.4.2).                                                               ð

Операции склейки, сохраняющие эйлеровость и планарность графов, обозначим как операции  - склейки (операции  - склейки, если | V ()| £ 3).

Теорема 4.4.3. Класс эйлеровых планарных  графов  - замкнут с порождающими базисами  и .

Доказательство. Поскольку простые циклы С _n, n =1,2,… являются эйлеровыми и планарными, то обоснование   в качестве элементного базиса проводится аналогично теореме 4.4.2. Покажем, что операции  - склейки по графам из множества   образуют операционный базис класса эйлеровых планарных графов. Установим вначале полноту указанного набора типов операций  - склейки, то есть, что этих трех типов операций  - склейки достаточно для построения из графов элементного базиса любого эйлерова планарного графа. Доказательство проведем индукцией по M - числу ребер рассматриваемых графов.

1. M =1. Таким графом является простой цикл Î .

2. Предположим, что все эйлеровы планарные графы с числом ребер
M =2,3,..., m можно построить из графов , используя операции  - склейки по графам из множества .

3.  Пусть G  произвольный эйлеров планарный граф, содержащий m +1 ребер. Если G является простым циклом, то G Î . В противном случае из леммы 4.4.1 следует, что G содержит простой цикл C_i, пересекающийся с подграфом, порожденным множеством ребер, не принадлежащих C_i не более чем по трем вершинам. После удаления из графа G ребер цикла C_i и возможно образовавшихся при этом изолированных вершин получим подграф , состоящий из одной или нескольких компонент связности. Каждая из компонент является эйлеровым графом, так как степени их вершин сохранили четность после удаления ребер цикла C_i. Если компонента связности одна, то получаем представление , в котором подграф , | E ( )| £ m   может быть построен  по предположению индукции.Если компонент связности больше чем одна, то среди них обязательно найдется компонента , содержащая только одну вершину из цикла C_i. Тогда , где  подграф, порожденный ребрами графа G, не принадлежащими . Графы   и ,  являются эйлеровыми планарными, содержащими каждый не более чем по m -1 ребру, могут быть построены по предположению индукции.

Покажем минимальность по включению используемых типов операций  - склейки. Без операций склейки по O ₁ нельзя построить графы, содержащие одну вершину и несколько петель. Для построения графов, содержащих две вершины, соединенных четным числом кратных ребер, необходимо использование операций склейки по O ₂. Без операций склейки по O ₃  не обойтись при построении октаэдра (рис.4.3.1) с помощью операций  - склейки.             ð

Рассмотренный операционный базис не является единственным для класса эйлеровых планарных графов. Справедлива

Теорема 4.4.4. Класс эйлеровых планарных  графов  - замкнут с порождающими базисами  и .

Доказательство этой теоремы, требующее более тщательного анализа структуры эйлеровых планарных графов, приведено в [9].                               ð

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

Гамильтоновы графы

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

 

 

Лемма 4.5.1. Граф G =   сохраняетгамильтоновость графов   и , если | V ()|=| V (G ₁)| и (или) | V ()|=| V (G ₂)| либо | V ()|=2 и соответствующие им вершины графов-операндов являются смежными в гамильтоновых циклах графов   и .

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

Операции, удовлетворяющие указанным ограничениям, обозначим как операции - склейки. Поскольку наличие кратных ребер не существенно для наличия гамильтонова цикла, то будем также пользоваться операциями  - склейки, сохраняющими и отсутствие кратных ребер. Простая цепь, содержащая n вершин, обозначается как L_n. Нижеследующие результаты получены в работе [10].

Теорема 4.5.1. Конструктивные описания -замкнутого класса гамильтоновых графов имеют элементный базис  и один из трех операционных базисов ,  или .

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

Покажем, что при этом можно получить любой гамильтонов граф .  Если граф  содержит петли и (или) кратные ребра, то его можно представить соответственно в виде  или , где граф  или  содержит на одну петлю С₁ или на одно кратное ребро e меньше, чем граф . Применяя к графу  те же рассуждения, приходим к простому гамильтонову графу.

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

Покажем, что использования операций   - склейки по графам из множеств  или  или  достаточно для построения простого гамильтонова графа , исходя из циклов

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