Две структурные задачи о цепях и циклах в графах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

На правах рукописи УДК 519.1

ТУЛАЙ НАЙЕФ ИБН АЛИ

ДВЕ СТРУКТУРНЫЕ ЗАДАЧИ О ЦЕПЯХ И ЦИКЛАХ В ГРАФАХ

01.01.09 - математическая киАрнетнка

Автореферат

диссертации на соискание учбной степени кандидата физико-математических наук

■■г ел

Новосибирск 1993

Работа выполнена в Новосибирском государственном университете

Научнне руководители: доктор физико-математических наук доцент . А.В.Косточка

кандидат физико-математических наук доцент Л.С.Мельников

Официальные оппоненты: доктор физико-математических наук

доцент В.А.Евстигнеев

кандидат физико-математических наук В.А.Ташкинов

Ведущая организация ВЦ СО РАН

Защита состоится "24" ноября 1993 г. в часов на заседани

специализированного совета Д 002.23.03 по присуждению учёной степе доктора физико-математических наук в Институте математики СО РАН по адресу: 630090, Новосибирск, 90, Университетский проспект, 4, ИМ С диссертацией можно ознакомиться в библиотеке Института математ СО РАН.

Автореферат разослан "19" октября 1993 г.

Учёный секретарь специализированного совета

доктор физико-математических наук А.В.Косточка

I.ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Задача китайского почтальона состоит в нахождении длины кратчайшего замкнутого маршрута, проходящего через все рббра графа. В терминах задачи китайского почтальона можно сформулировать такие оптимизационные проблемы как нахождение наибольшего паросочетания, кратчайшего пути, оптимальных консервативных (±1)-взвешиваний ребер. С ней тесно связаны задача о минимальном покрытии ребер циклами и задача о многопродуктовых потоках на плоскости. Распэ [в] и Джексон [7], получили оценки наихудших решений невзвешенной задачи китайского почтальона для графов без мостов и минимальных 2-рбберно-связных обыкновенных графов. Поскольку эти оценки ненамного отличались от тривиальных, то возникают естественные вопросы:

1) Можно ли улучшить оценки Распэ и Джексона?

2) Найти обширные классы графов, в которых оценки наихудших решений невзвешенной задачи китайского почтальона существенно лучше.

Задача Энтринжера, поставленная в 1973 году, состоит в описании обыкновенных графов в, в которых для каждого а.3£в£|V(а>|, существует ровно один цикл длины в. Она связана с рядом других проблем о циклической структуре графов и некоторым! теоретико-числовыми вопросами.

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

минимальных джойнов в графах, теория эйлеровых графов и теоремы о нигде ненулевых потоках в графах.

научная новизна. Результаты диссертации состоят в следующем:

- описаны все графы g, на которых достигается оценка Распа;

- описаны минимальные 2-рбберно-связные обыкновенные графы g с максимальной длиной пути китайского почтальона;

- описаны 2-связные мультиграфы в с максимальной длиной пути китайского почтальона;

- найдены точные верхние оценки длины пути китайского почтальона в однородных графах и ряде подклассов однородных графов (графы с заданной связностью, с заданным числом малых разрезов, т-атомные графы идо.);

- получено описание внешнепланарных графов Энтринжера;

- описаны все гра$ы Энтринжера с цикломатическим числом, меньшим шести;

- описаны все эйлеровы графы Энтринжера с цикломатическим числом, меньшим восьми.

практическая и. теоретическая иенность. Результаты и метода главы 2 будут использованы для дальнейшего изучения строения решений задачи китайского почтальона. Идеи главы 3 могут помочь при решениии задач о циклической структуре графов.

апробация работы. Результаты диссертации докладывались на семинарах "Эстремальные задачи на графах", "Дискретный анализ" и семинаре отдела теоретической кибернетики Института математики СО РАН, семинаре под руководством профессора В.К.Попкова на ВЦ СО РАН. публикация. По теме диссертации опубликованы две работы ti] и [2]. структура и объем работы. Диссертация состоит из введения, трбх глав основного текста и списка литературы. Объем работы - 120

страниц.

II.КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении даны постановки задач, сделан обзор предшествующих работ и сформулированы основные результаты работы.

