«ОБОБЩЁННЫЕ РОМАШКИ В k-СВЯЗНОМ ГРАФЕ ( ...»

Федеральное государственное бюджетное учреждение наук

и

Санкт-Петербургское отделение Математического института

имени В. А. Стеклова Российской академии наук

На правах рукописи

Глазман Александр Львович

ОБОБЩЁННЫЕ РОМАШКИ В k-СВЯЗНОМ ГРАФЕ

(01.01.09 дискретная математика и математическая кибернетика)

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

Научный руководитель кандидат физико-математических наук Д. В. Карпов Санкт-Петербург 2014 Оглавление Введение Связность................................ Структура разбиения k-связного графа............... Результаты диссертации........................ Ромашки в k-связном графе................... Ромашки в четырехсвязном графе............... Структура диссертации........................ 1 Обобщенные ромашки в k-связном графе 2 Ромашки в четырехсвязном графе 2.1 2-Ромашки............................ 2.2 0-Ромашки............................ Введение Теория графов является одним из важнейших и интереснейших разделов математики. В различных областях математики алгебре, топологии, информатике и других возникает потребность описания свойств тех или иных объектов на языке теории графов и использования результатов теории графов, что подчеркивает значимость изучения графов и их свойств.

В диссертации рассматриваются неориентированные графы без петель и кратных ребер. Множество вершин графа G будем обозначать через V (G), а множество ребер через E(G). Степень вершины v в графе G мы будем обозначать через dG (v).

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

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

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

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

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

Во второй половине XX века активно проводились исследования связности графов. Одним из направлений этих исследований были вопросы о сохранении графом свойства k-связности при удалении его вершин или ребер. Эти вопросы привели к введению понятий критических и минимальных k-связных графов. k-связный граф называется критическим, если при удалении любой его вершины он перестает быть k-связным. Аналогично, k-связный граф называется минимальным, если при удалении любого его ребра он перестает быть k-связным. Наиболее сильные результаты по минимальным k-связным графам получили R. Halin [2–5] и W. Mader [9–12]. В работах [1,6,9,18,23] изучались критические k-связные графы и вопросы о том, при каких условиях в k-связном графе существует вершина, удаление которой не нарушает k-связность графа, и какие вершины данного графа удовлетворяют этому свойству.

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

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

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

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

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

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

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

Именно зависимые разделяющие множества создают трудности в исследовании структуры разбиения k-связного графа при k > 1.

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

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

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

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

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

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

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

2) Пусть U, W, R V(G). Будем говорить, что множество R отделяет множество U от множества W, если U R, W R и никакие две вершины u U \ R и w W \ R не лежат в одной компоненте связности графа G R.

В случае, когда U = {u}, мы будем говорить, что R отделяет вершину u от множества W. Если же U = {u} и W = {w}, то мы будем говорить, что R отделяет вершину u от вершины w.

Определение 2. Пусть S Rk (G).

1) Часть разбиения графа G набором S (или часть S-разбиения) это подграф графа G, индуцированный на максимальном по включению множестве A V(G) таком, что никакое множество S S не разделяет A. Будем обозначать через Part(S) множество всех таких частей. Если набор S состоит из одного множества S, то будем обозначать множество всех частей {S}-разбиения через Part(S).

2) Вершины части A Part(S), не входящие ни в одно из множеств набора S, будем называть внутренними, а множество всех таких вервнутренностью части A, которую будем обозначать через Int(A).

шин Вершины части A, входящие в какие-либо множества из S, мы будем награницей части A и зывать граничными, а множество всех этих вершин обозначать через Bound(A).

3) Назовем часть A пустой, если Int(A) = и непустой в противном случае. Назовем часть A малой, если |V (A)| < k и нормальной, если |V (A)| k.

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

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

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

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

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

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

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

2) Назовем лепестки Qi и Qj близкими, если включение Qk Qi,j выполняется либо для всех k от i до j, либо для всех k от j до i.

Определение 4. 1) Пусть существует такие набор S Rk (G), состоящий из множеств вида Qi,j, где i и j не соседние, что разбиение Part(S) состоит из m частей G1,2, G2,3,..., Gm,1, причем Bound(Gi,i+1 ) = Qi,i+1.

Кроме того, пусть из того, что Qi и Qj пересекаются, следует, что они близки. Тогда назовем набор F ромашкой.

2) Множество P назовем центром, а множества Q1,..., Qm лепестками этой ромашки. Разбиением графа G ромашкой F назовем Part(F ) = {G1,2 ,..., Gm,1 }, а подграфы Gi,i+1 будем называть частями этого разбиения. Введем обозначение Gi,j = G(j1 V(Gx,x+1 )).

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

Определение 5. Внутренними множествами обобщенной ромашки назовем множества Qi,j для всех пар неблизких лепестков Qi и Qj. Обозначим через R(F ) набор, состоящий из внутренних множеств обобщенной ромашки F. Границами ромашки назовем множества Qi,i+1 для всех i.

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

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

В теореме 1 доказывается, что если обобщенную ромашку F = (P ; Q1,..., Qm ) изобразить как окружность с центром P и лепестками Q1,..., Qm расположенными на ней в таком циклическом порядке, то объединение центра и двух неблизких лепестков Qi и Qj является разделяющим множеством и отделяет друг от друга две дуги, на которые нашу окружность делит хорда Qi Qj.

Теорема 1. Пусть F = (P ; Q1,..., Qm ) обобщенная ромашка. Тогда R(F ) Rk (G), причем множество Qi,j R(F ) отделяет Gi,j от Gj,i.

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

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

Теорема 2. Пусть наборы S, T Rk (G) порождают обобщенные ромашки FS и FT соответственно с одинаковым центром и одинаковыми множествами лепестков. Тогда Part(S) = Part(T) и FS = FT (то есть, циклические порядки лепестков в этих ромашках одинаковы).

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

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

Определение 6. Пусть F = (P ; Q1,..., Qm ) обобщенная ромашка.

Рассмотрим два ее произвольных лепестка Qi и Qj, где i = j. Ребро части Gi,j назовем внешним, если ни для какого x от i до j 1 оно не является ребром части Gx,x+1. Множество внешних ребер части Gi,j обозначим через EF (i, j).

Понятие внешних ребер играет решающую роль в постановке новых утверждений, касающихся обобщенных ромашек в k-связном графе. При изучении месторасположения лепестков ромашки F, подграф Gi,j после удаления внешних ребер можно, в некотором смысле, считать отрезком, в отличие от графа G, который, как уже говорилось, удобнее отождествлять с окружностью.

1.10 показывает, что каждый лепесток с номером от i до j действительно разделяет наш “отрезок” от Qi до Qj (подграф Gi,j Eout (i, j)), причем его “концы” (лепестки Qi и Qj ) лежат в разных частях.

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

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

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

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

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

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

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

Определение 7. Назовем лепесток 0-ромашки переключателем, если он состоит из двух несмежных вершин и лежит в объединении двух соседних с ним лепестков. Если лепесток Qi 0-ромашки F = (Q1,..., Qm ) является переключателем, то переключением Qi назовем замену Qi на Qi = (Qi1 Qi+1 ) \ Qi.

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

Внутренние множества ромашки, похожей на ромашку F, будем называть квазивнутренними множествами F.

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

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

Далее исследуется взаимное расположение двух максимальных обобщенных 0-ромашек F и F, имеющих общее внутреннее разделяющее множество. В общем и целом, в Теореме 5 доказывается, что за исключением некоторых вырожденных случаев, ромашки лежат “сбоку” друг от друга, то есть ни одно внутреннее разделяющее множество ромашки F не разделяет множество V(F ) \ V(F ), и ни одно внутреннее разделяющее множество ромашки F не разделяет множество V(F ) \ V(F ). Для точной формулировки указанной теоремы необходимо ввести понятие малых ромашек и ромашек W1 и W2-типа (см. рис. 2.3).

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

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

Определение 10. Допустим, вершины обобщенной 0-ромашки можно таким образом обозначить через a, b, d1, d2, d3, d4, d5, что лепестками ромашки являются множества {a, b}, {d1, d2 }, {d2, d3 }, {d3, d4 }, {d4, d5 }. Будем говорить тогда, что это Если в множестве вершин ромашки есть еще одна вершина, назовем ее вершиной c, причем {a, c} является лепестком, то будем говорить, что ромашка W 2-типа.

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

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

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

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

4 Множество T разбивается на лепестки по-разному, обе ромашW 1-типа, в каждой из них есть ровно по две вершины, не лежащие в другой.

5 Множество T разбивается на лепестки по-разному, обе ромашW 2-типа, в каждой из них есть ровно по две вершины, не лежащие в другой.

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

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

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

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

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

Для любого множества M V(G)E(G) мы будем обозначать через G M граф, полученный из G в результате удаления вершин и ребер множества M и всех ребер, инцидентных вершинам множества M.

Определение 11. 1) Будем называть множества S, T Rk (G) независимыми, если S не разделяет T и T не разделяет S. В противном случае, назовем эти множества зависимыми.

2) Каждому набору S Rk (G) поставим в соответствие граф зависимости Dep(S), вершины которого множества набора S, а две вершины смежны тогда и только тогда, когда соответствующие множества зависимы.

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

Нетрудно доказать, что если T не разделяет S, то S не разделяет T, то есть, эти множества независимы (см. [8, 23]).

В определении 2 мы дали определение части разбиения графа набором разделяющих множеств S. Заметим, что две различные части A1, A2 Part(S) либо не имеют общих вершин, либо V (A1 ) V (A2 ) содержится в одном из множеств набора S. В [26, теорема 2] доказано, что граница Bound(A) состоит из всех вершин части A, имеющих смежные вершины вне A и отделяет Int(A) от V(G) \ V(A), если оба этих множества не пусты.

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

Отметим, что каждая вершина x графа G смежна хотя бы с одной другой вершиной y. Тогда никакое множество не может разделить x и y, следовательно, для произвольного набора S Rk (G) любая часть A Part(S) содержит хотя бы две вершины.

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

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

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

Определение 12. Назовем Qi и Qj близкими, если включение Qk Qi,j выполняется либо для всех k от i до j, либо для всех k от j до i.

Определение 13. 1) Пусть существует такой набор S Rk (G), состоящий из множеств вида Qi,j, где i и j не соседние, что разбиение Part(S) состоит из m частей G1,2, G2,3,..., Gm,1, причем Bound(Gi,i+1 ) = Qi,i+1.

Кроме того, пусть из того, что Qi и Qj пересекаются, следует, что они близки. Тогда назовем набор F ромашкой.

2) Множество P назовем центром, а множества Q1,..., Qm лепестками этой ромашки. Разбиением графа G ромашкой F назовем Part(F ) = {G1,2,..., Gm,1 }, а подграфы Gi,i+1 будем называть частями этого разбиения. Если никакие два лепестка ромашки F не пересекаются, то назовем эту ромашку правильной. Будем говорить, что набор S порождает ромашку F.

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

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

