Обобщённые ромашки в k-связном графе тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Глазман, Александр Львович

• Глазман, Александр Львович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Глазман, Александр Львович

Оглавление

Введение

Связность

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

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

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

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

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

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

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

2.1 2-Ромашки

2.2 О-Ромашки

Введение диссертации (часть автореферата) на тему «Обобщённые ромашки в k-связном графе»

Введение

Теория графов является одним из важнейших и интереснейших разделов математики. В различных областях математики — алгебре, топологии, информатике и других — возникает потребность описания свойств тех или иных объектов на языке теории графов и использования результатов теории графов, что подчеркивает значимость изучения графов и их свойств.

В диссертации рассматриваются неориентированные графы без петель и кратных ребер. Множество вершин графа С? будем обозначать через У(С), а множество ребер — через Е(С). Степень вершины V в графе С мы будем обозначать через (1с{у).

Связность

Граф называется связным, если от любой его вершины можно дойти по ребрам до любой другой. Несвязный граф разбивается на компоненты связности — наибольшие но включению связные подграфы.

Множество вершин графа называется разделяющим, если при его удалении граф становится несвязным. Граф называется вершинно к-связным, если в нем более к вершин и нет разделяющего множества, содержащего менее к вершин. В частности, при к = 2 такой граф называется двусвязным, при к = 3 — трехсвязным, а при к — 4 — четырехсвязным.

Понятие /¿-связности является естественным обобщением понятия

связности графа и по этой причине имеет большое теоретическое и практическое значение. Многие практические задачи, в частности, имеющие отношение к надежности различных систем связи и транспортных сетей, могут быть сформулированы в терминах вершинной связности подходящих графов. Некоторые примеры использования вершинной связности можно найти в книге [20, глава 20].

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

Связностью двух вершин х и у графа G называется наименьшее количество вершин, которое необходимо удалить из G для того, чтобы в оставшемся графе вершины х и у оказались в разных компонентах связности. Первым свойства связности графа начал изучать К. Menger [13], в 1927 году доказавший следующую теорему: для любых двух несмежных вершин х,у их связность в графе G равняется наибольшему количеству непересекающихся простых путей между хну в графе G. Позднее, в 1932 году H.Whitney [19] сформулировал критерий /¿-связности графа: граф является /¿-связным тогда и только тогда, когда в нем более к вершин и для любых двух вершин х, у найдется к соединяющих их путей, попарно не имеющих общих вершин.

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

к-связным. Аналогично, /¿-связный граф называется минимальным, если при удалении любого его ребра он перестает быть /¿-связным. Наиболее сильные результаты по минимальным /¿-связным графам получили Я. НаНп [2-5] и \У. Мас1ег [9-12]. В работах [1,6,9,18,23] изучались критические /¿-связные графы и вопросы о том, при каких условиях в /¿-связном графе существует вершина, удаление которой не нарушает /¿-связность графа, и какие вершины данного графа удовлетворяют этому свойству.

Другое направление, в котором активно проводились исследования связности графа — это построение редукционных теорий, позволяющих при помощи последовательности -операций удаления и стягивания ребер, свести произвольный /¿-связный граф к /¿-связному графу достаточно простой структуры (при этом все промежуточные графы, возникающие на данной последовательности операций, также должны быть /¿-связными). В [16,27] Татт доказал, что любой трехсвязный граф при помощи последовательного удаления и стягивания ребер можно привести к колесу — графу, состоящему из простого цикла и вершины, смежной со всеми вершинами этого цикла. В работах [7] и [14] описаны аналогичные теории для к = 2 и к = 4. Случай произвольного к обсуждается в работе [15].

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

Еще одно направление исследований связности графа — это вопросы, касающиеся структуры разбиения /¿-связного графа разделяющими множествами, содержащими по к вершин.

Структура разбиения связного графа его точками сочленения (то есть вершинами, удаление которых делает граф несвязным) описана в [28]. Для описания этой структуры удобно использовать так называемое дерево блоков и точек сочленения, вершинами которого являются точки со-

членения и блоки — максимальные по включению двусвязные подграфы. Структура дерева блоков и точек сочленения является очень важной характеристикой графа и описывает факторизацию многочлена Татта, который в свою очередь является фундаментальным объектом в теории графов и не только — его частными случаями являются хроматический многочлен (ищущий число правильных раскрасок графа в к цветов) и инвариант узла — многочлен Джонса (в случае узлов специального вида — альтернирующих узлов). В [28] можно найти другие примеры использования структуры дерева блоков и точек сочленения, причем не только в теории связности.

При к > 1 структура разбиения к-связного графа выглядит несколько сложнее. Для того, чтобы это пояснить, введем понятие зависимых разделяющих множеств. Два /¿-вершинных разделяющих множества называются зависимыми, если при удалении одного из них вершины другого оказываются в разных компонентах связности. В противном случае разделяющие множества называются независимыми. Очевидно, что при к — 1 любые два /¿-вершинных разделяющих множеств независимы. Именно зависимые разделяющие множества создают трудности в исследовании структуры разбиения /¿-связного графа при к > 1.

Исследованием случая к = 2 занимался Татт. В книге [17] 1966 года он описал структуру взаимного расположения двухвершинных разделяющих множеств в двусвязном графе и показал, что она имеет много общего со структурой точек сочленения. В частности, была предложена конструкция дерева блоков для двусвязного графа.

Попытки построения аналогичных конструкций для графов большей связности делались в работах [8,23,25]. Наличие зависимых разделяющих множеств приводит к тому, что получающиеся конструкции дерева блоков для /¿-связного графа оказываются неоднозначными — они существенно

зависят от того, в каком порядке при их построении выбираются разделяющие множества. Кроме того, подобные конструкции учитывают не все /¿-вершинные разделяющие множества графа: разбивая граф при помощи одного из этих множеств мы автоматически теряем информацию обо всех зависимых с ним разделяющих множествах. В работах [23,25] эти трудности были частично преодолены для графов, удовлетворяющих некоторым дополнительным условиям. Однако в общем случае вопрос об описании структуры разбиения /¿-связного графа всеми его /¿-вершинными разделяющими множествами при к > 3 остается открытым.

В работе [26] был разработан новый метод изучения структуры взаимного расположения /¿-вершинных разделяющих множеств /¿-связного графа — теорема о разбиении. С ее помощью был получен ряд результатов для случая произвольного к. В качестве иллюстрации работы этого метода в конце работы [26] приведено достаточно наглядное и простое описание структуры двухвершинных разделяющих множеств в двусвяз-ном графе. Это описание в целом аналогично конструкции Татта [17], но хорошо иллюстрирует эффективность нового метода.

В 2011 году Карпов и Пастор [24] описали структуру трехсвязно-го графа. В их работе трехвершинные множества разбиваются на вполне определенные группы, которые называются комплексами. Благодаря этому новому определению удается построить гипердерево, вершинами которого являются комплексы — некоторые хорошо описанные наборы разделяющих множеств. Комплексы делятся на несколько типов в зависимости от множества вершин, покрытого разделяющими множествами этого комплекса. Определение ромашки будет дано ниже, пока же хочется отметить, что лишь комплекс ромашки может покрывать сколь угодно много вершин — каждый из остальных комплексов покрывает не более 12 вершин. Это наблюдение, а также теорема 3 из [26] показывают, что комплекс ромашки является наиболее важным и сложным для изучения в случае

произвольного к.

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

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

Обозначения

Для того, чтобы выписать условия доказанных в диссертации теорем, необходимо ввести некоторые определения и обозначения. Множество всех /¿-вершинных разделяющих множеств в графе (2 будем обозначать через тк(С).

Определение 1. 1) Пусть Я, X С У (С). Будем говорить, что множество Я разделяет множество X, если не все вершины из X \ Я лежат в одной компоненте связности графа С — Я.

2) Пусть и, Я С V(С). Будем говорить, что множество Я отделяет множество II от множества IV, если и <£. Я, IV <£ Я и никакие две вершины и£и\Яигп£]¥\Яне лежат в одной компоненте связности графа С — Я.

