Введение
Будем говорить, что граф укладывается на поверхности , если его можно так нарисовать на
, что никакие два его ребра не пересекаются. Граф называется планарным, если его можно уложить на плоскости; плоский граф – это граф, уже уложенный на плоскости. Области, определяемые плоским графом, назовем его внутренними гранями[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 с.
Библиографическая ссылка
Белаш А.Н. ПОЛНЫЙ ОБХОД ПО ВНУТРЕННИМ ГРАНЯМ α-БЛОКА С ВОЗВРАЩЕНИЕМ В ИСХОДНУЮ ВЕРШИНУ (ЦИКЛ БЕЛАША) // Современные проблемы науки и образования. – 2008. – № 6. ;URL: https://science-education.ru/ru/article/view?id=1131 (дата обращения: 11.02.2025).