Определение 14. 1) Пусть S Rk (G), причем Part(S) = {A1,..., Am }.

Рассмотрим произвольное j от 2 до m и некоторое дизъюнктное разбиение I = {I1,..., Ij } множества натуральных чисел от 1 до m на j подмножеств. Рассмотрим такие индуцированные подграфы B1,...,Bj графа G, что V(Bt ) = iIt V(Ai ). Будем говорить, что S делит граф G на обобщенные части B1,...,Bj, согласованные с разбиением I. Обозначать набор обобщенных частей, согласованных с I, будем так PartI (S).

которые делят граф на m1,..., mt частей соответственно. Рассмотрим набор I = {I 1,..., I t } такой, что для всех j от 1 до t множество I j является разбиением чисел от 1 до mj на несколько (более одной) групп. Обобщенной частью разбиения графа набором разделяющих множеств S, согласованной с набором разбиений I, назовем максимальный по включению индуцированный подграф, целиком лежащий в одной из обобщенных частей разбиения графа каждым из множеств набора. Множество всех обобщенных частей разбиения графа набором S, согласованных с набором разбиений I, будем обозначать через PartI (S) и называть обобщенным разбиением графа набором S, согласованным с I.

3) Внутренность и граница обобщенной части определяется так же, как внутренность и граница обычной.

Лемма 1.1. Пусть S, T Rk (G), а набор I задает разбиение частей из Part(S) на обобщенные части. Тогда множества S и T зависимы тогда и только тогда, когда нет обобщенной части из PartI (S), во множестве вершин которой содержатся все вершины из T.

Доказательство. () Пусть множества S и T зависимы. Тогда во внутренности каждой из частей разбиения графа G множеством S содержится как минимум одна вершина множества T ( [23, лемма 10]). Ясно, что тогда и во внутренности каждой из обобщенных частей разбиения графа множеством S, согласованного с I, содержится как минимум одна вершина множества T. Поэтому не найдется обобщенной части, среди вершин которой есть все вершины множества T.

() Пусть нет обобщенной части из PartI (S), во множестве вершин которой содержатся все вершины из T. Тогда есть две обобщенные части из PartI (S), во внутренности каждой из которых есть вершины множества T. Значит, найдутся и две обыкновенные части разбиения графа G множеством S с таким же свойством. То есть S и T зависимы.

Замечание 1.2. Заметим, что все утверждения из [26] верны и для обобщенных частей, и глобальная причина этого такова в их доказательстве не использовалась связность подграфов, индуцированных на внутренности частей, а до тех пор, пока мы ей не пользуемся, понятия обобщенной части и обычной части неразличимы.

Определение 15. 1) Пусть существует такой набор S Rk (G), состоящий из множеств вида Qi,j, где i и j не соседние, и набор разбиений I, что обобщенное разбиение PartI (S) состоит из m частей G1,2, G2,3,..., Gm,1, причем Bound(Gi,i+1 ) = Qi,i+1. Кроме того, пусть из того, что лепестки Qi и Qj пересекаются, следует, что они близки. Тогда назовем набор F обобщенной ромашкой.

2) Центр и лепестки обобщенной ромашки определим так же, как соответствующие понятия для обычной ромашки. Разбиением графа G обобщенной ромашкой F назовем PartI (F ) = {G1,2,..., Gm,1 }, а подграфы Gi,i+1 будем называть частями этого разбиения.

Замечание 1.3. Обычная ромашка, очевидно, является частным случаем обобщенной.

В дальнейшем считаем, что в графе больше, чем 2k |P | вершин.

Замечание 1.4. 1) В случае четырехсвязного графа логично работать именно с обобщенными ромашками, но из-за этого придется передоказать некоторые утверждения, доказанные в [26] и [24]. К тому же, мы нигде не предполагаем правильности ромашки, а требуем, чтобы выполнялось гораздо более слабое условие чтобы пересекались только близкие лепестки. Пример обобщенной ромашки, не являющейся обычной приведен на рис. 1.2.

2) Для того, чтобы определение Part(F ) было корректно, необходимо доказать, что независимо от S и I части Gi,i+1 будут одни и те же. Это будет доказано в теореме 2. Но сразу же хочется отметить, что в некоторых случаях обобщенная ромашка, порожденная набором разделяющих множеств с нетривиальным набором разбиений, может быть порождена как обычная при должном выборе набора разделяющих множеств. Однако такой набор найдется не всегда.

Рис. 1.2: Обобщенная ромашка, которая не является обычной.

Введенные выше обозначения будем считать стандартными для ромашки, лепестки располагаем в циклическом порядке, а их индексы будем рассматривать как вычеты по модулю количества лепестков. Введем обозначение Gi,j = G(j1 V(Gx,x+1 )).

Удобно рассматривать ромашку, расположив лепестки Q1,..., Qm по окружности в соответствии с их циклическим порядком, а в центр поместив P (см. рис. 1.1). Между лепестками Qi и Qi+1 поместим часть Gi,i+1.

В данном случае фраза “между лепестками” имеет вполне конкретный естественно, часть Gi,i+1 располагаем с той стороны, где нет смысл других лепестков. В дальнейшем для того, чтобы понять, что означает словосочетание между лепестками Qi и Qj предлагается воспользоваться только что нарисованной картиной берем или все, что лежит на одной дуге окружности или все, что на другой.

Определение 16. Внутренними множествами обобщенной ромашки назовем множества Qi,j для всех пар неблизких лепестков. Обозначим через R(F ) набор, состоящий из внутренних множеств ромашки F. Границей ромашки назовем множества Qi,i+1 для всех i.

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

Лемма 1.2. Для обобщенной ромашки F = (P ; Q1,..., Qm ) справедливы следующие утверждения.

1) Лепестки с разными номерами не совпадают.

2) Если лепестки Qi и Qj пересекаются, то либо V(Gi,j ), либо V(Gj,i ) совпадает с Qi,j.

3) Если множество Qi,j S, то оно разбивает граф ровно на две обобщенные части, причем это Gi,j и Gj,i.

4) Если множество Qi,j S и лепесток Qk Qi,j, то k = i или k = j.

5) Всякое множество из набора S представляется в виде Qi,j единственным образом.

6) Если множество Qi,j S, то Qi и Qj не являются близкими.

7) Для каждого лепестка Qi найдется такое j, что Qi,j S.

8) Если v Qi Qj и V(Gi,j ) = Qi,j, то все лепестки с номерами от i до j содержат v.

то Qk V(Gi,j ) = Qk (Qi Qj ) для произвольного k от j + 1 до i 1.

Доказательство. 1) Пусть Qi = Qj, но i = j. Тогда по определению обобщенной ромашки лепестки Qi и Qj близки, то есть все лепестки, лежащие между ними с одной из сторон, содержатся в Qi,j. Не умаляя общности, это лепестки с номерами от i до j. Но так как Qi = Qj, а во всех лепестках поровну вершин, получаем просто, что для всех k от i до j выполнено равенство Qk = Qi. Тогда части Gi,i+1 и Gj1,j пусты.

Значит, они совпадают. Но все части в определении обобщенной ромашки различные. Поэтому j = i + 1, и лепесток Qj+1 уже не совпадает с Qi. Но в таком случае V(Gi,i+1 ) V(Gi+1,i+2 ). Противоречие.

2) Заметим, что по определению обобщенной ромашки лепестки Qi и Qj близки. Не умаляя общности, считаем, что лепестки с номерами от i до j лежат в Qi,j. Ясно, что тогда любые два таких лепестка пересекаются. Множество Gi,j является объединением нескольких частей разбиения графа G набором S. При этом, очевидно, Gi,j = G (хотя бы потому, что в Gi,j не содержится ни одного множества из набора S). Поэтому, если мы выкинем объединение границ всех частей, содержащихся в Gi,j, и при этом от Gi,j что-то останется, то граф G обязательно распадется на несколько компонент связности. Но заметим теперь, что границы всех этих частей, содержащихся в Gi,j, состоят из центра ромашки некоторых вершин лепестков с номерами от i до j, а все эти лепестки содержатся в Qi,j. Значит, множество Qi,j как раз и является объединением границ этих частей. Но в нем меньше, чем k вершин, поэтому оно не может быть разделяющим. Тогда после удаления Qi,j от Gi,j ничего не останется. То есть, действительно Gi,j = Qi,j.

3) Докажем, что Qi,j не может разделять Gi,j (в смысле обобщенных частей). Мы знаем, что V(Gi,j ) = j1 V(Gx,x+1 ), причем любые две соседx=i ние части разбиения графа ромашкой F пересекаются как минимум по лепестку, входящему в границы обеих этих частей. Так как по определению Qi,j не может разделять ни одну из частей Gx,x+1, то для того, чтобы разделить Gi,j, наше множество должно содержать некий лепесток Qy, где y от i + 1 до j 1. Но тогда по первой части нашей леммы лепесток Qy обязан пересекаться и с Qi, и Qj. Значит, по части 2 нашей леммы множество вершин одной из частей Gi,y и Gy,i совпадает с Qi,y. При этом, очевидно, лепесток Qj не содержится в Qi,y. Поэтому именно V(Gi,y ) совпадает с Qi,y. Аналогично, V(Gy,j ) = Qy,j. Из того, что Qi,y Qy,j = Qi,j, следует равенство V(Gi,j ) = Qi,j. Но тогда множество Qi,j, очевидно, не может разделять Gi,j. Противоречие.

Таким образом, множество Qi,j не разделяет Gi,j. Совершенно аналогично получаем, что оно не разделяет и Gj,i. Но в определении обобщенных частей разбиения графа неким разделяющим множеством говорится, что этих частей должно быть как минимум две. Значит, действительно, подграфы Gi,j и Gj,i являются обобщенными частями разбиения графа G множеством Qi,j, и других обобщенных частей нет.

4) Заметим, что в ходе доказательства части 3) нашей леммы мы предположили, что в разделяющем множестве Qi,j из набора S содержится лепесток Qy, где y от i + 1 до j 1, и доказали, что в таком случае обязательно V(Gi,j ) = Qi,j. С другой стороны, из той же части 3) следует, что обобщенными частями являются Gi,j и Gj,i. Но множество вершин обобщенной части не может содержаться в самом разделяющем множестве. Противоречие.

5) Пусть T S, причем T = Qi,j = Qk,. Если k совпадает с i или с j, то совпадает с j или с i соответственно, и это один и тот же способ разбить T на два лепестка и центр. Если же k не совпадает ни с i, ни с j, то это противоречит утверждению пункта 4) нашей леммы.

6) Пусть Qi и Qj близки. Тогда в Qi,j содержатся все лепестки, лежащие между Qi и Qj с одной из сторон. Предположим, что Qi,j S.