В случае, когда и = {и}, мы будем говорить, что Я отделяет вершину и от множества IV. Если же II = {и} и \¥ = {ии}, то мы будем говорить, что Я отделяет вершину и от вершины ги. Определение 2. Пусть © С

1) Часть разбиения графа (2 набором © (или часть ©-разбиения) — это подграф графа С, индуцированный на максимальном по включению множестве А С таком, что никакое множество 5 € © не разделя-

ет А. Будем обозначать через Part(ö) множество всех таких частей. Если набор © состоит из одного множества 5, то будем обозначать множество всех частей {¿>}-разбиения через Part(5).

2) Вершины части А £ Part(6), не входящие ни в одно из множеств набора будем называть внутренними, а множество всех таких вершин — внутренностью части А, которую будем обозначать через Int(^). Вершины части А, входящие в какие-либо множества из мы будем называть граничными, а множество всех этих вершин — границей части А и обозначать через Bound(A).

3) Назовем часть А пустой, если Int (Л) = 0 и непустой в противном случае. Назовем часть А малой, если 11^(^4)1 < к и нормальной, если

\V(A)\ > к.

Замечание 1. В [25] доказано, что множество вершин границы части А совпадает с множеством вершин этой части, имеющих смежные вершины за ее пределами. Это утверждение делает понятие границы части независимым от набора разделяющих множеств.

