Конструктивное описание графов

Следствие 1. Если V(Ğ) — тупиковое разделяющее множество вершин связного графа G = ( о )Ğ и \V(Ğ)\ ≥ 2, то каждая пара вершин из V(Ğ) соединена в G(E( )\E( ')) и G(E( )\E( ')) цепями Ln, n ≥ 2, внутренние вершины которых не принадлежат V(Ğ).

Следствие 2. Если V(Ğ) — тупиковое разделяющее множество вершин связного графа G = ( о )G и \V(Ğ)\ ≥ 3, то в V( )\V( ') и V( )\V( ') найдутся вершины, соединенные непересекающимися цепями с любыми тремя вершинами из V(Ğ).

Свойство 5. Если V(Ğ) — тупиковое разделяющее множество вершин графа G = ( o )Ğ, то операция склейки сохраняет ацикличность и связность графов тогда и только тогда, когда Ğ — К1.

ДОКАЗАТЕЛЬСТВО. Необходимость наличия хотя бы одной вершины

в части Ğ следует из свойства 2. Если |V(Ğ)| ≥ 2, то по следствию 1 в графе G должен существовать цикл. Так как и не содержат петель, то из свойства 1 следует, что Ğ = K1.

Достаточность. Нетрудно видеть, что операции склейки по сохраняют ацикличность графов. Связность графа G следует из свойства 2. Свойство 5 доказано.

 

§ 3. Структура замкнутых

и if-замкнутых  классов графов

Теорема 1. Каждый Н-замкнутый класс графов имеет единственный

элементный базис.

ДОКАЗАТЕЛЬСТВО. Рассмотрим произвольный H-замкнутый класс графов Р. Поставим ему в соответствие ориентированный граф с множеством вершин V( ) =Р. Дуга ( ), V( ), i , содержится тогда и только тогда, когда соответствующий вершине граф является графом-операндом хотя бы одной нетривиальной операции H-склейки, реализующей граф , соответствующий вершине . Так как при проведении дуг в G^ учитываются лишь нетривиальные операции H-склейки, то \V( )\ > |V( )| или (и) \E( )\ > \E( )\.

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

поскольку ни один из таких графов не может быть выражен  в виде Н- суперпозиции других графов из Р. Отсюда же следует и единственность элементного базиса. Теорема 1 доказана.

Из теоремы 1, учитывая замечание 1, получаем

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

Следующая теорема  дает ответ на вопрос о мощности базисов замкнутых

классов.

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

ДОКАЗАТЕЛЬСТВО. Достаточно выделить бесконечную последовательность графов, каждый из которых нельзя представить суперпозицией других графов последовательности. Ее замыкание образует искомый класс. Пример подобной последовательности графов приведен на рис. 2. Теорема 2 доказана.

Следствием  теоремы 2 является

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

ДОКАЗАТЕЛЬСТВО. Число замкнутых классов множества Q всех графов оценивается сверху числом всех подмножеств графов из Q. Так как Q содержит счетное число графов, то число подмножеств в Q равно континууму.

Далее, множество  замкнутых классов, базисами которых  являются все подмножества бесконечной последовательности графов, изображенных на рис. 2, континуально. Теорема 3 доказана. Так как каждый замкнутый класс является и H-замкнутым классом, то из теорем 2 и 3 имеем

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

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

§ 4. Базисы классов всех графов,

мультиграфов  и обыкновенных графов

Множество всех графов является, очевидно, замкнутым  классом.

Теорема 4. Графы , и образуют базис В замкнутого класса всех графов.

ДОКАЗАТЕЛЬСТВО. Учитывая свойство 1 операции склейки, имеем { , , } В. Далее согласно следствию 3 для доказательства обратного включения достаточно показать, что любой граф G представим в виде суперпозиции графов из { , , }. Это можно сделать, например, так:

1) построить пустой |V(G)|-вершинный граф с помощью (|V(G)| —

1) операций склейки по  , реализующих графы вида (g o ) , где g— результирующий граф предыдущей операции склейки (g = при выполнении первой операции);

2) затем пустой граф  дополнить ребрами до графа  G, использовав |E(G)| операций склейки, реализующих графы вида (g о К2) и (или) (g о ) .

Теорема 4 доказана. Из теоремы 4 получаем

Следствие 6. Замкнутый класс всех графов имеет элементный базис Вэ = { , , } и операционный базис — { , , }.

Для доказательства следствия 6 достаточно установить минимальность числа типов операций, включенных в множество В0. Без операций склейки по К0 нельзя реализовать несвязные графы (свойство 2). Графы (.. .( о )Ki о • • • о ) невозможно построить без использования операций склейки по . Графы (.. .( о ) о • • • о ) нельзя построить без использования операций склейки по .

На основе подмножеств  базисов  и можно строить другие Н- замкнутые классы графов. Из следствия 6 получаем

Следствие 7. Замкнутый класс мультиграфов имеет элементный базис = { , } и операционный базис = { , }. При переходе к операциям склейки, сохраняющим отсутствие кратных ребер, получаем

Следствие 8. < Н >-замкнутый класс обыкновенных графов имеет элементный базис = { , } и операционный базис = { , }.

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

Теорема 5, Существует счетное множество конечных описаний замкнутого класса всех графов. ДОКАЗАТЕЛЬСТВО. Счетные множества конечных элементных и операционных базисов для класса Р всех графов можно получить следующим образом.

Из множества Н операций склейки всех типов последовательно удаляются

операции склейки  по ( о ) , (( о ) о ) и т. д. Получающиеся при этом подмножества операций склейки обозначаются через , i = 1,2,... Для каждого замыкания класса Р по и строятся множества графов и операций (см. таблицу).