В диссертации рассматриваются вопросы, касающиеся задачи китайского почтальона и задачи Энтринжера. Главы I и 2 посвящены задаче китайского почтальона, а глава 3 посвящена задаче Энтринжера. Полученные результаты сформулированы в девяти теоремах.

Все неопределённые понятия можно найти в книге Харари [3]. Мы рассматриваем только связные конечные граф*. Пусть g - граф, через v(g) и ecg) обозначим множества вершин и рббер графа g, соответственно. Тогда задача китайского почтальона заключается в том, чтобы найти длину кратчайшего замкнутого обхода, содержащего все рббра графа g. Путбм почтальона называется любой кратчайший замкнутый маршрут, проходящий по всем ребрам графа g. Через p(g) обозначим один из путей почтальона. Длина пути почтальона |P(G)i -это число ребер, содержащихся в нбм.

Известно, что если g - эйлеров граф, то |р(бл =|е(в) i . Значит, проблема нахождения длины пути китайского почтальона возникает, когда в о имеются нечбтные вершины (т.е. вершины нечбтной степени). Можно переформулировать задачу китайского почтальона как задачу нахождения минимального эйлерова графа, содержащего данный граф. Пусть g - не эйлеров граф и f - множество ребер, которые проходятся более одного раза по пути pío. Известны следующие факты:

1) каждое ребро множества г проходится точно двазды по pig);

2) |P(G)|-|E(G)|+|F|;

3) суграф H(V(G).F) не содержит циклов;

4) в любом простом цикле число рббер, которые проходятся дважды, не

превосходит половины длины цикла.

Из (2) и (3) следует, что |Р(в)|<|Е(б)|+п-1, где п=|У(в)г.