Теперь введем самое важное понятия в диссертации — понятие ромашки в fc-связном графе.

Пусть т > 4 и множества Р, С V(G) удовлетворяют

следующим условиям для всех г € {1,..., т}:

0<\Р\<к, QiHP = 0, \Qi\ = к~}РУ

£

Рассмотрим набор F = (Р; Qi,..., Qm)• Множества Qi,..., Qm считаем циклически упорядоченными, то есть их циклическая перестановка не меняет F. Введем обозначение Qy = Qi U Qj U Р.

Если не заботиться о строгости определения, удобно рассматривать ромашку, расположив лепестки Qь ..., Qm по окружности в соответствии с их циклическим порядком, а в центр поместив Р. При этом удаление

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

Строгое определение ромашки гораздо более абстрактно и требует определения понятия близких лепестков.

Определение 3. 1) Индексы у нас являются вычетами по модулю т, и удобно представлять их себе как числа от 1 до га, расставленные по кругу — по часовой стрелке для определенности. Для г ф j,j — 1 иод индексами от i до j стоит понимать индексы, лежащие на той из дуг между г и j, на которой находится индекс г+1. Для г = j — 1 под индексами от г до j будем понимать г и j.

2) Назовем лепестки Qi и Qj близкими, если включение Qk С Qi,j выполняется либо для всех к от г до j, либо для всех к от j до г. Определение 4. 1) Пусть существует такие набор (5 С состоящий

из множеств вида Qij, где inj — не соседние, что разбиение Part((5) состоит из т частей С2,з,---> ^тд? причем Bound(Gi,i+i) = Qi,i+i-Кроме того, пусть из того, что Qi и Qj пересекаются, следует, что они близки. Тогда назовем набор F ромашкой.

2) Множество Р назовем центром, а множества Qi,...,Qm — лепестками этой ромашки. Разбиением графа G ромашкой F назовем Part(F) = {^1,2,..., Gm,\}, а подграфы С?г,г+1 будем называть частями этого разбиения. Введем обозначение Gij = G(U:!c'lJlV(GXfX+1)).

На самом деле, в диссертации рассматривается несколько более общий объект — обобщенная ромашка. Отличие в том, что в обобщенной ромашке подграфы • • •, Gm,i могут состоять из нескольких частей разбиения Part(G). Полное определение приведено в главе 1. Гораздо более важно, что в определении ромашки лепесткам разрешено содержаться в объединении других лепестков. Это существенное отличие от определения в [26], поэтому основные утверждения для ромашки из [26] приходится

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

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

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

В теореме 1 доказывается, что если обобщенную ромашку Р = (Р; (¿1,..., Ят) изобразить как окружность с центром Р и лепестками <5ъ ..., расположенными на ней в таком циклическом порядке, то объединение центра и двух неблизких лепестков и Qj является разделяющим множеством и отделяет друг от друга две дуги, на которые нашу окружность делит хорда QiQj.

Теорема 1. Пусть Р = (Р;ф — обобщенная ромашка. Тогда

£Н(Р) С ((■?), причем мноэ/сество € £Н(Р) отделяет Су от

Формулировка теоремы 1 данной диссертации фактически дословно повторяет теорему б из [26], отличие заключается в том, что в диссертации используется более общее определение ромашки. Во-первых, лепесткам разрешено лежать в объединении других лепестков, а во-вторых, подграфы могут состоять из нескольких частей разбиения графа набором разделяющих множеств.

Благодаря теореме 2 становится корректно определено понятие разбиения графа ромашкой Р — в этой теореме доказывается, что это разбиение определяется центром и набором лепестков (без наперед заданного циклического порядка).

Теорема 2. Пусть наборы 6, Т С порождают обобщенные ро-

машки и Ег соответственно с одинаковым центром и одинаковыми множествами лепестков. Тогда = Раг^Т) и ^ = Рг (то есть,

циклические порядки лепестков в этих ромашках одинаковы).

Теорема 2 данной диссертации является обобщением теоремы 7 из [26], отличие вновь заключается в большей общности определения ромашки.

Далее рассматривается ряд более продвинутых свойств частей разбиения графа обобщенной ромашкой. Для этого вводится понятие внешних ребер.

Определение 6. Пусть Р = (-Р;ф ~~ обобщенная ромашка.

Рассмотрим два ее произвольных лепестка С^г и Qj, где г ^ Ребро части назовем внешним, если ни для какого х от г до ^ — 1 оно не является ребром части Стх,х+1- Множество внешних ребер части Оу обозначим через

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

Лемма 1.10 показывает, что каждый лепесток с номером от г до з действительно разделяет наш "отрезок" от (¿1 до Qj (подграф Сц — Е0иь{ьз)), причем его "концы" (лепестки и О/) лежат в разных частях.

После этого в леммах 1.12 и 1.13 исследуется возможность добавления лепестков в ромашку — устанавливаются достаточные для этого условия. Эти утверждения оказываются крайне полезными в доказатель-

стве Теоремы 5.

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

Основное отличие четырехсвязного графа от к-связного для произвольного к заключается в том, что есть всего два типа ромашек — с центром, состоящим из двух вершин (2-ромашки), и с пустым центром (0-ромашки). Работу с ромашками усложняют ребра между вершинами разных лепестков. В случае четырехсвязного графа в лепестках либо по одной, либо по две вершины, и для двух выбранных лепестков можно рассмотреть все возможные способы соединения их вершин ребрами. Объем работы существенно сокращается благодаря утверждениям, доказанным для произвольного к-связного графа.

Обобщенные 2-ромашки в четырехсвязном графе, во-первых, являются, ромашками, а во-вторых, очень похожи на ромашки в трехсвяз-ном графе, отличие только в дополнительной вершине в центре. Для 2-ромашек доказывается теорема 3, аналогичная лемме 10 для трехсвяз-ных графов из [24].

Теорема 3. Любое 4-разделяющее множество, содержащееся в множестве вершин максимальной 2-ромашки, содержит ее центр, то есть является либо ее внутренним множеством, либо границей.

Исследовать обобщенные 0-ромашки в четырехсвязном графе оказывается гораздо сложнее. Лепестки 0-ромашки могут пересекаться, содержаться в объединении других лепестков, а части разбиения могут быть несвязны. Для формулировки аналогичной теоремы про разделяющие множества, содержащиеся в множестве вершин максимальной 0-ромашки, необходимо определить понятие квазивнутренних множеств. Определение Т. Назовем лепесток 0-ромашки переключателем, если он состоит из двух несмежных вершин и лежит в объединении двух сосед-

них с ним лепестков. Если лепесток 0-ромашки Р = (<31, ...,<5т) является переключателем, то переключением назовем замену на

= и Яг+г) \ ф. Определение 8. Две 0-ромашки будем называть похоэ/сими, если одна из них получается из другой после нескольких переключений (см. рис. 2.1). Внутренние множества ромашки, похожей на ромашку Р, будем называть квазивнутреиними множествами Р.

В лемме 2.4 доказывается, что отношение похожести является отношением эквивалентности.

Теорема 4. Любое 4-разделяющее множество, содержащееся в мноэюе-стве вершин максимальной обобщенной 0-ромашки, является либо ее внутренним множеством, либо квазивнутренним, либо ее границей.

Далее исследуется взаимное расположение двух максимальных обобщенных 0-ромашек Р и Р', имеющих общее внутреннее разделяющее множество. В общем и целом, в Теореме 5 доказывается, что за исключением некоторых вырожденных случаев, ромашки лежат "сбоку" друг от друга, то есть ни одно внутреннее разделяющее множество ромашки Р не разделяет множество У(Р') \ У(Р), и ни одно внутреннее разделяющее множество ромашки Р' не разделяет множество У(Р) \ У(Р")- Для точ~ ной формулировки указанной теоремы необходимо ввести понятие малых ромашек и ромашек и \У2-типа (см. рис. 2.3).

Определение 9. Назовем обобщенную 0-ромашку Р малой, если у нее есть внутреннее множество, пересекающееся со всеми лепестками Р.

В лемме 2.5 доказыавется, что во всякой малой ромашке ровно шесть лепестков, — отсюда название.

Определение 10. Допустим, вершины обобщенной 0-ромашки можно таким образом обозначить через (2, Ь, , с?2, , ¿4, ¿5, что лепестками ромашки являются множества {а, Ь}, {<¿1,(^2}, {<^3^4}, {^4,^5}. Будем

говорить тогда, что это — ромашка \¥1 -типа.

Если в множестве вершин ромашки есть еще одна вершина, назовем ее вершиной с, причем {а, с} является лепестком, то будем говорить, что это — ромашка \V2-muna.

Теорема 5. Пусть две максимальные обобщенные 0-ромашки ^ и имеют общее внутреннее разделяющее множество Т. Известно, что некоторое внутреннее разделяющее множество ромашки Р разделяет множество У(-Р') \ V(Р). Тогда выполнено одно из следующих утверждений:

1° Граф (2 изоморфен одному из трех исключений (см. рис. 2А).

2° Множество Т разбивается в обеих ромашках па лепестки одинаково, обе ромашки являются малыми, причем у них ровно два общих лепестка. Кроме того, индуцированный подграф графа С на двух общих лепестках ромашек Р и Р' — это цикл длины 4.

3° Множество Т разбивается на лепестки по-разному, обе ромашки являются малыми, в каждой из них есть ровно по две вершины, не лежащие в другой.

4° Множество Т разбивается на лепестки по-разному, обе ромашки — \Vl-muna, в каждой из них есть ровно по две вершины, не лежащие в другой.

5° Множество Т разбивается па лепестки по-разному, обе ромашки — \V2-muna, в каждой из них есть ровно по две вершины, не лежащие в другой.

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

Диссертация состоит из введения и двух глав. Формулировки всех теорем помещены во введение. Нумерация определений сквозная, а нумерация

разделов, лемм, формул и замечаний ведется отдельно для каждой главы.

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

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

Результаты диссертации изложены в работах [21,22].

Глава 1

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

Введем основные понятия, которые будем использовать в течение всей работы.

Для любого множества М С У(С)иЕ(С) мы будем обозначать через (7 — М граф, полученный из (? в результате удаления вершин и ребер множества М и всех ребер, инцидентных вершинам множества М. Определение 11. 1) Будем называть множества 5, Т € (С?) независимыми, если Б не разделяет Т и Т не разделяет 5. В противном случае, назовем эти множества зависимыми.

2) Каждому набору © С 9*^(0) поставим в соответствие граф зависимости Бер(б), вершины которого — множества набора <5, а две вершины смежны тогда и только тогда, когда соответствующие множества зависимы.

Таким образом, набор в разбивается на компоненты зависимости — поднаборы, соответствующие компонентам связности графа Бер(6).

Нетрудно доказать, что если Т не разделяет 5, то 5 не разделяет Т,

то есть, эти множества независимы (см. [8,23]).

В определении 2 мы дали определение части разбиения графа набором разделяющих множеств 6. Заметим, что две различные части Ai, Л.2 G Part(e) либо не имеют общих вершин, либо V(A\) П V(A2) содержится в одном из множеств набора ©. В [26, теорема 2] доказано, что граница Bound(^l) состоит из всех вершин части А, имеющих смежные вершины вне А и отделяет Int (Л) от V(G) \ У(Л), если оба этих множества не пусты.

Важным частным случаем разбиения /^-связного графа набором ^-разделяющих множеств является разбиение этого графа одним к-разделяющим множеством S. Понятно, что для любой части F G Part (S) ее внутренность Int (F) есть множество вершин одной из компонент связности графа G — S. Поскольку никакое подмножество множества S не является разделяющим множеством графа G, каждая вершина множества S должна быть смежна хотя бы с одной вершиной из Int(F), то есть подграф F связен.

Отметим, что каждая вершина х графа G смежна хотя бы с одной другой вершиной у. Тогда никакое множество не может разделить х и т/, следовательно, для произвольного набора 6 С £Нu{G) любая часть A G Part(ö) содержит хотя бы две вершины.

Одним из важнейших объектов в исследовании структуры ^-связных графов является ромашка. Напомним общее определение для произвольного к.

Пусть m > 4, и множества Р, Qi,...,Qm С V(G) удовлетворяют следующим условиям для всех г G {1,..., m}:

к — \Р\

0<\Р\<к, QiHP = 0, \Qi\ = 1 '. Рассмотрим набор F = (F; Qi,..., Qm). Множества Qi,..., Qm считаем

циклически упорядоченными, то есть их циклическая перестановка не меняет Р. Введем обозначение = (¿^и и Р. Определение 12. Назовем и Qj близкими, если включение С^ь С выполняется либо для всех к от г до либо для всех к от у до г.

Определение 13. 1) Пусть существует такой набор 6 С 9^(6?), состоящий из множеств вида Qq, где г и j — не соседние, что разбиение Part(€>) состоит из т частей G2,3,..., Gm, 1, причем Bound{G^+i) = Qij+i. Кроме того, пусть из того, что Qi и Qj пересекаются, следует, что они близки. Тогда назовем набор F ромашкой.

2) Множество Р назовем центром, а множества Q\,..., Qm — лепестками этой ромашки. Разбиением графа G ромашкой F назовем Part(F) = {Gi£, • ■ ■ ,Gmti}, а подграфы Gjj+i будем называть частями этого разбиения. Если никакие два лепестка ромашки F не пересекаются, то назовем эту ромашку правильной. Будем говорить, что набор <5 порождает ромашку F.

Замечание 1.1. Дополнительное условие про близость пересекающихся лепестков необходимо — без него не будет верна теорема 1. В работах [26] и [24] авторы имеют дело с правильными ромашками, для которых это

А

V

Рис. 1.1: Ромашка.

условие выполнено тривиальным образом — пересекающихся лепестков там просто нет.

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

Определение 14. 1) Пусть S G 9\k{G), причем Part(5) = {А\,..., Ат}. Рассмотрим произвольное j от 2 до т и некоторое дизъюнктное разбиение I = {Ii,..., Ij} множества натуральных чисел от 1 до т на j подмножеств. Рассмотрим такие индуцированные подграфы Bi,... ,Bj графа G, что V(Bt) = иг€74У(Лг). Будем говорить, что S делит граф G на обобщенные части Bi,...,Bj, согласованные с разбиением /. Обозначать набор обобщенных частей, согласованных с I, будем так — Part/(5).

2) Пусть (5 С %Kk{G) — это набор разделяющих множеств Si,..., St, которые делят граф на mi,..., mt частей соответственно. Рассмотрим набор J = {J1,..., I1} такой, что для всех j от 1 до t множество Р является разбиением чисел от 1 до vrij на несколько (более одной) групп. Обобщенной частью разбиения графа набором разделяющих множеств согласованной с набором разбиений 3, назовем максимальный по включению индуцированный подграф, целиком лежащий в одной из обобщенных частей разбиения графа каждым из множеств набора. Множество всех обобщенных частей разбиения графа набором (5, согласованных с набором разбиений 3, будем обозначать через Part;j(G) и называть обобщенным разбиением графа набором ©, согласованным с Of.

Список литературы диссертационного исследования кандидат наук Глазман, Александр Львович, 2014 год

Литература

[1] G. Chartrand, A. Kaugars, D.R. Lick. Critically n-connected graphs. // Proc. of the Amer. Math. Soc., 1972, vol. 32, p. 63-68.

[2] R. halin. A theorem on n-connected graphs. // Journal of Combinatorial Theory, 1969, vol. 7, p. 150-154.

[3] R. halin. On the structure of n-connected graphs. // In: Recent Progress in Combinatorics (ed: W. T. Tutte), Academic Press, London - New York, 1969, p. 91-102.

[4] r. halin. Zur Theorie dern-fach zusammenhängenden Graphen. // Abh. Math. Sem. Univ. Hamburg, 1969, vol. 7, p. 133-164.

[5] R. halin. Studies on minimally n-connected graphs. // In: Combinatorial Mathematics and its Applications (ed: D. J. A. Welsh), Academic Press, London - New York, 1971, p. 129-136.

[6] y. o. hamidoune. On critically h-connected simple graphs. // Discrete Mathematics, 1980, vol. 32, p. 257-262.

[7] S. hedetniemi. Characterizations and constructions of minimally 2-connected graphs and minimally strong digraphs. // In: "Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing, 1971," p. 257-282.

[8] W. Hohberg. The decomposition of graphs into k-connected components. Discr. Math., 109 (1992), p. 133-145.

[9] W. MADER. Eine Eigenschaft der Atome endlicher Graphen. // Arch. Math., 1971, vol. 22, p. 333-336.

10] W. MADER. Ecken vom Grad n in minimalen n-fach zusammenhängenden Graphen. // Arch. Math., 1972, vol. 23, p. 219-224.

11] W. MADER. Endlichkeitssätze für k-kritische Graphen. // Math. Ann., 1977, vol. 229, p. 143-153.

12] W. Mader. On vertices of degree n in minimally n-connected graphs and digraphs // Combinatorics, Paul Erdös is eighty (Volume 2) Keszthely (Hungray), 1993. Budapest: Janos Bolyai Mathematical Society, 1996, p. 423-449.

13] K. MENGER. Zur allgemeinen Kurventheory. // Fund. Math., 1927, p. 10, p. 96-115.

14] P. J. SLATER. A classification of 4-connected graphs. // Journal of Combinatorial Theory, 1974, vol. 17, p. 257-282.

15] P.J. SLATER. Soldering and Point Splitting. / / Journal of Combinatorial Theory, Series B, 1974, vol. 24, p. 338-343.

16] W.T.Tutte. A theory of 3-connected graphs. // Indag. Math. 1961, vol. 23, p. 441-455.