По определению обобщенной ромашки лепестки Qi и Qj не могут быть соседними. Значит, найдется такое k, отличное от i и j, что Qk Qi,j. А это противоречит утверждению пункта 4) нашей леммы.

7) Рассмотрим лепесток Qi и части Gi1,i и Gi,i+1. Заметим, что какое-то множество T из набора S должно разделять эти две части.

Ясно, что оно обязано содержать все общие вершины этих двух частей.

Но среди этих общих вершин есть все вершины лепестка Qi. Значит, доказали, что Qi T. Тогда по пункту 4) этой леммы получаем, что T = Qi,j для некоторого j.

8) Пусть нашелся лепесток Qk, где k от i + 1 до j 1, не содержащий вершину v. По пункту 7) этой леммы найдется такое, что Qk, S.

Заметим, что если поэтому Q пересекается с Qk, и поэтому эти два лепестка близки, что противоречит пункту 6) нашей леммы. Значит, пункту 3) нашей леммы множество Qk, разбивает граф на две обобщенные Gk, и G,k. Но вершина v лежит в обеих этих частях. Значит, она части обязана лежать и в Qk,. Так как v Qk, обязательно v Q. То есть лепесток Q должен пересекаться и с Qi, и с Qj. Тогда он близок к ним обоим.

Заметим, что по пункту 2) множество вершин одного из подграфов Gi, и G,i совпадает с Qi,. Но есть следующее включение мноV(Gi, ) V(Gi,j ) Qk. Поэтому если V(Gi, ) совпадает с Qi,, жеств то Qk Qi,, что невозможно, так как Qk и Q не пересекаются. Значит, именно V(G,i ) совпадает с Qi,. Аналогично получаем, что V(Gj, ) = Qj,.

Но тогда все вершины графа лежат в объединении центра обобщенной ромашки и лепестков Qi, Qj и Q, а мы изначально предполагаем, что в графе G больше, чем 2k |P | вершин. Противоречие.

9) Пусть v Qk V(Gi,j ). Тогда, так как v не может лежать во внутренности ни одной из частей разбиения графа G ромашкой F, найдется лепесток Q, содержащий v, где от i до j. По второму пункту текущей леммы одна из частей G,k и Gk, должна совпадать с Qk,. Пусть это часть Gk,. Тогда по восьмому пункту текущей леммы все лепестки с номерами от k до содержат v. В частности, лепесток Qi содержит ее.

Аналогично, если часть G,k совпадает с Qk,, то Qj содержит v.

k-разделяющих множеств, порождающего обобщенную ромашку, связен.

Теперь все готово для того, чтобы доказать Теорему 1.

Доказательство. Рассмотрим два произвольных неблизких лепестка Qi и Qj. Заметим, что в обоих подграфах Gi,j и Gj,i есть вершины, не лежащие в Qi,j. Ясно, что все вершины множества Qi,j являются общими вершинами этих двух подграфов. Докажем, что других общих вершин у них нет.

Рассмотрим произвольную их общую вершину v, не лежащую в Qi,j.

Если она является внутренней вершиной какой-либо из частей разбиения графа ромашкой F, то она лежит только в этой части, и поэтому не может лежать и в Gi,j и в Gj,i. Значит, она не является внутренней вершиной ни одной из частей разбиения. Теперь вспомним, что V(Gi,j ) = V(Gi,i+1 )· · · V(Gj1,j ) = P (Int(Gi,i+1 )· · ·Int(Gj1,j ))(Qi · · ·Qj ). Поэтому, так как вершина v лежит в части Gi,j, но не является внутренней вершиной ни одной из частей разбиения графа ромашкой F и не лежит в Qi,j, должно найтись такое k от i + 1 до j 1, что v Qk. Аналогично, найдется такое разные стороны от Qk и Q. Значит, по определению обобщенной ромашки лепестки Qk и Q близки и по пунктам 2 и 8 леммы 1.2 либо v Qi, либо v Qj. Противоречие.

Таким образом все общие вершины Gi,j и Gj,i это вершины множества Qi,j. Предположим, что оно не разделяет подграфы Gi,j и Gj,i.

Тогда должны найтись такие две смежные вершины u и v, не лежащие в Qi,j, что u V(Gi,j ), а v V(Gj,i ). Ясно, что должна найтись часть разбиения графа обобщенной ромашкой F, содержащая обе эти вершины.

Не умаляя общности, считаем, что это часть Gk,k+1, где k от i до j 1.

Но V(Gk,k+1 ) V(Gi,j ), поэтому все общие вершины Gk,k+1 и Gj,i лежат в Qi,j. Тогда вершина v лежит в Qi,j. Противоречие.

Следствие 1.1. [26, следствие 4] Для обобщенной ромашки F = (P ; Q1,..., Qm ) выполняются следующие утверждения.

1) Расположим индексы 1, 2,..., m по окружности соответственно их циклическому порядку и поставим в соответствие множеству Qi,j хорду этой окружности, соединяющую i и j. Тогда внутренние множества Qx,y и Qz,t ромашки F являются зависимыми k-разделяющими множествами в том и только том случае, когда соответствующие им хорды окружности пересекаются во внутренней точке.

2) Если множества Qx,y и Qz,t являются зависимыми разделяющими множествами, то Qx,y отделяет друг от друга лепестки Qz и Доказательство этих утверждения непосредственно следует из теоремы 1.

Из теоремы 1 следует, что для неблизких лепестков i и j подграфы Gi,j и Gj,i можно понимать как обобщенные части, на которые Qi,j делит граф G. Соответственно, для них применимы определения границы и внутренности. Кроме того, подграфы Gi,i+1 мы называем частями разбиения графа G ромашкой. Далее для удобства все подграфы Gi,j, где i = j, мы будем называть частями даже если Qi и Qj являются близкими, но не соседними (на самом деле, в этом случае подграф Gi,j является обобщенной частью разбиения графа G обобщенной ромашкой, получающейся из F удалением всех лепестков с номерами от i до j, но мы не будем на этом останавливаться). Для подграфа Gi,j определим понятие внутренности и границы, а также укажем, когда мы будем называть его пустой частью, а когда малой.

Определение 17. Пусть F = (P ; Q1,..., Qm ) обобщенная ромашка, Part(F ) = {G1,2,..., Gm,1 }. Для неравных i и j введем понятия границы и внутренности Gi,j. Границей Gi,j называем Bound(Gi,j ) = Qi,j, ваем часть Gi,j пустой, если у нее пустая внутренность и малой, если |V(Gi,j )| < k.

Лемма 1.4. Для обобщенной ромашки F = (P ; Q1,..., Qm ) верно следующее.

1) Если ни один из лепестков не лежит в объединении остальных, то R(F ) состоит просто из множеств Qi,j для всех пар различных несоседних в циклическом порядке индексов i и j.

2) Если лепестки Qi и Qj являются близкими, но не соседними, то одна из частей Gi,j и Gj,i пуста.

Доказательство. 1) Заметим, что если два лепестки являются близкими, но не соседними, то в их объединении должен содержаться как минимум один лепесток. Поэтому если ни один из лепестков ромашки не лежит в объединении остальных, то близкими являются только соседние лепестки.

А набор R(F ) состоит как раз из множеств вида Qi,j, где лепестки Qi и Qj не являются близкими.

2) Если Qi и Qj пересекаются, то это просто пункт 2) леммы 1.2.

Теперь предположим, что они не пересекаются. Так как эти лепестки несоседние, между ними с обеих сторон есть лепестки. Но они являются близкими, поэтому хотя бы с одной из сторон лепестки, лежащие между ними, целиком содержатся в Qi,j. Не умаляя общности считаем, что это лепестки с номерами от i до j. Рассмотрим Qi+1. Этот лепесток лежит в Qi,j. Поэтому он обязан пересекаться и с Qi, и с Qj. Тогда по второй части леммы 1.2 одна из частей Gi,i+1 и Gi+1,i является пустой. Ясно, что пуста именно Gi,i+1, так как в Gi+1,i есть некоторое количество вершин из Qj, не лежащих в Qi,i+1. Аналогично доказываем, что Gi+1,j пуста. Так как V(Gi,j ) = V(Gi,i+1 ) V(Gi+1,j ) и Qi+1 Qi,j, получаем требуемое.

Лемма 1.5. Пусть набор разделяющих множеств S порождает обобщенную ромашку F. Известно, что вершина u содержится в каждом из множеств набора S. Тогда u лежит в центре ромашки F.

Доказательство. Предположим, что вершина u не лежит в центре ромашки F. Ясно, что u есть в границе каждой из частей разбиения графа G набором S. Тогда для любого i знаем, что либо u Qi либо u Qi+1. Теперь предположим, что нашлись два лепестка Qi и Qj, не содержащие u. Ясно, что они не могут быть соседними. Разберем два случая.

Случай 1. Лепестки Qi и Qj близки. Тогда по лемме 1.4 одна из частей Gi,j и Gj,i пуста, то есть совпадает с Qi,j. Пусть это часть Gi,j.

Тогда Qi,i+1 Qi,j. Но u Qi,j, а один из лепестков Qi и Qi+1 обязан содержать u. Противоречие.

Случай 2. Лепестки Qi и Qj не близки. Тогда по теореме 1 множество Qi,j отделяет Gi,j от Gj,i. Но при этом вершина u есть и в той, и в другой части, а в Qi,j ее нет. Противоречие.

Значит, нет двух лепестков, не содержащих u. Заметим, однако, что любое множество T S является множеством вида Qi,j, где Qi и Qj это два непересекающихся лепестка. В частности, в составе любого T S есть лепесток, не содержащий u. Но у нас среди лепестков ромашки F найдется не более, чем один такой. Таким образом, он есть, и все множества из S содержат его как один из двух образующих лепестков. Выберем любую вершину v этого лепестка и проведем для нее то же самое рассуждение. Получим, что найдется некий другой лепесток, который участвует в образовании всех множеств из S. Значит, набор S состоит из одного множества. Противоречие.

Лемма 1.6. Пусть два несоседних лепестка Qi и Qj обобщенной ромашки F пересекаются, причем именно часть Gi,j является пустой. Тогда имеет место следующее включение множеств:

Доказательство. Докажем, что для любого k от i до j есть включение Qk Qi Qj. Пусть это не так. То есть нашлись такие вершина u Qi Qj и номер k от i до j, что u Qk. Рассмотрим произвольный лепесток Q, для которого такие лепестки содержат вершину u. Разберем два случая.

Случай 1. Лепестки Q и Qk близки. Тогда либо Qi Q,k либо Qj Q,k.

Так как u Qi Qj, в любом случае получаем, что u Q,k. Но u Qk.

Значит, u Q.

