Введение
Будем говорить, что граф укладывается на поверхности , если его можно так нарисовать на , что никакие два его ребра не пересекаются. Граф называется планарным, если его можно уложить на плоскости; плоский граф – это граф, уже уложенный на плоскости. Области, определяемые плоским графом, назовем его внутренними гранями[1].
На сегодняшний день известны два обхода графа с возвращением в ту вершину, из которой они были начаты:
1) цикл Эйлера (обход графа по всем ребрам с возвращением в исходную вершину, причем каждое ребро должно быть пройдено только один раз)[1,2];
2) цикл Гамильтона (обход графа по всем вершинам с возвращением в исходную вершину, причем каждая вершина должна быть пройдена только один раз) [1,2].
Однако ни в одной из известных работ, относящихся к обходам графа с возвращением в исходную вершину, не встречается описание обхода плоской укладки графа по всем внутренним граням с возвращением в исходную вершину.
Основное изложение теорем в этой работе будет относиться к -блоку. Дадим определение -блоку. Пусть мы имеем невзвешенный плоский псевдограф , где – множество вершин графа , – множество ребер графа , – множество внутренних граней графа . Назовем внутренними кратными ребрами те кратные ребра, которые не являются смежными с внешней гранью. Назовем внешними те кратные ребра, которые смежны с внешней гранью. Пример внутренних и внешних кратных ребер приведен на рисунке 1.
Рис. 1. Пример внутренних и внешних кратных ребер
На рисунке 1 ребра и являются внешними кратными ребрами, а ребра , , являются внутренними кратными ребрами.
Упростим псевдограф до графа , который будет представлять собой блок без внутренних кратных ребер следующим образом: если в графе есть точка сочленения , связывающая два блока и , то для дальнейшего рассмотрения мы возьмем, не теряя общности, блок . Это допустимо, так как дальнейшее изложение аналогично будет и для блока . Допустим, что блок является мультиграфом (он содержит кратные ребра). Удалим из блока все внутренние кратные ребра, оставив на местах инцидентных им вершин только одно ребро. После этого преобразования блок превратится в граф . Но, не теряя общности, мы можем также предположить, что в графе есть множество точек сочленения и соответственно множество блоков. Упрощение псевдографа все равно будет проводиться по схеме предложенной выше. Пример упрощения псевдографа приведен на рисунке 2.
Рис. 2. Пример преобразования графа в граф
Назовем тип графов, соответствующих графу -блоком.
Постановка задачи
Пусть представлен на плоскости плоский граф , где – множество вершин графа , – множество ребер графа , – множество внутренних граней графа . Допустим, что – -блок. Далее обозначим: – вершина графа , , ; – ребро графа , , ; – внутренняя грань графа , , ; – вершина из которой начинается обход графа. Предположим, что при начатом обходе из вершины мы попадаем в некоторое ребро , которое является смежным с гранями и или, не теряя общности, предположим, что является смежным с гранями , (). Тогда пройдя ребро мы должны принять, что мы прошли строго только одну из граней или . Отсюда сделаем вывод, что задача успешно решена, если мы построим такую цепь , состоящую из звеньев , , , которая при выходе из вершины приведет нас также в вершину пройдя по граням только один раз, ребра также не должны повторятся. Назовем такого вида простую цепь – грань-простой цикл. Таким образом, задача сводится к нахождению общего грань-простого цикла (цикл Белаша) графа . Цепь, которая строится по принципу построения грань-простого цикла, но с конечной вершиной отличной от начальной, назовем грань-простой цепью. Но если такая цепь имеет повторяющиеся грани, то мы ее назовем грань-цепью. А если в цикле повторяются грани, то мы назовем его грань-цикл.
Назовем грань-простой цикл простым самому себе в том случае, если он относится к семейству грань-простых циклов и проходит через различные относящиеся к нему грани только один раз, однако часть этих граней может относиться и к другим циклам из этого семейства. Таким образом, семейство грань-простых циклов будет последовательно покрывать -блок по граням. Ниже мы обоснуем как будет строиться семейство покрывающих-блок циклов.
Пусть – множество последовательно покрывающих граф грань-простых циклов, , - -ый грань-простой цикл. Возьмем два последовательно следующих друг за другом цикла и ,. Цикл будет отличаться от цикла тем, что он будет проходит только один раз через все грани цикла , но при этом он будет содержать также некоторые грани, смежные с уже пройденными гранями цикла . Если на графе существует цикл Белаша, то им будет грань-простой цикл .
Теорема 1. Пусть граф – -блок. Если на этом графе найдется такая грань , что относительно нее можно построить семейство грань-простых циклов имеющее общее подмножество вершин ( ), то последний из этих циклов будет циклом Белаша.
Доказательство. Доказательство проведем методом математической индукции. Шаг индукции обозначим буквой . Построим произвольный граф, удовлетворяющий условиям теоремы и соответствующий шагу индукции (рис. 3).
Рис. 3. Произвольный -блок для шага индукции
Построим цикл Белаша для -блока изображенного на рисунке . Этот цикл изобразим на рисунке 4.
Рис. 4. Цикл Белаша для -блока изображенного на рисунке 3
Из рисунка 4 видна очевидность существования цикла Белаша для произвольного -блока, удовлетворяющего условиям теоремы 1 при . Предположим, что такой цикл существует для произвольного графа на шаге индукции . Достроим граф до графа . Продолжим построение семейства грань-простых циклов уже для графа . Предположим, что грань-простые циклы, покрывающие граф , образуют следующее семейство . Если грань-простые циклы покрыли по граням весь граф, то, очевидно, что последний из них цикл будет циклом Белаша. Но предположим, что только до , возможно последовательно покрывать граф грань-простыми циклами. Иными словами на цикле остается не пройденная какая-то грань . Эта грань останется не пройденной также и на всех последующих циклах начиная от цикла , так как если бы мы ее могли пройти, то она вошла бы в семейство до цикла . Очевидно, что в этом случае не будет и существовать цикла Белаша для графа . Отметим также факт, что если на графе вообще не будет существовать грань, относительно которой можно построить семейство , покрывающее весь граф, то на таком графе и не будет цикла Белаша.■
Следствие 1. Пусть – граф, на котором существует цикл Белаша. Тогда любая вершина , принадлежащая этому циклу, может быть исходной для этого цикла.
СПИСОК ЛИТЕРАТУРЫ:
1. Харари Ф. Теория графов / Пер. с англ. и предисл. В.П. Козырева. Под ред. Г.П. Гаврилова. Изд.2-е. – М.: Едиториал УРСС, 2003. – 296 с.
2. Оре О. Теория графов. Главная редакция физико-математической литературы изд-ва «Наука», 1968 – 216 с.