17] W.T.Tutte. Connectivity in graphs. Toronto, Univ. Toronto Press, 1966.

18] H.J.veldman. Non-к-critical vertices in graphs. // Diskrete Mathematics, 1983, vol. 44, p. 105-110.

19] H.whitney. Congruent Graphs and the Connectivity of Graphs. // American Journal of Mathematics, 1932, vol. 54, no. 1, p. 150-168.

20] К. Берж. Теория графов и ее применения. // Москва, Иностранная литература, 1962. (Перевод с французского. С. Berge, Theorie des graphes et ses applications. Dunod, Paris, 1958.)

21] А.л.глазман. Обобщенные ромашки в k-связном графе. Записки научных семинаров ПОМИ, 391 (2011), стр. 45-78.

22] А.л.глазман. Обобщенные ромашки в k-связном графе. Часть 2. Записки научных семинаров ПОМИ, 417 (2013), стр. 11-85.

}

[23] Д. В. карпов, А. В. пастор. О структуре k-связного графа. Записки научных семинаров поми, 266 (2000), стр. 76-106.

[24] Д. В. Карпов, А. В. Пастор. Структура разбиения трёхсвязного графа. Записки научных семинаров ПОМИ, том 391 (2011 г.), стр. 90-148.

[25] Д. В. карпов. Блоки в k-связных графах. Записки научных семинаров ПОМИ, 293 (2002), стр. 59-93.

[26] Д. в. карпов. Разделяющие множества в к-связном графе. Записки научных семинаров ПОМИ, 340 (2006), стр. 33-60.

[27] У. Татт. Теория графов. // Москва, Мир, 1988. (Перевод с английского. W. Т. Tutte, Graph theory. Enciclopedia of Mathematics and its Applications, vol. 21, 1984.)

[28] Ф.харари. Теория графов. Москва, "Мир", 1973. (Перевод с английского. F.Harary, Graph theory, 1969.)