Случай 2. Лепестки Q и Qk не близки. Тогда по теореме 1 множество Q,k отделяет G,k от Gk,. Но при этом вершина u есть и в той, и в другой части. Значит, она должна быть и в Q,k.

Теперь рассмотрим любое множество T S. Заметим, что максимум один из двух лепестков, образующих T, находится среди Qi,Qi+1,...,Qj, так как любые два лепестка из этой группы пересекаются. Значит, для любого T S найдется такое, не равное ни одному из i, i + 1,..., j, что Q T. Но мы доказали, что все такие лепестки содержат вершину u.

Тогда и любое множество из набора S содержит u. По лемме 1.5 получаем, что u P и приходим к противоречию.

Итак, доказали, что для всех k от i до j есть включение Qk Qi Qj.

Значит, для всех k от i до j есть и включение Qi Qk Qi Qj. Если лепестки Qi и Qj1 соседние, то все уже доказано. Пусть нет. Заметим, что Qj1 пересекается с Qi, причем именно часть Gi,j1 является пустой.

Поэтому можно совершенно аналогично доказать, что для всех k от i до j 1 есть и включение Qi Qk Qi Qj1. И так далее. В итоге получим требуемое включение множеств.

Следствие 1.2. Если Qj пересекается с Qi, а Qi+1,..., Qj1 Qi,j, то Лемма 1.7. Для любого i найдется лепесток Qj, не пересекающийся ни с Qi, ни с Qi+1.

Доказательство. Предположим, что это не так. Рассмотрим произвольный лепесток Qj, где j = i, i + 1, пересекающийся с Qi. Тогда либо часть Gi,j, либо часть Gj,i малая по лемме 1.2. Но если мала часть Gi,j, то мала и часть Gi+1,j. Таким образом, если Qj пересекается с Qi то мала одна из частей Gj,i и Gi+1,j. К тому же выводу приходим в случае, когда Qj пересекается с Qi+1. А так как мы предположили, что все лепестки пересекаются либо с Qi либо с Qi+1, получаем что для любого j = i, i + 1 мала одна из частей Gj,i (первый вариант) и Gi+1,j (второй вариант). Заметим, что если для некоторого x = i, i + 1 выполнен первый вариант, то и для всех y от x до i 1 выполнен первый вариант.

Аналогично, если для какого-то x выполнен второй вариант, то и для всех y от i + 2 до x выполнен второй вариант. Теперь рассмотрим два случая.

Случай 1. Найдутся два лепестка, для одного из которых выполняется первый вариант, а для другого что для Qx выполняется первый вариант, а Qx1 второй. Ясно, что такое x найдется. Тогда все лепестки содержатся либо в части Gi+1,x1, либо в части Gx,i. Так как эти части являются малыми, по следствию 1. все лепестки, лежащие в Gx,i, имеют общую вершину пусть это будет вершина u, и все лепестки, лежащие в Gi+1,x1, имеют общую вершину пусть это будет вершина v. Значит, каждый лепесток нашей обобщенной ромашки содержит как минимум одну из вершин u и v. Рассмотрим произвольное множество S = Qs,t из набора, порождающего ромашку F.

Ясно, что лепестки Qs и Qt не могут пересекаться, поэтому один из них содержит вершину u, а другой вершину v. И так для произвольного множества из порождающего набора. Тогда все множества из набора, порождающего ромашку F, содержат вершины u и v. По лемме 1. приходим к противоречию.

Случай 2. Либо для всех лепестков выполняется первый вариант, ливторой. Пусть для всех j = i, i + 1 часть Gi+1,j является бо для всех малой. Тогда часть Gi+1,i1 мала, и все лепестки кроме Qi лежат в ней.

Значит, по следствию 1.2 все лепестки кроме Qi, имеют общую вершину пусть это будет вершина u. Тогда все множества из набора, порождающего ромашку F, содержат эту вершины u, и по лемме 1.5 приходим к противоречию.

Следствие 1.3. Объединение соседних лепестков обобщенной ромашки не может содержать других лепестков.

Доказательство. Пусть Qj Qi,i+1. Ясно, что тогда лепесток Qj пересекается с обоими лепестками Qi и Qi+1. Значит, одна из частей Gj,i+ и Gi+1,j пуста. Рассмотрим лепесток Q, не пересекающийся ни с Qi, ни с Qi+1. Не умаляя общности, будем считать, что j от до i. Тогда по лемме 1.6, если пуста часть Gj,i+1, то все общие вершины лепестков Qj и Qi+ содержатся в Qi, а если пуста часть Gi+1,j, то все эти вершины содержатся в Q. Значит, так как лепестки Qi+1 и Q не пересекаются, есть включение Qj Qi+1 Qi Qi+1. При этом Qj Qi Qi+1. Тогда Qj Qi.

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

Введем определение множества вершин ромашки и максимальной ромашки, которые нам пригодятся в дальнейшем.

Определение 18. Множеством вершин ромашки назовем множество V (F ), состоящее из всех вершин графа, лежащих в центре или хотя бы в одном ее лепестке. Будем говорить, что ромашка F содержит ромашку F, если у них общий центр и V (F ) V (F ). Назовем ромашку F максимальной, если все ромашки, в которых она содержится, имеют то же множество вершин, и лепестков в них не больше, чем в F.

Лемма 1.8. Для обобщенной ромашки F = (P ; Q1,..., Qm ) выполняются следующие утверждения.

1) Пусть Qi и Qj это два таких ее различных лепестка, что i = j 1. Тогда если хотя бы одна из частей Gi,j1 или Gi+1,j непуста, то G(Int(Gi,j )) связен и непуст.

2) Пусть Qi и Qj это два таких ее различных лепестка, что i = j 1. Тогда если G(Int(Gi,j )) несвязен, то в Int(Gi,j ) вершин не больше, чем в лепестке ромашки F.

3) Если Qi и Qj это два не соседних, но близких лепестка, то Qi,j не является разделяющим множеством.

4) Множество Qi,i+1 не разделяет множество V (F ).

Доказательство. 1) Предположим, что одна из частей Gi,j1 и Gi+1,j непуста. Не умаляя общности, это Gi,j1. Тогда в ее внутренности найдется некоторая вершина v. Обозначим через u произвольную вершину лепестка Qj1, не лежащую в Qj. Заметим, что если Qi,j не является разделяющим множеством, то по теореме 1 лепестки Qi и Qj близки, и либо часть Gi,j пуста (что невозможно, так как часть Gi,j1 непуста), либо часть Gj,i пуста, и тогда G(Int(Gi,j )) = G Qi,j (а этот граф связен, поскольку Qi,j Rk (G)). Считаем, что множество Qi,j все же является разделяющим. Тогда Qi не пересекается с Qj. А из этого следует, что Qi,j1 Rk (G) так как обе части Gi,j1 и Gj1,i непусты. Обозначим через H1 подграф Gi,j1 Qi,j, а через H2 G(Int(Gj1,j ) {u}).

Заметим, что H1 связен, так как для каждой вершины x из Qi,j и каждой из частей разбиения Part(Qi,j1 ) найдется вершина, содержащаяся во внутренности этой части и смежная с x, и при этом в H1 есть вершины u и v. Теперь убедимся в том, что и H2 связен. Заметим, что если часть Gj1,j пуста, то H2 состоит из единственной вершины u, и утверждение очевидно. Ну а если эта часть непуста, то вершина u смежна хотя бы с одной вершиной каждой из компонент связности графа G Qj1,j, что гарантирует связность H2.

Остается заметить, что V(Int(Gi,j )) = V(H1 ) V(H2 ), причем V(H1 ) V(H2 ) =, так как в обоих подграфах есть вершина u.

2) Предположим, что G(Int(Gi,j )) несвязен. По предыдущей части леммы получим, что обе части Gi,j1 и Gi+1,j пусты. Значит, Int(Gi,j ) = (Qi+1 Qj1 ) \ Qi,j. Но ясно, что Qj1 V(Gi+1,j ) = Qi+1,j. Поэтому Int(Gi,j ) = Qi+1 \Qi,j. А тогда в Int(Gi,j ) вершин не больше, чем в лепестке ромашки F.

3) По части 2) леммы 1.4 одна из частей Gi,j и Gj,i пуста. Не умаляя общности, допустим, что это Gj,i. Тогда GQi,j = Int(Gi,j ). Предположим, что Qi,j все же является разделяющим. Значит, G(Int(Gi,j )) несвязен. Поэтому из первой части этой леммы следует, что обе части Gi,j1 и Gi+1,j пусты. Но тогда Int(Gi,j ) Qi+1, из чего следует, что в графе G слишком мало вершин (то есть меньше, чем 2k |P |). Противоречие.

4) Заметим, что любое множество из набора, порождающего ромашку, лежит либо в Gi+2,i, либо в Gi+1,i1. Предположим, что обе эти части пусты. Тогда порождающих множеств всего два, и они являются границами этих частей. Но они, очевидно, пересекаются по вершинам, не содержащимся в центре (часть Gi+2,i пуста, и лепесток Qi1 лежит в ней).

Противоречие с леммой 1.5.

Поэтому обе эти части не могут быть пусты. Значит по первому пункту этой леммы, примененному к лепесткам Qi+1 и Qi (именно в таком порядке) получаем, что G(Int(Gi+1,i )) связен. Но, очевидно, имеет место включение V (F ) Int(Gi+1,i ) Qi,i+1. Значит, множество Qi,i+1 не разделяет V (F ).

Следствие 1.4. Пусть F = (P ; Q1,..., Qm ) обобщенная ромашка.

Каждому множеству Qi,j из R(F ) мы поставим в соответствие обобщенное разбиение графа на части Gi,j и Gj,i. Тогда R(F ) с таким набором разбиений порождает F.

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

Тогда этот набор является подмножеством R(F ). Заметим, что добавление остальных внутренних множеств (не вошедших в этот набор) ничего испортить не может, потому что обобщенные части для каждого из множеств берутся такие, что каждая из частей разбиения графа ромашкой F лежит в одной из них.

Следствие 1.5. Пусть F и F это две обобщенные ромашки с одинаковыми по величине центрами, а разделяющее множество S является внутренним для обеих этих ромашек, причем в первом случае разбиение на обобщенные части согласовано с разбиением I, а во втором с I.

Тогда PartI (S) = PartI (S).

Доказательство. Заметим, что если |Part(S)| = 2, то утверждение тривиально. Теперь рассмотрим случай, когда |Part(S)| > 2. По пункту леммы 1.2, множество S разбивает граф G ровно на две обобщенные части и как внутреннее множество ромашки F, и как внутреннее множество ромашки F. Пусть разбиения графа G множеством S на обобщенные части, согласованные с F это A1 и A2, а согласованное с F это B и B2. Так как S разбивает граф G более, чем на две части, одна из обобщенных частей A1 и A2 не является настоящей частью разбиения графа множеством S. Не умаляя общности, это часть A1. То есть подграф, индуцированный на внутренности этой части, несвязен. Тогда во внутренности A1 по второму пункту леммы 1.8 вершин не больше, чем в лепестке F.

