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

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

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

После удаления из грани Г графа G цикла или дерева, соответствующего висячей вершине вспомогательного дерева, получаем граф G' с гранью Г', имеющей связную границу, состоящую из т циклов и деревьев. По предположению индукции все ее вершины можно расположить вдоль окружности, вписанной в Г', в порядке кругового обхода грани Г, не нарушая плоскую укладку графа . Склеим граф G' по с циклом или деревом, удаленным ранее из графа G. Добавляемые при этом вершины расположим вдоль дуги окружности, вписанной в грань Г', непосредственно за отождествленной вершиной в порядке кругового обхода Г; и согласующегося с ним круговым обходом внешней грани добавляемого графа. Если граф, склеиваемый с G' по , есть дерево, то, как указывалось при доказательстве базиса индукции, его ребра допускают при этом одностороннюю плоскую укладку. Если G' склеивается по с произвольным плоским графом, внешняя грань которого есть простой цикл, то односторонняя плоская укладка всех ребер и внутренних вершин (если они имеются) добавляемого графа, очевидно, всегда возможна без нарушения плоской укладки графа. Лемма 5 доказана.

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

Лемма 6- Операции склейки сохраняют планарность графов.

ДОКАЗАТЕЛЬСТВО. Рассмотрим плоские укладки графов и , в которых все вершины соответственно граней и расположены вдоль вписанных в них окружностей в порядке круговых обходов граней. Каждую такую окружность можно интерпретировать как линию разреза сферы на две полусферы, на которых размещены рассматриваемые плоские укладки графов и . Для отождествления вершин из V( ) с вершинами из V( ) в соответствии с круговыми обходами граней и Г2 достаточно поворота одной полусферы относительно другой вдоль линии разреза с «растяжениями » или «сжатиями» в случае необходимости длин дуг окружностей, соединяющих вершины из V( ) (V( )) а также, быть может, зеркального отображения укладки графа на одной из полусфер (при несовпадении направлений круговых обходов граней и ). Каждое такое преобразование сохраняет плоские укладки графов-операндов. Так как при отождествлении ребер из E( ) с ребрами из E( ) не появляются новые ребра, то результирующий граф G планарен. Лемма 6 доказана.

ЗАМЕЧАНИЕ 4. При  любом отождествлении частей и , каждая из которых содержит не более трех вершин, всегда можно выбрать на-, правления обходов граней и так, чтобы отождествление вершин осуществлялось в порядке обхода граней. Отсюда и из леммы 6 получаем

Следствие 10. Операции склейки сохраняют планарность графов при \V(G)\ <: 3.

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

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

Теперь установим, что способ отождествления частей ' и удовлетворяет ограничениям, накладываемым на операции склейки .

Учитывая замечание 4, достаточно рассмотреть ситуацию, когда |V(Ğ)| ≥ 4. Две вершины из V( )(V( )) называются соседними, если хотя бы одна из двух цепей, соединяющих их по границе грани \ ( ), не содержит внутренних вершин из V( )(V( ). Нетрудно видеть, что пары отождествляемых вершин обеспечивают согласование круговых обходов граней, содержащих V( ) и V( ), тогда и только тогда, когда соседние вершины из V( ) отождествляются с соседними вершинами из V( ). При несоблюдении этого условия в части Ğ найдется вершина, которая соединяется непересекающимися цепями с тремя другими вершинами из V(Ğ). Поскольку V(Ğ) — тупиковое разделяющее множество графа G, то, учитывая следствие 2, каждая из этих трех вершин соединена непересекающимися цепями еще с двумя вершинами, дна из которых принадлежит подграфу G(V( )\(V( )), а другая — подграфу G(V( )\(V( )). Поэтому в G можно вйделить часть, гомеоморфную ч т о противоречит условию планарности графа G [7]. Лемма 7 доказана.

На основе лемм 6 и 7 доказана

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

ДОКАЗАТЕЛЬСТВО. Предположим, что в графе G найдутся части  и , i < j , такие, что |V( ) V( )\≥ 3. Произвольную тройку из этих вершин обозначим через v1, v2 и v3. По следствию 2 каждая из них соединена непересекающимися цепями с вершинами V( )\V( ) и V( )\V( i2). Рассмотрим граф = ( о ) , j > i, получаемый далее в процессе построения графа G. Выберем из склеиваемых графов Gj1 и Gj2 тот, который не содержит часть . Пусть это будет граф . Так как вершины v1, v2 и v3 принадлежат тупиковому разделяющему множеству вершин графа , то они соединены непересекающимися цепями с некоторой вершиной V( )\V( ). Учитывая выбор , эти цепи не пересекаются с цепями, которые соединяют указанные три вершины с вершинами и . Таким образом, в графе можно выделить часть, гомеоморфную Кз,з, что противоречит условию планарности графа , а следовательно, и условию планарности результирующего графа G. Лемма 8 доказана.

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

планарности максимальных графов

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

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

ДОКАЗАТЕЛЬСТВО. Необходимость. Число вершин (ребер) графов G, , , Ğ обозначим соответственно через n, , , (m, , ). Так как G, , являются максимальными планарными графами, то

Из определения  операции склейки следует, что

Подставляя  равенства (1) в соотношение (2), с учетом выражения (3)

получаем

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

ным графом. Число  вершин и ребер в любом максимальном внеш- непланарном графе связано соотношением

Система уравнений (4) и (5) имеет единственное решение  = 3 и = 3. Таким образом, если V(Ğ) — тупиковое разделяющее множество вершин максимального планарного графа G, то при его построении из максимальных

планарных графов и может использоваться только операция склейки по Кз. Принадлежность вершин из Кз одной грани в плоских укладках графов и следует из теоремы 8.

Достаточность. Вершины Кз принадлежат одной грани в плоских укладках графов и . Так как |V(Ğ)| = 3, то из следствия 10 вытекает планарность графа G. Подставляя в правую часть соотношения (2) два последних равенства из (1) и =3, при = З с учетом (3) получаем m = Зn — 6. Таким образом, G является максимальным планарным графом. Теорема 9 доказана.

 

 

 

ЛИТЕРАТУРА

1. Емеличев  В. А., Мельников О. И., Сарванов  В. И., Тышкевич

Р. И. Лекции по теории графов. М.: Наука, 1990.

2. Иорданский  М. А. Замкнутые классы планарных графов / / Комбинаторно-

алгебраические  методы в прикладной математике. Горький: Горьк.

гос. ун-т, 1985. С. 76-82.

3. Иорданский  М. А. Алгоритмические описания внешнепланарных графов

/ / Тез. второй междунар. конф. «Математические алгоритмы».

Н. Новгород: Нижегород. гос. ун-т, 1995. С. 24-25.

4. Иорданский  М. А. О степенях вершин некоторых классов планарных

графов / / Комбинаторно-алгебраические методы и их применение. Горький:

Горьк. гос. ун-т, 1987. С. 34-39.

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

5. Иорданский  М. А. Некоторые вопросы анализа и синтеза графов //

Тр. первой междунар. конф. «Математические алгоритмы». Н. Новгород:

Нижегород. гос. ун-т, 1995. С. 33-38.

6. Уилсон Р. Введение в теорию графов. М.: Мир, 1978.

7. Харари  Ф. Теория графов. М.: Мир, 1977.

8. Яблонский  С. В. Введение в дискретную математику. М.: Наука, 1986.

9. Яблонский  С В . Основные понятия кибернетики / / Проблемы кибернетики.

М.: Физматгиз, 1959. Вып. 2. С. 7-38.