Для каждого  множества  имеем = Р. Возможность построения всех одновершинных графов, допускающих ребра-петли, следует из способа построения э и определения . Объединяя эти графы операциями склейки по И добавляя ребра с помощью операций, реализующих графы вида (g о ) , где g — результирующий граф предыдущей операции склейки, получаем любой граф G. Минимальность по включению множеств э следует из ограничений на множества и теоремы 4. Минимальность по включению множеств 0 устанавливается следующим образом: без операций склейки по не реализуются несвязные графы (свойство 2 операции склейки); без операций склейки по нельзя построить граф , так как каждое не содержит операций склейки по Ki\ по этой же причине необходимы операции склейки по , ( o ) и т. д. для реализации соответственно графов (( о ) о , ((( о ) о ) о ) и т. д. Теорема 5 доказана.

ЗАМЕЧАНИЕ 2. Задания  графов, соответствующие различным  базисам,

различаются величиной  избыточности, возрастающей при переходе от к , i = 1,2,...

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

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

ДОКАЗАТЕЛЬСТВО. Бесконечность элементного базиса следует из того, что любой граф G = , n ≥ 3, не может быть получен в результате выполнения нетривиальной операции склейки по подграфу Ğ.

Действительно, если это возможно, то, учитывая свойство 4 операций склейки, множество V(Ğ) должно быть разделяющим в графе G и его связность Ϟ (G) n — 2. С другой стороны, полный граф имеет связность Ϟ( ) = п — 1. Таким образом, элементный базис должен содержать в своем составе счетное множество полных графов.

Покажем бесконечность  операционного базиса. Рассмотрим счетную последовательность графов вида ( о ) _i, n = 2 , 3 , . . . Каждый граф этой последовательности имеет связность, равную п — 1, и не может быть результатом операции склейки с по i < n — 1, так как при этом связность графа будет меньше п — 1. Следовательно,в операционный базис входит счетное множество операций склейки по Ğ, где Ğ = , n= 1,2,... Теорема 6 доказана.

Следствие 9. Мощность множества всех < Н >-замкнутых классов обыкновенных графов континуальна.

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

§5. Условия наследования

триангулированности графов

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

если G и (или) G , т о происходит наследование всех свойств графов-операндов.

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

Лемма 2. Если отождествляемые части графов-операндов являются полными, то операция склейки сохраняет хордальность графов.

ДОКАЗАТЕЛЬСТВО. Поскольку графы-операнды и хордальны, цикл , n ≥ 4, без хорды должен содержать вершины из V( )\V( ) и V( )\ V( ), где V( )и V( ) — вершины отождествляемых частей графов и . При этом вершины множества V(Ğ) образуют разделяющее множество в результирующем графе (свойство 4). Так как — простой цикл, то получаем две несмежные вершины в (5, что

невозможно, так  как отождествлялись полные части  графов-операндов.  Таким образом, цикл , n ≥ 4, содержит хорду. Лемма 2 доказана.

Лемма 3. Если V(Ğ) — тупиковое разделяющее множество вершин хордального графа G — ( о )Ğ, то Ğ — его полная часть.

ДОКАЗАТЕЛЬСТВО. При |V(Ğ)| = 1 утверждение леммы следует из определения полной части графа. Если |V(Ğ)| ≥ 2 и Ğ не является полной частью графа G, то по следствию 1 получаем цикл , n ≥ 4, без хорды, что противоречит условию. Лемма 3 доказана.

Из лемм 2 и 3 следует

Теорема 7, Если V(Ğ) — тупиковое разделяющее множество вершин графа G = ( о )Ğ, то операция склейки сохраняет хордальность графов тогда и только тогда, когда Ğ — полная часть графа G. Обозначим через , 1 i , результирующий граф операции склейки, использовавшейся на i-м шаге построения графа G; — отождествленная часть графа = ( о )  

Лемма 4. Если V — разделяющее множество вершин графа ,

 i — 1, я все части , i < j , являются полными, то V является

разделяющим множеством вершин графа G.

ДОКАЗАТЕЛЬСТВО. Предположим, что V не является разделяющим множеством в G. Это означает, что в графе G содержится ребро (v1,v2) такое, что вершина v1 принадлежит V( )\V( ), в то время как вершина v2 принадлежит множеству V( )\V( ). Однако такого ребра в G не может быть, ибо ребро (v1, v2) отсутствовало в графе и не могло появиться позднее при выполнении операций склейки по полным частям. Лемма 4 доказана.

ЗАМЕЧАНИЕ 3. Из теоремы 7 и леммы 4 следует структурная  харак- теризация хордальных графов [10].

§6. Условия  наследования

планарности графов

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

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

ДОКАЗАТЕЛЬСТВО. Связную часть плоского графа G, являющуюся границей грани Г, обозначим через . Нетрудно видеть, что граф представим в виде { -суперпозиции простых циклов и максимальных (по включению) деревьев. Проведем доказательство индукцией по m — числу циклов и деревьев, используемых при построении графа . Базис индукции для m = 1. Если является деревом, то произведем линейное размещение его вершин в соответствии с круговым обходом грани Г (в любом из двух возможных направлений), начиная с произвольной вершины. При этом допустима одностраничная плоская укладка ребер дерева, поскольку отрезки прямой, заключенные между концевыми вершинами произвольной пары ребердерева, либо не пересекаются, либо один из них содержится в другом. Заменяя отрезок прямой, содержащий все вершины дерева, на дугу окружности с сохранением односторонней плоской укладки ребер дерева, получаем искомую плоскую укладку графа G. Если — простой цикл, то существование искомой плоской укладки графа G очевидно.