Поэтому во внутренности A2 больше, чем в лепестке (иначе в графе будет слишком мало вершин). Рассуждая аналогично, получим, что если часть A2 не является настоящей частью, то в ее внутренности вершин не больше, чем в лепестке F, что невозможно. Значит, обобщенная часть A является настоящей частью разбиения графа множеством S. Тогда она обязана лежать в B1 или в B2. Не умаляя общности, считаем, что она лежит в B2. Если A2 = B2, то A1 = B1, и нужное доказано. Предположим, что это не так, то есть в B2 есть что-то еще кроме A2. Но в таком случае внутренность обобщенной части B2 несвязна, и по лемме 1.8 вершин в ней должно быть не больше, чем в лепестке F. Ясно, что лепестки ромашек F и F имеют один и тот же размер, так как их центры содержат одно и то же количество вершин. Но A2 B2, в A2 вершин больше, чем в лепестке, а в B2 не больше. Противоречие.

Теперь докажем Теорему 2.

Доказательство. Пусть FS = (P ; Q1,..., Qm ), а FT = (P ; Q1,..., Qm ).

Ясно, что V (FS ) = V (FT ). Рассмотрим неблизкие лепестки Qi и Qj ромашки FS. По теореме 1 знаем, что множество Qi,j является разделяющим, причем оно разделяет V (FS ). Пусть в ромашке FT это лепестки Qx и Qy.

По пункту 3) леммы 1.8 получаем, что они являются либо соседними, либо неблизкими, а по пункту 4) той же леммы заключаем, что соседними они быть не могут. Таким образом мы доказали, что неблизкие лепестки одной ромашки являются неблизкими лепестками другой.

Тогда два соседних лепестка одной ромашки в другой является либо соседними, либо близкими, но не соседними. Но в объединении двух соседних лепестков по следствию 1.3 не может содержаться других лепестков, поэтому второй вариант исключается. Значит, соседние лепестки одной ромашки являются соседними и в другой. Тогда циклические порядки лепестков в наших ромашках одинаковы. Применим следствие 1. и получим, что Part(S) = Part(T).

Лемма 1.9. Пусть F обобщенная ромашка, а Qi и Qj это два ее различных лепестка. Рассмотрим множество T Qi,j. Тогда справедливы следующие утверждения.

1) Если Gi,j непуста, а T = Qi,j, то граф Gi,j T связен.

2) Если T = P Qi (Qj \{u}), где u Qj, то граф Gi,j T является либо пустым, либо связным.

Доказательство. 1) Заметим, что если часть Gj,i пуста, то граф Gi,j T совпадает с G T, который связен, так как сам граф G является k-связным, а в множестве T менее k вершин. Значит, можно считать, что часть Gj,i непуста. Тогда множество Qi,j является k-разделяющим и разбивает граф на обобщенные части Gi,j и Gj,i. Заметим, что каждая из вершин множества Qi,j должна быть смежна хотя бы с одной из вершин каждой из компонент связности графа GQi,j. Поэтому, так как T Qi,j, но содержит не все его вершины, граф Gi,j T связен.

2) Нам важно, пусты или нет части Gi,j и Gj,i, поэтому удобно разобрать несколько случаев.

Случай 1. Часть Gi,j пуста. Тогда либо граф Gi,j T пуст, если u Qi, либо в нем всего одна вершина и он, очевидно, связен.

Случай 2. Часть Gj,i пуста. В этом случае граф Gi,j T совпадает с графом G T, который связен, так как сам граф G является k-связным, а в множестве T менее k вершин.

Случай 3. Части Gi,j и Gj,i непусты. Тогда лепестки Qi и Qj не пересекаются, и, в частности, u Qi. Значит, множество T = Qi,j, и можно применить утверждение предыдущего пункта.

Определение 19. Для произвольных двух множеств вершин A и B графа G через E(A, B) будем обозначать множество ребер этого графа, соединяющих вершины из A с вершинами из B.

Определение 20. Пусть F = (P ; Q1,..., Qm ) обобщенная ромашка.

Рассмотрим два ее произвольных лепестка Qi и Qj, где i = j. Ребро части Gi,j назовем внешним, если ни для какого x от i до j 1 оно не является ребром части Gx,x+1. Множество внешних ребер части Gi,j обозначим через EF (i, j).

Замечание 1.5. 1) Довольно часто верхний индекс будем опускать, если понятно, о какой ромашке речь. У двух обобщенных ромашек может быть общая часть, и ребро, внешнее для нее в одной из ромашек, может не быть таковым в другой.

2) Несложно убедиться в том, что EF (i, j) E(Qi, Qj ). Это следуout ет из того, что ни одна из вершин не лежит одновременно в Int(Gi,j ) и в Int(Gj,i ).

3) Ясно, что Eout (i + 1, i) = E(Qi, Qi+1 ).

Лемма 1.10. Пусть F = (P ; Q1,..., Qm ) это обобщенная ромашка, рим произвольное k от i + 1 до j 1.

1) Предположим, что Qi Qj,k и Qj Qi,k. Тогда множество Qk (Qi Qj ) отделяет V(Gi,k ) от V(Gk,j ) в подграфе Gi,j Eout (i, j) P.

2) Предположим, что часть Gj,i не является малой. Тогда множество Qk отделяет V(Gi,k ) от V(Gk,j ) в подграфе Gi,j Eout (i, j) P.

Замечание 1.6. Эта лемма, так же как и все последующие леммы в разделе, посвященном ромашкам в k-связном графе для произвольного k, направлена на доказательство того, что, в некотором смысле, при изучении месторасположения лепестков ромашки F подграф Gi,j можно считать отрезком, в отличие от графа G, который, как уже говорилось, удобнее отождествлять с окружностью. При этом нельзя забывать про одну тондля того, чтобы эта логика работала, надо удалить из части Gi,j кость все внешние ребра.

На самом деле, в данной работе структура ромашки изучается как раз посредством перехода к подграфам вида Gi,j Eout (i, j), потому что строго доказывать утверждения про лепесток, разделяющий такой подграф (“отрезок”) гораздо проще, чем про пару лепестков, разделяющих весь граф (“окружность”).

Данная лемма показывает, что каждый лепесток с номером от i до j действительно разделяет наш “отрезок” от Qi до Qj (подграф Gi,j Eout (i, j)), причем его “концы” (лепестки Qi и Qj ) лежат в разных частях.

Доказательство. 1) Предположим, что утверждение леммы не выполнено и лепестки Qi и Qj не пересекаются. Тогда либо найдется вершина v, лежащая в обеих этих частях, но не лежащая ни в центре, ни в лепестке Qk, либо найдутся такие две смежные вершины u и v, не лежащие ни в центре, ни в лепестке Qk, что u V(Gi,k ), а v V(Gk,j ), причем uv Eout (i, j).

Случай 1. Существует вершина v, лежащая в V(Gi,k ) и в V(Gk,j ), но не лежащая ни в центре, ни в лепестке Qk. Из определения ромашки следует, что эта вершина v обязана быть вершиной нашей ромашки и найдутся такие лепестки Qx и Qy, содержащие ее, что x от i до k, а y от k до j. Тогда одна из частей Gx,y и Gy,x является пустой. Значит, по лемме 1.6 либо Qk содержит вершину v, либо оба лепестка Qi и Qj содержат ее. Так как последнее невозможно, получаем, что v Qk.

Противоречие.

Случай 2. Существуют такие две смежные вершины u и v, не лежащие ни в центре, ни в лепестке Qk, что u V(Gi,k ), а v V(Gk,j ), причем uv Eout (i, j). Рассмотрим часть разбиения графа G ромашкой F, содержащую u и v (такая, очевидно, есть). Пусть это G, +1. Заметим, что либо от k до j 1. Не умаляя общности, будем считать, что от i до k 1.

Тогда v является одновременно вершиной Gi,k и Gk,j. Значит, по первому случаю, вершина v должна лежать либо в Qk, либо в центре ромашки F.

Противоречие.

Таким образом, осталось доказать утверждение для пересекающихся лепестков Qi и Qj. Рассуждаем так же, как и раньше, разбираем те же два случая. В первом случае получаем, что все общие вершины V(Gi,k ) и V(Gk,j ) на этот раз лежат в Qk (Qi Qj ), а во втором случае вообще ничего не меняется. Остается заметить, что от V(Gi,k ) и V(Gk,j ) что-то останется после удаления Qk (Qi Qj ), потому что от первого из этих множеств останется как минимум одна вершина лепестка Qi, а от как минимум одна вершина лепестка Qj, иначе Qi Qj,k или второго Qj Qi,k.

2) Заметим, что если Qi Qj =, то часть Gi,j пуста, и по лемме 1. выполнено включение Qk Qi Qj. Если же Qi Qj =, то это включение выполнено тривиальным образом. Тогда Qk Qi \ Qj и Qk Qj \ Qi, так как иначе Qk = Qi или Qk = Qj. Значит, по первой части нашей леммы множество Qk (Qi Qj ) отделяет V(Gi,k ) от V(Gk,j ) в подграфе Gi,j Eout (i, j)P. Но мы знаем, что Qk Qi Qj. Поэтому Qk (Qi Qj ) = Qk, и требуемое утверждение доказано.

различных лепестка. Рассмотрим множество S, которое не содержит ни одной вершины из части Gi,j кроме, возможно, некоторых вершин лепестка Qj. Тогда множество S не отделяет Qi от Qj в Gi,j P Eout (i, j).

Замечание 1.7. Продолжая философские пояснения, начатые в замечании 1.6, можно переформулировать эту лемму следующим образом “концы отрезка” нельзя разделить, удалив лишь некоторый кусок одного из этих “концов”.

Доказательство. Очевидно, можно считать, что S Qj, так как вершины множества S, не лежащие в части Gi,j, нам не мешают. Заметим, что если S = Qj, то утверждение очевидно. Поэтому далее будем считать, что это не так. Ясно, что можно ограничиться случаем S = Qj \ {v}, где v произвольная вершина лепестка Qj.

Случай 1. Часть Gj,i не является малой. Будем доказывать требуемое утверждение по индукции по количеству лепестков в части Gi,j в предположении того, что часть Gj,i не является малой. В качестве базы рассмотрим случай j = i+1. По замечанию 1.5 Eout (i+1, i) = E(Qi, Qi+1 ), а Eout (i, i + 1) =, поэтому надо доказать, что множество S не отделяет Qi от Qi+1 в Gi,i+1 P. Если v Qi, то утверждение очевидно.