Как упоминалось, задача китайского почтальона связана с задачами нахождения длины циклического покрытия рббер I с(о | и нахождения длины циклического покрытия вершин |Су(в)|. Напомним, что с(б) -множество таких простых циклов,-что любое ребро графа в принадлежит по крайней маре одному циклу этого множества, причбм сумма длин циклов этого множества минимальна. Аналогично определяем (только вместо рббер используются вершины).

Очевидно, что |Р(01<|С(в)|, для любого графа без мостов. Однако уже для графа Петерсена длина'кратчайшего покрытия циклами больше длины пути китайского почтальона. В связи с этим в работах йтаи и Роде [6] предлагается следувдая гипотеза: ГИПОТЕЗА I. Если в - обыкновенный граф без мостов, то

|С(б)|=|ЕСО|+|У(6)|-1. (I)

Так как нахождение длины циклического покрытия рббер |С(0| сложнее, чем нахождение длины пути китайского почтальона |Р(0|, то многие пытались найти классы графов в, для которых 1Р(б)|=|С(в)|. Например, Бермонд. Джексон и Жежв [4] доказали, что если в -пленарный граф без мостов или 4-связный граф, то |Р(б)|=|С(в)|. Поэтому полезно получить оценку длины пути почтальона. Например, Распз [8] доказал, что если в - обыкновенный связный граф без мостов, отличный от к , то

4

|Р(6)|<|Е(в)|+|У(6)|-Э. (2)

В диссертации описаны все классы графов, для которых оценка (2) достигается. Зтот результат сформулирован в теореме I.

Пусть кзт (1=1.2.3) - графы, полученные из кэт добавлением 1

б

рёбер соответственно в доля, содержащув три вершины, а гк4 получен склеиванием по вершине двух графов к4.

ТЕОРЕМА I. Пусть о - обыкновенный связный граф без мостов, отличный от 2К. . к .к* .к! . к* , И 1 У(<3)) >е. Тогда

4 Э.т 3,т Э,т Э.гп * ^

|Р(6)|<|Е(6)|+|У(в)|-4 . Следующая гипотеза, предложенная в работе Бермонд. Джексон и Жеже [4], связана с оценкой длины циклического покрытия вершин |су(б)|. ГИПОТЕЗА 2. Если б - обыкновенный связный граф без мостов, то

|Су.(в)|< 2(|У(в)'|-1), (3)

На самом деле, эта гипотеза сильнее, чем гипотеза I. Для того чтобы убедиться в справедливости этой гипотезы, достаточно доказать оценку (3) для минимальных 2-рёберно-связных обыкновенных графов. В связи с этим, Распэ доказал [в], что если в - минимальный 2-рёберно-связный обыкновенный граф, то

|Р<0)|< 2{|У(6)|-1). В диссертации этот результат улучшен.

ТЕОРЕМА 2. Пусть в - минимальный 2-рёберно-связный граф, таи>з и хотя бы один блок графа в не является треугольником и отличен от графов к2т и к2т (т - нечётно) . Тогда

|Р(б)| < 2( | У(0 I - 2).

Здесь к2т - граф, полученный из полного двудольного графа кгт путём замены одного из рёбер на путь длины 2.

Другой результат, связанный с этой темой, сформулирован в теореме 3. ТЕОРЕМА 3. Пусть в - 2-связный мультиграф и |У(0|>2. Тогда |Р(6)|<|Е(6)|+|У(0|-2. Отметим, что невозможно улучшить оценку

|Р101<|Е(6)|+п-*, (4)

в классе (к-п-рёберно-связных обыкновенных графов, потому что для

полных двудольных графов к^ , при нечётном к потребуется п-к рёбер, чтобы получить эйлеров граф из исходного графа к^ n k . Здесь возникает вопрос:, можно ли улучшить оценку (4) для какого-то большого класса графов и получить оценку вида

|p(g)|<|e(g)|+an, где а<1. Оказалось, что это возможно для однородных графов. Прежде чем привести результаты нам необходимы следующие понятия.

Назовем джойном в графе g подграф hcv(G).f), где v(g) - множество вершин исходного графа g, f - множество ребер, которые проходятся дважды по p(g). Через r(g) обозначим минимальное возможное число рббер в даойне графа g. Очевидно, что

. ip(g)|-|e(g)|+r(g). Таким образом, нахождение длины пути китайского почтальона эквивалентно нахождению мощности дкойна. Теперь приведём несколько определений.

Подмножество s рёбер графа g называется рёберным разрезом, если его удаление увеличивает число компонент связности и s минимально по включению относительно этого свойства. Скажем, что s -нечетный разрез, если isi нечетно. В (2k+i)-однородном графе разрез s назовём малым, если isi<2k. Для (2k+n-однородного графа g-(v.e) пусть г(б) - наибольшее возможное число малых нечетных разрезов таких, что каждое ребро графа в принадлежит не более чем двум разрезам.

в (2k+i)-однородном графе g без малых нечётных разрезов по теореме Татта t(G)»|V|/2 . Оказывается, для того, чтобы т(в) было велико, необходимо наличие в g большого числа малых нечетных разрезов. Мы покажем, что через г(в) можно оценить сверху т ígj-i v)/2 для (2k+i)-однородного 2<:-рб0ерно-связного графа.

В связи с этим в главе 2 получены следующие результаты.

ТВОРЕНА. 4. Пусть в-(У.Е) - (2к+1)-однородный 21-реберно-связный граф. Тогда

г (в)-| VI /2 < шах | О. .

Оценка теоремы достигается для любых 05«к на бесконечном множестве (2к+1)-однородных (21+1)-рбберно-связных (в том числе и обыкновенных) графов.

Скажем, что (2к+1)-однородный граф б является т-атошшы, если для любого малого нечетного разреза я каждая из компонент графа (зчэ имеет не менее т вершин. Поскольку в описанной ситуации обе компоненты в\з имеют по нечетному количеству вершин, то достаточно рассматривать т-атомнне графи для нечетных т. Заметим, что любой (2к+1)-однородный псевдограф без петель является з-атомным, а обыкновенный (2к+д.) —однородный граф - (2к+3)-атомным графом.

ТЕОРЕМА 5. Пусть 6»(У,Е) - (2к+1)-однородный 2Ь-рбберно-связный т-атомный граф (т нечетно). Тогда

т (в) —| VI /2 < шах { 0. ] •

Оценка этой теореда тоже достигается для любых о<кх и любах нечетных ш>о на бесконечном множестве т-атомных (2к+1)-однородных {21+1)-рбберно-связных графов. В частности, справедливо

СЛЕДСТВИЕ I. Максимум г(в) по всем (2к+1)-однородным 21-рббер-но-связным графам без петель на п вершинах равен

пах | п/2. п/2 + .

СЛЕДСТВИЕ 2. Максимум т (О по всем (2к+1)-однородным 2Ъ-рббер-но-связннм обыкновенным графам на п вершинах не превосходит

{ П/2' П/2 + Цк+1)/(к-о1(к+2) } '

Оценка в следствии 2 точна при - В других

случаях ее можно еще улучшить. Мы улучшили еб при [(к+о/(к-1).]2=1 и получили следующий результат.

ТЕОРЕМА 6. Пусть б-(У,Е) - (2к+1)-однородный г^рбберно-связный обыкновенный граф и 31+1< к. Тогда

,,<„,(„ (Зк-Р| VI - с 1 /2 < таж | О. а(2вк*1-1)-1 -

ГДе с=2(5к+9к-КЗк+б)+1).

Оценка этой теоремы тоже достигается для любых 0£Кк, где 31+1< к на бесконечном множестве (2к+1)-однородных (21+1)-рбберно-связных обыкновенных графов. Отметим еще, что асимптотика подученных оценок ближе к п/2 чем-к п.

Глава 3 посвящена изучению проблемы Энтринжера [5]: описать обыкновенные графы в такие, что для любого е. з<в<п. где п - число вершин в, <3 содержит ровно один цикл длины в. Такие графы назовбм графами Энтринжера.

Отметим, что если 6 - граф Энтринжера, то число рббер в нбм не больше, чем п+ г в"-*5—эха оценка достигается, если в -внешнепланарный граф и обладает свойством Энтринжера. А если б -граф Энтринжера и не является внешнепланарным, то число рббер в нбм не больше п+ у ~5 .

Это говорит нам о том, что если минимальная степень графа строго больше 2, то он не является графом Энтринжера.

В связи с этим получены три результата:

ТЕОРЕМА 7. Среди внешнепланарных графов, графы Энтринжера исчерпываются четырьмя графами, изображенными на рис.1.

ю

рис I

ТЕОРЕМА 8. Среди обыкновенных графов а с |Е(б)|<|У<с)|+4 гра(|ы Энтринжера исчерпываются семью графами, изображенными на рис.

I и 2.

Рис 2.

ТЕОРЕМА 9. Если о - эйлеров граф и |Е(0|<|У(В)|+б, то 6 не является графом Энтринжера, если только он не треугольник.

В заключение автор выражает благодарность Л.С.Мельникову и А.В.Косточке за постановку задач и постоянное внимание к работе.

РАБОТЫ АВТОРА ПО ТШЕ ДИССЕРТАЦИИ

1. Тулай.Н. Экстремальные гра$ы для задачи китайского почтальона. "Метода дискретного анализа в теории графов и сложности", Л 52, Новосибирск. ИМ, 1992, с.102-111.

2. Тулай.Н. О длине пути китайского почтальона для минимальных 2-рЗберносвязных графов."Метода дискретного анализа в теории графов

и сложности", JE 52, Новосибирск, ИМ, 1992, с.94-101.

СПИСОК ЛИТЕРАТУРЫ

3. Ф.Харари, Теория графов, "Мир", Москва, 1973.

4. J.C.Bermond. B.Jacoon, F.Jaeger, Shortest covering of grahps with cycles. J.Combinatorial Th. (B) 35 (1983). pp. 297-308.

5..J.A. Bondy. U.S.R.Murty. Graph theory with applications. NORTH-HOLLAND. New York. 1976.

6. A.Itai and K.Rodeh. Covering a graph by circuits, in: Automata. Languages and Programming, Lecture Notes in Computer Science. 10 (1981) pp.746-754.

7. B.Jackson, Shortest circuit covers and postaan tours in graphs with a nowhere-zero 4-flow. 1990. No 4, pp 659-665.

8. A.Rcspaud, Postman tours and cycle covers. Discrete Math., 111(1993), pp.447-454.

Подписано к печати 7.10Л993 Формат бумаги 60 84 I/I6 Тираж 100 экз.

Объем 0,75" п.л. Заказ Si.

Отпечатано на ротапринте Института математики СО РАН