Обобщённые ромашки в k-связном графе

• Автор: Глазман, Александр Львович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Санкт-Петербург
• Количество страниц: 135 с. : ил.

Оглавление
Введение
Связность

Структура разбиения Аьсвязного графа

Результаты диссертации

Ромашки в ^-связном графе

Ромашки в четырехсвязном графе

Структура диссертации

1 Обобщенные ромашки в Аг-связном графе

2 Ромашки в четырехсвязном графе

2.1 2-Ромашки

2.2 О-Ромашки

Введение
Теория графов является одним из важнейших и интереснейших разделов математики. В различных областях математики — алгебре, топологии, информатике и других — возникает потребность описания свойств тех или иных объектов на языке теории графов и использования результатов теории графов, что подчеркивает значимость изучения графов и их свойств.
В диссертации рассматриваются неориентированные графы без петель и кратных ребер. Множество вершин графа Є будем обозначать через У{Є), а множество ребер — через Е(С). Степень вершины у в графе Є мы будем обозначать через Ф?(и).
Связность
Граф называется связным, если от любой его вершины можно дойти по ребрам до любой другой. Несвязный граф разбивается на компоненты связности — наибольшие по включению связные подграфы.
Множество вершин графа называется разделяющим, если при его удалении граф становится несвязным. Граф называется вершинно к-связным, если в нем более к вершин и нет разделяющего множества, содержащего менее к вершин. В частности, при к = 2 такой граф называется двусвязным, при к = 3 — трехсвязным, а при к — 4 — четырехсвязным.
Понятие А;-связности является естественным обобщением понятия

связности графа и по этой причине имеет большое теоретическое и практическое значение. Многие практические задачи, в частности, имеющие отношение к надежности различных систем связи и транспортных сетей, могут быть сформулированы в терминах вершинной связности подходящих графов. Некоторые примеры использования вершинной связности можно найти в книге [20, глава 20].
Аналогично вершинной /г-свзяности определяется реберная fc-связность, которая изучалась многими исследователями и имеет много интересных свойств. Однако в данной диссертации мы будем иметь дело только с вершинной ^-связностью, поэтому для сокращения далее вершинно /г-связные графы мы будем называть просто к-связными.
Связностью двух вершин х и у графа G называется наименьшее количество вершин, которое необходимо удалить из G для того, чтобы в оставшемся графе вершины х и у оказались в разных компонентах связности. Первым свойства связности графа начал изучать К. Menger [13], в 1927 году доказавший следующую теорему: для любых двух несмежных вершин х,у их связность в графе G равняется наибольшему количеству непересекающихся простых путей между х и у в графе G. Позднее, в 1932 году Н. Whitney [19] сформулировал критерий /с-связности графа: граф является /с-связным тогда и только тогда, когда в нем более к вершин и для любых двух вершин х,у найдется к соединяющих их путей, попарно не имеющих общих вершин.
Во второй половине XX века активно проводились исследования связности графов. Одним из направлений этих исследований были вопросы о сохранении графом свойства /с-связности при удалении его вершин или ребер. Эти вопросы привели к введению понятий критических и минимальных /г-связных графов, /с-связный граф называется критическим, если при удалении любой его вершины он перестает быть

Противоречие с пунктом 1 леммы 1.2.

Введем определение множества вершин ромашки и максимальной ромашки, которые нам пригодятся в дальнейшем.
Определение 18. Мнооюеством вершин ромашки назовем множество И(Р), состоящее из всех вершин графа, лежащих в центре или хотя бы в одном ее лепестке. Будем говорить, что ромашка Р содержит ромашку Р', если у них общий центр и V(Р') с У{Е). Назовем ромашку і71 максимальной, если все ромашки, в которых она содержится, имеют то же множество вершин, и лепестков в них не больше, чем в Р.
Лемма 1.8. Для обобщенной ромашки F = (Р; <31,..., <3т) выполняются следующие утверждения.
1) Пусть (Зі и (3] — это два таких ее различных лепестка, что г ф І — 1. Тогда если хотя бы одна из частей Счц-1 или непуста, то С(1п 1((7у)) связен и непуст.
2) Пусть (Зі и — это два таких ее различных лепестка, что і ^ 3 — 1. Тогда если С(1п1(Сг-^)) несвязен, то в Іп^Сг^-) вершин не больше, чем в лепестке ромашки Р.
3) Если (Зі и Qj — это два не соседних, но близких лепестка, то (Зі^ не является разделяющим множеством.
4) Множество (Зі,і+і не разделяет миоэюество У(Р).
Доказательство. 1) Предположим, что одна из частей Сц,у_і и С?г+ непуста. Не умаляя общности, это С?у-і. Тогда в ее внутренности найдется некоторая вершина V. Обозначим через и произвольную вершину лепестка <3.7-1, не лежащую в <3Г Заметим, что если <3г,у не является разделяющим множеством, то по теореме 1 лепестки (Зі и Qj близки, и либо часть С?г,7 пуста (что невозможно, так как часть С7гд_і непуста), либо часть пуста, и тогда С(1п1((?г,;)) = (? — <3гу (а этот граф связен,