Предположим теперь, что v Qi. Заметим, что по лемме 1.5 обязательно найдется множество из набора, порождающего ромашку, не содержащее вершину v. Пусть это множество Qx,y. Очевидно, оба множества Qx и Qy не могут содержать Qi \ Qi+1, так как они не могут пересекаться. Не умаляя общности, считаем, что Qx Qi \ Qi+1. Тогда Qi Qx,i+1. Кроме того, Qi+1 Qx,i, так как в множестве Qx,i точно нет вершины v. Значит, можно применить лемму 1.10 к лепесткам Qi+1, Qi и Qx. Получаем, что Qx (Qi Qi+1 ) отделяет V(Gi+1,x ) от V(Gx,i ) в Gi+1,i E(Qi, Qi+1 ) P.

Теперь удалим из графа G множество T = Qx,i+1 \ {v}. Ясно, что оно содержит в себе множество P Qx (Qi Qi+1 ), но не содержит целиком ни Qi, ни Qi+1, поэтому отделяет V(Gi+1,x ) от V(Gx,i ) в Gi+1,i E(Qi, Qi+1 ).

В частности, T отделяет v от Qi в этом подграфе. Однако, множество T не может быть разделяющим в G, так как в нем k 1 вершина. Значит, от Qi до v есть путь в Gi,i+1 (Qi+1 \ {v}). А это как раз то, что мы хотели доказать.

Теперь докажем переход. Рассмотрим произвольные i и j. Знаем, что множество S Qj. Поэтому S V(Gi,j1 ) Qj V(Gi,j1 ). Кроме того, есть включение Qj V(Gj1,i ), причем, так как часть Gj,i не является малой, по лемме 1.6 знаем, что Qi Qj Qj1. Значит, получается, что Qj V(Gi,j1 ) Qj1. Тогда все общие вершины S и V(Gi,j1 ) содержатся в лепестке Qj1. Применим доказанное утверждение для Qj1 и Qj и получим, что найдется вершина v, связанная с v в Gj1,j P S. Обозначим путь, соединяющий вершины v и v в этом подграфе, через P1. Рассмотрим S = S (Qj1 \ {v }). Ясно, что все вершины множества S, содержащиеся в части Gi,j1, содержатся в лепестке Qj1. Применим индукционное предположение для множества S и лепестков Qi и Qj1 и получим, что S не отделяет Qi от Qj в Gi,j1 P Eout (i, j 1), то есть найдется вершина u Qi, связанная связаны и в Gi,j1 P S Eout (i, j 1). Обозначим путь, соединяющий их в этом подграфе, через P2. Заметим, что ни один из путей P1 и P не может проходить по ребрам из множества Eout (i, j), потому что эти ребра либо вообще не лежат ни в Gi,j1, ни в Gj1,j, либо лежат в Gi,j и тогда, очевидным образом, являются ребрами из Eout (i, j 1). Тогда вершины u и v связаны в Gi,j P S Eout (i, j), то есть множество S не отделяет Qi от Qj в Gi,j P Eout (i, j).

Случай 2. Часть Gj,i является малой. Заметим, что в этом случае G = Gi,j, и нужное утверждение очевидно следует из k-связности графа G.

Рассмотрим произвольное множество Q V(Gi,i+1 ) \ P, содержащее столько же вершин, сколько содержат лепестки ромашки F.

Тогда если множество Q отделяет Qi от Qi+1 в Gi,i+1 P, то F = (P ; Q1,..., Qi, Q, Qi+1,..., Qm ) обобщенная ромашка. Причем если S порождает F, то найдется такое j, что S {Qj Q P } порождает F.

Доказательство. По лемме 1.7 найдется лепесток Qj, не пересекающийся ни с Qi, ни с Qi+1. Ясно, что Qi Qi+1,j и Qi+1 Qi,j.

Тогда по лемме 1.10 множество Qj (Qi Qi+1 ) отделяет V(Gi+1,j ) от V(Gj,i ) в графе Gi+1,i E(Qi, Qi+1 ) P (помним, что по замечанию 1. E(Qi, Qi+1 ) = Eout (i + 1, i)). Очевидно, что Q содержит Qi Qi+1, а также как минимум один конец каждого из ребер между этими лепестками.

При этом множество S = Q Qj P не содержит целиком ни один из лепестков Qi и Qi+1. Значит, множество S отделяет V(Gi+1,j ) от V(Gj,i ) в графе Gi+1,i. Но с другой стороны по условию мы знаем, что Q отделяет Qi от Qi+1 в Gi,i+1. Тогда и множество S отделяет Qi от Qi+1 в Gi,i+1.

Представим разбиение графа Gi,i+1 множеством Q как разбиение на две обобщенные части, одна из которых содержит Qi, а другая Qi+1. Первую назовем частью Gi, а вторую частью Gi+1. Тогда S является разделяющим множеством в графе G, причем все части из Part(S) можно разбить гая Набор S разбивает граф на m частей G1,2,...,Gm,1. Ясно, что если мы добавим к этому набору множество S (разбивающее G на обобщенные части G(V(Gi+1,j ) V(Gi+1 )) и G(V(Gj,i ) V(Gi ))), то просто часть Gi,i+ распадется на части Gi и Gi+1, а остальные части останутся прежними, причем с теми же границами. Заметим, что граница Gi состоит из вершин лепестков Qi и Q, а также из центра P нашей ромашки, так как лепесток Qj не пересекается с V(Gi,i+1 ). Аналогично, граница части Gi+ состоит из лепестков Qi+1 и Q, а также из центра P. Таким образом, главное свойство ромашки выполнено. Осталось доказать, что любые два пересекающихся лепестка близки. Удобнее рассмотреть два случая.

Случай 1. Пересекаются два лепестка Qx и Qy ромашки F. Так как в ромашке F нужное условие было выполнено, одна из частей Gx,y и Gy,x является малой. Пусть это Gx,y. Если i не от x до y 1, то новый лепесток Q ничему не мешает. Предположим, что i все же от x до y 1.

Тогда часть Gi,i+1 целиком лежит в пустой части Gx,y, а следовательно, и сама является пустой. Значит, наш новый лепесток Q обязан лежать в Qi,i+1 Qx,y.

Случай 2. Лепесток Q пересекается с некоторым лепестком Qx ромашки F. Если x {i, i + 1}, то все очевидно. Пусть x {i, i + 1}. Ясно, что лепесток Qx обязан пересекаться или с Qi, или с Qi+1, так как он не может содержать вершин из Int(Gi,i+1 ). Заметим, что по лемме 1.7 найдется лепесток, не пересекающийся ни с Qi, ни с Qi+1. Он, очевидно, лежит в одной из частей Gx,i и Gi+1,x, и часть с этим лепестком не пуста. Тогда, если Qx пересекается с обоими лепестками Qi и Qi+1, то либо часть Gx,i+1, либо часть Gi,x является малой, и все очевидно.

Поэтому считаем, что Qx пересекается только с одним из лепестков Qi и Qi+1. Не умаляя общности, это Qi. Тогда именно часть Gx,i является малой. Значит, если мы докажем, что Qi содержится в Qx Q, то мы докажем требуемое. Пусть это не так. Ясно, что пересечение лепестков Qi и Qi+1 содержится в Q, так как Q отделяет их друг от друга в Gi,i+1 P. Тогда если Qi Qx,i+1, то Qi Qx Q, а мы предположили, что это не так. Поэтому Qi Qx,i+1. Кроме того, Qi+1 Qx,i, так как Qx Qi+1 =. Значит, можно применить лемму 1.10 и получить, что множество Qx (Qi Qi+1 ) разделяет Qi и Qi+1 в Gi+1,i P E(Qi, Qi+1 ).

Мы знаем, что Q содержит Qi Qi+1, но множество Qx Q не содержит ни Qi, ни Qi+1. Поэтому множество Qx Q тоже разделяет Qi и Qi+ в Gi+1,i P E(Qi, Qi+1 ). Но при этом Q разделяет лепестки Qi и Qi+1 в части Gi,i+1 P. Значит, множество Qx Q разделяет лепестки Qi и Qi+ в графе G P. Тогда множество Qx Q P является разделяющим. Но так как лепестки Q и Qx пересекаются, в нем содержится менее k вершин.

Противоречие.

лепестка. Множество Q содержит столько же вершин, сколько и леот i до j 1, но не совпадает пестки F, и лежит в V(Gx,x+1 ), где x ни с Qx, ни с Qx+1. Тогда если Q в Gi,j P Eout (i, j) разделяет Qi и Qj, то F = (P ; Q1,..., Qx, Q, Qx+1,..., Qm ) обобщенная ромашка.

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

Доказательство. Заметим, что Q V(Gi,x ) = Q Qx, а Q V(Gx+1,j ) = Q Qx+1. Поэтому по лемме 1.11 множество Q не отделяет Qi от Qx в Gi,x P Eout (i, x), а Qx+1 от Qj в Gx+1,j P Eout (x + 1, j). Тогда Q не отделяет Qi от Qx и Qx+1 от Qj в Gi,j P Eout (i, j), так как ребра из Eout (i, j) либо не лежат ни в Gi,x, ни в Gx+1,j, либо лежат в какой-то из них и тогда являются внешними ребрами этой части. Значит, так как множество Q не совпадает ни с Qx, ни с Qx+1, но отделяет Qi от Qj в Gi,j P Eout (i, j), оно обязано отделять Qx от Qx+ в Gx,x+1 P Eout (i, j). Теперь заметим, что ни одного внешнего ребра из Eout (i, j) в части Gx,x+1 по определению быть не может. Поэтому Q отделяет Qx от Qx+1 в Gx,x+1 P. А из этого по лемме 1.12 следует, что F = (P ; Q1,..., Qx, Q, Qx+1,..., Qm ) обобщенная ромашка.

Лемма 1.14. [24, лемма 1] Пусть множества S, T Rk (G) зависимы.

Пусть Part(S) = {F1, F2,..., Fn }, а Part(T ) = {H1, H2,..., Hm }. Для всех i {1,..., n} и j {1,..., m} введем обозначения P = S T, Sj = S Int(Hj ), Ti = T Int(Fi ), Gi,j = G(V(Fi ) V(Hj )).

Тогда Part({S, T }) = {Gi,j }i{1,...,n},j{1,...,m}, Bound(Gi,j ) = P Ti Sj, причем Ti = для всех i {1,..., n} и Sj = для всех j {1,..., m}.

а Qi и Qj это два ее различных лепестка. Рассмотрим граф H, который получается из Gi,j P удалением всех внешних ребер этой части и добавлением всех ребер, соединяющих две вершины из лепестка Qi или две вершины из лепестка Qj. Обозначим через количество вершин в лепестке ромашки F. Тогда для графа H справедливы следующие утверждения.

1) Любое разделяющие множество графа H, содержащее менее вершин, делит его ровно на две части, причем в одной из них лежит лепесток Qi, а в другой лепесток Qj.

