Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,791

COMPLETE GRAPH DETOUR ON INTERIOR FACES OF α-BLOCK WITH RETURNING TO STARTING APEX (CYCLE OF BELASH)

Белаш А.Н.
Статья описывает обзор существующих обходов планарных графов. Представлена проблема обхода графа по граням (цикл Белаша). Статья описывает главный подход к решению этой проблемы. Материал касается только альфа блока. Некоторые следствия теорем о цикле Белаша представлены в работе. Автор объясняет, где может существовать цикл Белаша.
The article represents the review of existing detours of the plane graphs. The problem of the detour of the graph on the faces (cycle of Belash) is presented. The article describes the general approach to a solution of this problem. The material concerns only alpha block. Some corollaries of theorems of the cycle of Belash is described here. The author explains where there can be a cycle of Belash.

Введение

Будем говорить, что граф укладывается на поверхности , если его можно так нарисовать на , что никакие два его ребра не пересекаются. Граф называется планарным, если его можно уложить на плоскости; плоский граф – это граф, уже уложенный на плоскости. Области, определяемые плоским графом, назовем его внутренними гранями[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 с.