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

Оглавление
Введение 4
Связность ...................................................... 4
Блоки в ^-связном графе. Структура разбиения /г-связного графа б
Результаты диссертации.......................................... 10
Разделяющие множества и части разбиения.................... 10
Блоки й-связного графа..................................... 13
Зависимые и независимые множества. Компоненты зависимости ........................••....................... 13
Ромашки.................................................... 15
Слабо нерасщепимые графы................................... 17
Структура диссертации........................................... 19
1 Основпые понятия 21
1.1. Части разбиения................................... . . . 21
1.1.1. Представление части разбиения в виде пересечения 22
1.1.2. Граница и внутренность..................*.......... 25
1.1.3. Блоки...........'.................................. 26
1.2. Зависимые и независимые разделяющие множества ... 27
1.2.1. Независимые разделяющие множества................... 28
1.2.2. Разбиение ^-связного графа парой зависимых /^-разделяющих множеств .................................. 30
1.3. Свойства правильных частей разбиения....................... 32
2 Компоненты зависимости набора разделяющих множеств 35
2.1. Пополнение и замыкание набора разделяющих множеств 35
2.2. Компоненты зависимости набора разделяющих множеств 38
2.3. Новые свойства пополнения и замыкания набора разделяющих множеств................................... 45
2.4. Разбиение графа набором из попарно независимых множеств .................................................... 46
2.5. Процесс разбиения ^-связного графа............... 49
3 Ромашки и квазиромашки 52
3.1. Циклический порядок лепестков квазиромаитки...... 52
3.2. Разбиения без малых частей....................... 60
3.3. Сруктура разбиения двусвязного графа............. 71
4 Слабо нерасщепимые графы. Основные свойства 74
5 Структура разбиения слабо нерасщенимого ^-связного
графа 79
5.1. Классы ^-разделяющих множеств.................... 79
5.2. Доминирующие множества. Границы и внутренняя область класса.................................... 86
5.3. Множества независимого класса.................... 94
5.4. Множества большого комплекса.....................101
5.5. Разбиения графа комплексами......................117
Литература
136
— 4 —
Введение
Теория графов является одним из важнейших и интереснейших разделов математики. В различных областях математики — алгебре, топологии, информатике и других — возникает потребность описания свойств тех или иных объектов на языке теории графов и использования результатов теории графов, что подчеркивает значимость изучения графов и их свойств.
В диссертации мы будем рассматривать неориентированные графы без петель и кратных ребер, множество вершин графа С мы всегда будем обозначать через Г (С), а множество его ребер — через Е{<3).
Связность
Одним из основных понятия в теории графов является понятие связности. Граф называется связным, если между любыми двумя его вершинами существует путь. Множество вершин несвязного графа разбивается на компоненты связности. (Под компонентой связности мы понимаем максимальное по включению множество вершин графа, любые две из которых связаны путем.)
Граф называется (вершинно) к-связным, если в нем не менее к + 1 вершин и при удалении любых к — 1 вершин получается связный граф. Связностью двух вершин х и у графа С называется наименьшее количество вершин, которое необходимо удалить из О для того, чтобы в оставшемся графе вершины х и у оказались в разных компонентах связности. Вершинная связность двух смежных вершин считается равной -Ьоо. Обозначается вершинная связность х и у через ко(х,у). Вершинная связность графа О — это наименьшая вершинная связность
пары его вершин. Таким образом, граф является ^-связным тогда и только тогда, когда его вершинная связность не менее к.
Понятие вершинной /с-связыости является обощение понятия связности и по этой причине имеет большое теоретическое и практическое значение. Многие практические задачи, в частности, имеющие отношение к надежности различных систем связи и Транспортных сетей, могут быть сформулированы в терминах вершинной связности подходящих графов. Некоторые примеры использования вершинной связности можно найти в книге [1, глава 20]. Вершинная связность графа и набор вершинных связностей пар его вершин являются важными характеристиками графа. Эти характеристики графа находят применение в описании свойств планарных графов и в топологии [10, глава 11]. Существуют связи между вершинной связностью графа и его алгебраическими характеристиками.
Начало исследований свойств вершинной связности графа положил в 1927 году К.Мевдег [27], доказавший следующую теорему: для любых двух несмежных вершин х,у связность кс{х,у) равняется набольшему количеству непересекающихся простых путей между X и у в графе О.
С 60-х годов XX века активно проводились исследования по вершинной связности графов. Многих исследователей интересовали вопросы о сохранении Ж-связности графа при удалении его вершин и ребер и об описании критических и минимальных к-связных грат фов (то есть, к-связных графов, перестающих быть ^-связными при удалении любой вершины или любого ребра соответственно). Наиболее сильные результаты по минимальным /с-связным графам получили КНаПп [12, 13, 14, 15] и \V.Mader [22, 23, 24, 25]. В работах [11, 22, 32, 16, 7] изучались критические ^-связные графы и вопро-
— 6 —
сы о том, при каких условиях в 6-связном графе существует вершина, удаление которой не нарушает 6-связность графа, и какие вершины данного графа удовлетворяют этому свойству.
Еще одно направление, в котором активно проводились исследования по вершинной связности — это построение редукционных теорий, позволяющих при помощи последовательности таких операций, как удаление и стягивание ребер, свести произвольный 6-связный граф к 6-связному графу достаточно простой структуры (при этом все промежуточные графы, возникающие на данной последовательности операций, также должны быть 6-связными). Классическим примером такой теории является теория Татта [30, 9, 31], утверждающая, что из любого трехсвязного графа при помощи удаления и стягивания ребер можно получить колесо — граф, состоящий из простого цикла и вершины, смежной со всеми вершинами этого цикла. Аналогичные теории для 6 = 2 и 6 = 4 описаны в работах [18] и [28] соответственно. Вопрос о возможности построения подобной теории для произвольного 6 обсуждается в работе [29].
Блоки в /с-связном графе. Структура разбиения А>связного графа
Еще одно направление исследований по вершинной связности — это исследование структуры разбиения 6-связных графов минимальными по количеству вершин разделяющими множествами. Интерес к этому направлению объясняется тем, что важную роль в изучении свойств связных графов играют блоки, точки сочленения и их структура. Блоком связного графа <7 называется его максимальный по включению двусвязный подграф, а точкой сочленения — вершина, удаление которой Делает граф несвязным. Структуру блоков и точек сочленения связ-
— 7 —
ного графа отображает дерево блоков и точек сочленения ([10, глава 4]). Вершины этого дерева соответствуют блокам и точкам сочленения связного графа (7, а ребра соединяют любой блок с содержащимися в нем точками сочленения. Таким образом, можно говорить о разбиении связного графа на блоки. Подробно структура и свойства блоков и точек сочленения связного графа описана в [2, 10]. В [10] можно найти примеры использования этой структуры, причем не только в теории связности.
Конструкция разбиения графа на блоки полезна для описания структуры связности графа. Так, все вершины, при удалении которых граф остается связным — это внутренние вершины блоков (то есть, вершины, не являющиеся точками сочленения). Более того, при одновременном удалении нескольких внутренних вершин разных блоков граф остается связным. Это обстоятельство, в частности, позволяег построить в связном графе, степени всех вершин которого не менее трех, остовное дерево с большим количеством висячих вершин [3].
В связи с важностью теории блокои и точек сочленения для изучения свойств связных графов неоднократно предпринимались попытки обобщить эту теорию на случай А>связных графов. Авторы ряда работ (например, [17], [10] и [26]) предлагали называть ^-блоком или ^-компонентой графа (7 максимальный по включению ^-связный подграф графа С. При очевидной аналогии в определении с блоками связного графа, свойства вводимых таким образом ^-блоков имеют мало аналогий со свойствами классических двусвязных блоков связного графа.
Более перспективным оказался другой подход к определению блока ^-связного графа, также имеющий аналогию с классическими двусвязными блоками связного графа. Рассмотрим процесс последователь-
— 8 —
ного разбиения связного графа С его точками сочленения. Пусть V — точка сочленения графа. (7, а С'І5... ,С'П — компоненты связности графа Ст — V. Пусть граф получен из С\ добавлением вершины V и всех выходящих из нее к вершинам графа С\ ребер графа О. Тогда графы Сі,... ,С?„ оказываются связными, все их точки сочленения являются точками сочленения графа С и, наоборот, любая точка сочленения графа О является точкой сочленения одного из полученных графов. Продолжим процесс разбиения до тех пор, пока все полученные графы не окажутся дву связными. В [2, 10] доказано, что вне зависимости от порядка, операций мы получим разбиение графа (? на блоки. При таком определении блоков сразу же видно, что структуру их взаимного расположения отображает дерево.
Первую попытку предложить похожую конструкцию для описания разбиения двусвязного графа на блоки сделал Б. МасЪапе [21] в 1937 году. В 1966 году \¥.Т. Ти^е [31] подробно описал конструкцию разбиения двусвязного графа его 2-разделяющими множествами (то есть, множествами из двух вершин, удаление которых делает граф несвязным). Эта конструкция является естественным обобщением для двусвязного графа алгоритмического подхода к определению классического блока. Основное отличие шага процесса разбиения двусвязного графа [31] от шага процесса построения классических блоков состоит в том, что после “разреза” двусвязного графа по некоторому его 2-разделяющему множеству к каждому из образовавшихся подграфов (порожденному вершинами одной из компонент связности, образовавшейся при удалении 2-разделяющего множества, и вершинами самого 2-разделяющего множества) добавляется так называемое виртуальное ребро, соединяющее вершины данного 2-разделяющего множества. Процесс продолжается до тех пор, пока все полученные графы не окажутся трехсвязиыми. Данная конструкция дает просто описываемый процесс разбиения дву-
связного графа на блоки, что позволяет построить дерево, являющееся естественным обобщением для двусвязного графа понятия дерева блоков связного графа. Детальное описание данной конструкции можно также найти в работах [20] и [9].
Однако, долгое время не было попыток обобщить понятие блоков на к-связные графы при к > 2 и построить структуру разбиения /^-связного графа его ^-разделяющими множествами. В 1992 году W. Hohberg в работе [19] предложил обобщение описанной выше конструкции последовательного разбиения графа на случай fc-связного графа для произвольного к. В работе [19] содержится ряд полезных свойств разделяющих множеств графов. Основным недостатком предложенной в [19] конструкции является то, что получаемые в результате блоки сильно зависят от процесса разбиения и, тем более, нельзя говорить о единственности структуры разбиения.
Диссертант и А. В. Пастор в работе [7] рассмотрели класс слабо не-расщепимых fc-связных графов (этот класс является достаточно большим: в него входят все к-связные графы, степени вершин которых не менее Разбиение слабо нерасщепимого /с-связного графа на блоки,
также определяемые как результат процесса последовательных разрезов графа но разделяющим множествам, оказывается в некотором смысле единственным: между блоками, получающимися в результате различных способов разбиения, можно установить взаимно однозначное соответствие так, что соответствующие блоки будут изоморфны, а множества их внутренних (то есть, не входящих в /с-разделяющие множества) вершин будут совпадать.
В настоящей диссертации мы используем другой подход к определению блоков в /г-связном графе, впервые предложенный диссертантом в работе [4]. Блок к-связного графа G определяется, как максимальное
- 10 —
по включению подмножество множества У(С) такое, что вершинная связность любых двух из этих вершин не менее к 4- 1. Отметим, что при данном определении блок — это не граф, а множество вершин. Такое определение намного проще алгоритмического определения блока и, на первый взгляд, больше похоже на подход к определению блока из [17, 26, 10]. Более того, наш блок является объединением множеств вершин нескольких максимальных но включению ^-связных подграфов графа <2, которые предлагалось рассматривать в качестве блока в этих работах. Однако, в главе 2 диссертации показана связь между нашими блоками и процессом последовательного разбиения графа его ^-разделяющими множествами. Новый подход значительно упрощает работу с блоками /г-связного графа.
Результаты диссертации Обозначения
Пусть С — произвольный граф. Для ТУ С У(С7) через О — ТУ мы будем обозначать граф, который получается при удалении из (7 всех вершин множества ТУ и всех выходящих из них ребер. Для і7 С Е(Є) через С? — Р мы будем обозначать граф, который получается при удалении из Є всех ребер множества Р (то есть, Є — Р = (V(С7), Р(С)\Р)). Через 5(0) мы будем обозначать минимальную степень вершины графа Ст.
Разделяющие мпожсства и части разбиения
Определение 1. Пусть О — произвольный граф. Назовем множество И С V ((7) разделяющей множеством графа Є, если граф О — Я несвязен. В случаях, когда необходимо указать количество элементов
11 —
разделяющего множества, мы будем называть разделяющее множество из х вершин х-разделяющим.
Операцию удаления из графа разделяющего множества Я. (в результате которой получается несколько компонент связности) мы будем называть разрезом графа О по множеству Я.
В /с-связном графе нет разделяющих множеств, состоящих менее, чем из к вершин. Обозначим через 91((?) набор из всех разделяющих множеств ^-связного графа а через 91*.. ((7) — набор из всех его ^-разделяющих множеств.
Определение 2. 1) Пусть Я,Х С ^г(£), причем X Я. Будем говорить, что множество Я разделяет множество X с Е'(С), если не все вершины из X \ Я лежат в одной компоненте связности графа С - Я.
2) Пусть Г/, И7 с У(С). Будем говорить, что множество Я отделяет множество и от множества И7, если V (£_ І?,, И7 £ Я и никакие две вершины и Є II \ Я и и> Є И7 \ Я не лежат в одной компоненте связности графа Є — Я.
Определение 3. Пусть © С 91 ((2).
1) Часть разбиения графа С набором © (или часть ©-разбиения) — это максимальное по включению множество А С V (С) такое, что никакое множество 5 € © не разделяет А. Будем обозначать через Р(©) множество из всех частей ©-разбиения. Если набор © сотоит из одного множества 5, то будем обозначать множество всех частей {5}-разбиения через Р(5).
2) Вершины части А 6 Р(в), не входящие ни в одно из множеств набора ©, будем называть внутреннимщ а множество всех таких вершин — внутренностью части А, которую будем обозначать через 1(А). Вершины части /1, входящие в какие-либо множества из ©, мы будем