2) Граф H является -связным.

3) Если S и T это два зависимых -вершинных разделяющих множества графа H, то пара частей, на которые множество S делит граф H, получается из пары частей, на которые его делит T, заменой S на T. То есть, если Part(S) = {A1, A2 }, а Part(T ) = {B1, B2 }, T = T V(A1 ), T = T V(A2 ), то выполнены следующие равенства множеств (см. рис. 1.3):

Доказательство. 1) Рассмотрим произвольное разделяющее множество S графа H, содержащее менее 2 вершин. Заметим, что разделить ни один из лепестков Qi и Qj невозможно, потому что подграфы графа H, индуцированные на них это полные графы. Значит, если условие этого пункта леммы не выполнено, в PartH (S) должна найтись часть, во внутренности которой нет вершин лепестков Qi и Qj. Но тогда множество SP является разделяющим в G, что невозможно, поскольку |S P | < k, а граф G является k-связным. Таким образом, множество S разбивает H ровно на 2 части, в одной из которых лежит Qi, а в другой Qj.

2) Пусть в некотором разделяющем множестве S графа H менее Рис. 1.3: На всех трех рисунках изображен граф H. На верхнем рисунке его разделяет множество S, на среднем множество T, а на нижнем изобмножества S и T прилегают вплотную ражено утверждение леммы 1. друг к другу.

вершин. Из пункта 1 следует, что S делит H на две части, в одной из которых лежит Qi, а в другой Qj. Обозначим первую через A, а вточерез B. Заметим, что Int(A) \ Qi,j =, так как иначе множерую ство S P Qi является разделяющим, а в нем менее k вершин. Аналогично доказывается, что Int(B) \ Qi,j =. Таким образом, доказано, что V (Gi,j ) = Qi Qj S. В частности, из этого следует, что часть Gj,i не может быть пустой, так как иначе в графе G будет слишком мало вершин.

Теперь рассмотрим произвольное x от j до i. Заметим, что если во множестве S Qx не содержится целиком ни один из лепестков Qi и Qj, то оно является разделяющим в графе G P, так как S и Qx отделяют Qi от Qj в Gi,j P Eout (i, j) и в Gj,i P Eout (j, i) соответственно. Но в таком случае множество S Qx P является разделяющим в графе G, а в этом множестве менее k вершин. Противоречие. Значит, для любого x от j до i множество S Qx содержит либо Qi, либо Qj.

Докажем, что если Qi S Qx и x = i, j, то мала именно часть Gx,i.

Иначе мала часть Gi,x и по лемме 1.6 есть включение Qi Qx Qi Qj, а последнее лежит в S по очевидным соображениям. Из Qi S Qx и Qi Qx S следует Qi S, что невозможно. Аналогично, если Qj S Qx, то мала часть Gj,x. Возьмем T1 = Qi \ S, а T2 = Qj \ S. Выше мы доказали, что для всякого x от j до i множество S Qx содержит один из лепестков Qi и Qj. То есть для всякого x от j до i лепесток Qx содержит одно из множеств T1 и T2.

Рассмотрим произвольное y от i до j. Заметим, что так как S Int(Gi,j ), а Qy Qi Qj и при этом |S| < |Qy |, верно одно из неравенств |S Qi | < |Qy Qi | и |S Qj | < |Qy Qj |. Пусть для некоторого y выполнено первое неравенство. Тогда лепестки Qi и Qy, очевидно, пересекаются, причем мала именно часть Gi,y, так как выше доказано, что часть Gy,i малой не является. Теперь обозначим через T3 пересечение Qi и всех лепестков с номерами от i до j, для которых выполнено первое неравенство. По лемме 1.6 получаем, что |S Qi | < |T3 | и для всякого y от i до j из неравенства |S Qi | < |Qy Qi | следует, что T3 Qy. Аналогично, найдется множество T4 Qj такое, что |S Qj | < |T4 | и для всякого y от i до j из неравенства |S Qj | < |Qy Qj | следует, что T4 Qy.

Итак, нашлись такие множества T1, T2, T3 и T4, что каждый лепесток ромашки F содержит как минимум одно из них. При этом T1, T3 Qi, Qi T1 S и |S Qi | < |T3 |. Значит, множества T1 и T3 пересекаются.

Аналогично, пересекаются и множества T2 и T4. Пусть в пересечении множеств T1 и T3 есть вершина u, а в пересечении T2 и T4 вершина v. Тогда каждый лепесток ромашки F содержит как минимум одну из вершин u и v. Но всякое разделяющее множество из набора, порождающего ромашку F состоит из двух непересекающихся лепестков и центра ромашки.

Значит, во всех разделяющих множествах из порождающего набора есть обе вершины u и v, что противоречит лемме 1.5.

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

3) Заметим, что граф H по предыдущему пункту -связен, поэтому по лемме 1.14 знаем:

Part({S, T }) = {H(V(A1 ) V(B1 )), H(V(A2 ) V(B2 )), Обозначим эти части через C1, C2, C3, C4 соответственно. По условию Qi содержится в части C1. Значит, по первому пункту текущей леммы Qj содержится в части C2. Докажем, что части C3 и C4 пусты. Предположим, что это не так и часть C3 непуста. Тогда Bound(C3 ) отделяет в графе H внутренность части C3 от H \ V(C3 ). Но во множестве Bound(C3 ) менее вершин, поэтому по пункту 1 текущей леммы это множество делит H на части, в одной из которых целиком содержится лепесток Qi, а в другой лепесток Qj. При этом во внутренности части C3 нет ни одной вершины из Qi,j, так как лепесток Qi лежит в C1, а Qj в C2. Противоречие.

Значит, обе части C3 и C4 пусты. Несложно убедиться в том, что из этого следуют указанные равенства множеств.

Следствие 1.6. Пусть F = (P ; Q1,..., Qm ) это обобщенная ромашка, а Qi и Qj это два ее различных лепестка. Рассмотрим такие вершин в лепестке ромашки F. Известно, что S и T разделяют Qi и Qj в Gi,j P Eout (Qi, Qj ). Разобьем все части из Part(S) на две залось, что в смысле этих обобщенных частей множества S и T зависимы. Тогда пара (V(A1 ), V(A2 )) отличается от пары (V(B1 ), V(B2 )) заменой S на T. То есть, если Part(S) = {A1, A2 }, а Part(T ) = {B1, B2 }, T = T V(A1 ), T = T V(A2 ), то выполнены следующие равенства множеств (см. рис. 1.3):

Доказательство. Это прямое следствие третьего пункта предыдущей леммы, надо просто рассмотреть описанный в ней граф H и заметить, что S и T являются в нем зависимыми -вершинными разделяющими множествами, причем вершинно части разбиения совпадают с A1 и A2 для S и с B1 и B2 для T.

Лемма 1.16. Пусть Qi и Qj это два таких лепестка максимальной обобщенной ромашки F, что часть Gj,i не является малой. Известно, что некоторая вершина u Qi в подграфе Gi,j P (Qi \ {u}) Eout (i, j) смежна только с некоторой вершиной v. Тогда v V(F ).

Доказательство. Если v Qj, то утверждение очевидно. Далее считаем, что v Qj. Тогда часть Gi,j не может быть малой. Кроме того, часть Gj,i не является малой по условию. Значит, лепестки Qi и Qj не пересекаются и, в частности u Qj. Рассмотрим Q = Qi {v} \ {u}. Ясно, что Q отделяет Qi от Qj в Gi,j P Eout (i, j). Поэтому, если найдется такое x, что Q V(Gx,x+1 ), то по лемме 1.13 можно добавить Q в ромашку F, что противоречит максимальности F. Значит, такого x не найдется. В частности Q V(Gi,i+1 ), и Qi+1 = Qj. Но Q \ {v}, очевидно, лежит в V(Gi,i+1 ). Поэтому v V(Gi,i+1 ). Заметим, что Qi+1 по лемме 1.10 отделяет V(Gi,i+1 ) от V(Gi+1,j ) в Gi,j Eout (i, j) P. Причем u V(Gi,i+1 ), а v V(Gi+1,j Qi+1,j ), и эти две вершины смежны. Значит, обязательно u Qi+1.

Теперь заметим, что вершина u в подграфе Gi+1,j P (Qi+1 \{u}) Eout (i+1, j) смежна только с v, поскольку u не является концом ни одного из ребер множества Eout (i, j) \ Eout (i + 1, j). Кроме того, очевидно, что часть Gj,i+1 не является малой. Значит, мы можем произвести ту же самую операцию еще раз и перейти к Gi+2,j. И так далее. Так как лепестков конечное число, рано или поздно придем к противоречию.

Следствие 1.7. Пусть Qi и Qj это два таких лепестка максимальной обобщенной ромашки F, что часть Gj,i не является малой. Тогда справедливы следующие утверждения.

единственная вершина из V(Gi,j Qi P ), смежная с u, то v V(F ).

единственная вершина из Int(Gi,j ), смежная с u, причем в части Gi,j содержится лепесток, не пересекающийся с Qi,j, то v V(F ).

Доказательство. 1) Заметим, что если uv Eout (i, j), то можно применить лемму 1.16, а если uv Eout (i, j), то v Qj и утверждение доказано.

2) Рассмотрим лепесток Qx в части Gi,j, не пересекающийся с Qi,j.

По лемме 1.10 этот лепесток разделяет Qi и Qj в Gi,j Eout (i, j) P. Так как он не пересекается ни с Qi, ни с Qj, в графе Gi,j Eout (i, j) между этими двумя лепестками нет ребер. То есть v это единственная вершина из V(Gi,j Qi P ), смежная с u. Значит, по пункту 1 вершина v является вершиной ромашки F.

Лемма 1.17. Пусть Qi и Qj это два различных лепестка обобщенной ромашки F, таких что часть Gj,i не является малой. Нашлось такое x от i до j, что часть Gi,x пуста. Тогда в подграфе Gi,j Qx P Eout (i, j) нет ребер, имеющих ровно один конец в множестве Qi \ Qx.

Доказательство. Если i = j 1, то x = j = i+1 и утверждение очевидно.

Пусть i = j 1. Заметим, что Qx по лемме 1.10 отделяет V(Gi,x ) от V(Gx,j ) в Gi,j Eout (i, j) P. Так как часть Gi,x пуста, в данном случае это означает, что Qx отделяет Qi от V(Gi,j Qi ) в Gi,j Eout (i, j) P. Значит, вершины из Qi \Qx не могут быть смежны с вершинами из V(Gi,j Qi Qx ) в подграфе Gi,j Eout (i, j) P. Отсюда вытекает требуемое.

Глава Ромашки в четырехсвязном графе Теперь вернемся к случаю четырехсвязного графа, то есть k = 4. Заметим, что центр ромашки в этом случае состоит либо из двух вершин, либо из нуля вершин.

Определение 21. Ромашки с центром, состоящим из двух вершин, мы будем называть 2-ромашками, а ромашки с пустым центром 0-ромашками.

2.1 2-Ромашки Ромашки с центром, состоящим из двух вершин, очень похожи на ромашки в трехсвязном графе (см. [24]). Причина кроется в том, что при удалении одной из вершин центра 2-ромашки граф становится трехсвязным, а наша ромашка становится ромашкой в нем. Для удобства будем обозначать лепестки не множествами Qi, а вершинами qi, где Qi = {qi }. Вершины центра P обозначим через p1 и p2.

В следующей лемме мы покажем, что обобщенные и обычные 2-ромашки это одно и то же, причем все 2-ромашки являются правильными. Заметим сразу же, что из первой ее части будет следовать, что в данном случае R(F ) это набор разделяющих множеств, состоящий из множеств Qi,j для всех пар различных несоседних в циклическом порядке индексов i и j.

Лемма 2.1. 1) В случае 2-ромашки соседние и близкие лепестки это одно и то же.

2) Утверждение леммы 1.8 в данном случае можно усилить для любых двух несоседних в циклическом порядке индексов i, j получается, что Part(Qi,j ) = {Gi,j, Gj,i }.

2-ромашками.

Доказательство. 1) Очевидно, так как все лепестки состоят из одной вершины, и если какой-то содержится в объединении других, то он обязан совпадать с одним из них.

2) Если хотя бы одна из частей Gi+1,j и Gi,j1 непуста, то можно воспользоваться леммой 1.8. Предположим, что обе они пусты. Тогда j = i + 2, и в Int(Gi,j ) есть ровно одна вершина Part(Qi,j ). Аналогично Gj,i Part(Qi,j ).

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

Следующее замечание (и его доказательство) совершенно аналогично замечанию 2 из [24].

Замечание 2.1. 1) Если часть Gi,i+1 пуста, то вершины qi и qi+1 смежны.

2) Если обе части Gi1,i и Gi,i+1 пусты, то вершина qi смежна в графе G с вершинами p1, p2, qi1, qi+1 и только с ними.

Следствие 2.1. Если граф зависимости набора {S1, S2,..., Sn } R4 (G) связен и | n Si | 2, то этот набор порождает 2-ромашку.

Данное следствие совершенно аналогично следствию 4 из [24], а следующая лемма доказывается так же, как лемма 4 из [24].

Лемма 2.2. Пусть F = (P ; q1,..., qm ) максимальная 2-ромашка. Тогда выполняются следующие утверждения.

1) Не существует множества T R4 (G) \ R(F ), содержащего P и зависимого хотя бы с одним из внутренних множеств ромашки F.

2) Для любой вершины v Int(Gi,i+1 ) существует путь из qi в qi+1, не проходящий через v, внутренние вершины которого лежат в Int(Gi,i+1 ).

Замечание 2.2. [24, замечание 3] 1) По набору R(F ) нетрудно восстановить центр и лепестки ромашки F.

2) Нетрудно понять, что ромашка F содержит ромашку F тогда и только тогда, когда R(F ) R(F ).

3) Из пункта 1 леммы 2.2 легко следует, что каждая 2-ромашка содержится в единственной максимальной.

Докажем Теорему 3.

Доказательство. Пусть F 2-ромашка, а S 4-разделяющее множество, содержащееся в множестве вершин F. Предположим, что S не является ни внутренним множеством F, ни ее границей. Обозначим через P центр F и разберем два возможных случая расположения S.

Случай 1. S P =. Тогда S состоит из четырех вершин, являющихся лепестками F. Пусть F = (P ; q1,..., qm ), где S = {q1, qi, qj, qk }, причем i от 2 до j 1, а k от j + 1 до m. Заметим, что граница части G1,i состоит из четырех вершин, поэтому по лемме 1.9, если эта часть непуста, то граф G1,i S связен. Кроме того, если она все же пуста, то после удаления S от нее останется только G(P ). Аналогично для частей Gi,j, Gj,k и Gk,1. Так как минимум одна из четырех частей все же непуста (иначе в графе слишком мало вершин), получаем, что в графе G S две вершины центра связаны. Значит, и весь граф GS связен. Противоречие.

Случай 2. S P =. Если S P, то все уже доказано. Пусть |S P | = 1. Обозначим эту вершину в пересечении через p. Теперь выкинем из нашего графа эту вершину p. Заметим, что получится трехсвязный граф.

Наша 2-ромашка F превратится в ромашку в этом графе, а множество S\{p} будет состоять из трех лепестков. Но тогда это множество не будет разделяющим в G p [24, лемма 10]. Значит, и множество S не является разделяющим в G.

2.2 0-Ромашки Теперь займемся анализом ромашек с пустым центром. К сожалению, максимальная 0-ромашка, содержащая данную, может быть не единственной. Наша цель описать эту неединственность и выяснить, какие разделяющие множества могут быть зависимы с множествами из R(F ) для 0-ромашки F. Для начала поймем, что означают общие утверждения про ромашки в k-связном графе в нашем конкретном случае 0-ромашек.

Лемма 2.3. Для 0-ромашки F = (Q1,..., Qm ) выполняются следующие утверждения.

1) Пересекаться могут только соседние лепестки. В частности, никакая вершина графа G не лежит сразу в трех лепестках ромашки F.

Причем, если лепестки Qi и Qi+1 пересекаются, то две их необщие вершины смежны.

2) Два лепестка являются близкими тогда и только тогда, когда они являются соседними или между ними (с какой-то из сторон) лежит ровно один лепесток, который при этом содержится в их объединении.

3) Если j {i 2, i 1, i, i + 1, i + 2}, то Qi,j является внутренним множеством ромашки F, причем Part(Qi,j ) = {Gi,j, Gj,i }.

4) Если множество Qi,i+2 является разделяющим, то либо Gi,i+2 Part(Qi,i+2 ), либо обе части Gi,i+1 и Gi+1,i+2 пусты, и внутренность Gi,i+2 состоит из двух несмежных вершин, образующих лепесток Qi+1.

5) Если множество Qi,i+2 является разделяющим, то либо Gi+2,i Part(Qi,i+2 ), либо в F всего четыре лепестка, обе части Gi+2,i+ и Gi+3,i пусты, и внутренность Gi+2,i состоит из двух несмежных вершин, образующих лепесток Qi+3.

Доказательство. 1) Рассмотрим два пересекающихся лепестка Qi и Qj.

Пусть их общая вершина часть Gj,i является малой. Не умаляя общности, считаем, что это Gi,j.

Значит, она состоит из вершины v и двух других вершин лепестков Qi и Qj. Предположим, что j = i + 1. Рассмотрим лепесток Qi+1. Он по пункту 8 леммы 1.2 должен содержать вершину v. Но так как он лежит в части Gi,j, в таком случае он будет совпадать либо с Qi, либо с Qj.

Противоречие.

Пусть лепестки Qi и Qi+1 пересекаются. Обозначим их вершины через x, y, z, где Qi = {x, y}, а Qi+1 = {y, z}. Ясно, что часть Gi,i+ это G(x, y, z). По лемме 1.11 множество {y} не разделяет Qi и Qi+1 в Gi,i+1.

Поэтому вершины x и z обязаны быть соединены ребром.

2) Рассмотрим два близких, но не соседних лепестка Qi и Qj. Тогда все лепестки, лежащие между ними с одной сторон, содержаться в Qi,j.

Считаем, что это лепестки с номерами от i до j. Рассмотрим лепесток Qi+1.

Он содержится в Qi,j и поэтому пересекается и с Qi и с Qj. Тогда по первому пункту лепестки Qi+1 и Qj являются соседними. Значит, обязательно j = i + 2.

3) По определению внутренними множествами (обобщенной) ромашки называются множества вида Qi,j, где лепестки Qi и Qj не близки. По предыдущему пункту близкими лепестками 0-ромашки могут являться только лепестки, между которыми с одной из сторон не более одного лепестка. Значит, если j {i 2, i 1, i, i + 1, i + 2}, множество Qi,j является внутренним множеством ромашки F.

Заметим, что по лемме 1.8 либо G(Int(Gi,j )) связен, и тогда Gi,j Part(Qi,j ), либо обе части Gi,j1 и Gi+1,j пусты. Докажем, что если j {i 2, i 1, i, i + 1, i + 2}, то граф G(Int(Gi,j )) связен. Пусть это не так. Тогда в нем есть хотя бы две вершины. Но по лемме 1.8 обе части Gi,j1 и Gi+1,j должны быть пусты. Из пустоты части Gi,j1 следует, что все вершины из Int(Gi,j ) должны лежать в Qj1. Так как в Int(Gi,j ) не менее двух вершин, а в Qj1 ровно две, получаем что эти два множества совпадают.

Аналогично, Int(Gi,j ) = Qi+1. То есть лепестки Qj1 и Qi+1 совпадают. Но тогда j = i + 2. Противоречие.

Таким образом, доказали, что Gi,j Part(Qi,j ). Аналогично получаем, что Gj,i Part(Qi,j ). Тогда, очевидно, Part(Qi,j ) = {Gi,j, Gj,i }.

4) По лемме 1.8 получаем, что лепестки Qi и Qi+2 не являются близкими, причем либо Gi,i+2 Part(Qi,i+2 ), либо обе части Gi,i+1 и Gi+1,i+ пусты. Предположим, что Gi,i+2 Part(Qi,i+2 ). Тогда в Int(Gi,i+2 ) должно быть хотя бы две вершины, и обе части Gi,i+1 и Gi+1,i+2 пусты. Из пустоты частей Gi,i+1 и Gi+1,i+2 получаем, что лепесток Qi+1 содержит Int(Gi,i+2 ).

Но в Qi+1 ровно две вершины, а в Int(Gi,i+2 ) не менее двух. Значит, Int(Gi,i+2 ) = Qi+1. Из несвязности G(Int(Gi,i+2 )) получаем, что вершины лепестка Qi+1 несмежны.

5) В этом случае Qi,i+2 по лемме 1.8 это внутреннее множество ромашки F. Заметим, что в части 3 текущей леммы при доказательстве того, что Gi,j Part(Qi,j ), мы пользовались лишь наличием в части Gi,j как минимум двух лепестков (кроме Qi и Qj ) и, разумеется, тем, что множество Qi,j является внутренним. Поэтому если в части Gi+2,i есть хотя бы два лепестка кроме Qi и Qi+2, то рассуждая так же, как в части 3 этой леммы, получим, что Gi+2,i Part(Qi,i+2 ). Предположим, что это не так, то есть в части Gi+2,i лежит всего один лепесток. Тогда i + 2 + 2 = i, и в ромашке ровно 4 лепестка. Применяя предыдущий пункт нашей леммы к индексам i + 2 и i + 4, получаем требуемое.