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

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

ГЛАЗМАН Александр Львович ОБОБЩЁННЫЕ РОМАШКИ В ^-СВЯЗНОМ ГРАФЕ

01.01.00 — Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации па соискание ученой стспепи кандидата физико-математических наук

11 ^шэ 2015

Санкт-Петербург — 2014

005559109

Работа выполнена в ФГБУН Санкт-Пстсрбургском отделении Математического института им. В. А. Стсклова Российской академии наук (ПОМИ РАН).

Научный руководитель: КАРПОВ Дмитрий Валерьевич

кандидат физико-математических наук, старший научный сотрудник ФГБУН Санкт-Петербургского отделения Математического института им. В. А. Стеклова Российской академии наук

Официальные оппоненты:

Райгородский Андрей Михайлович доктор физико-математических наук

профессор Московского Государственного Университета им. М. В. Ломоносова Образцова Светлана Анатольевна кандидат физико-математических наук

научный сотрудник (postdoctoral researcher), Тель-Авивский университет Ведущая организация:

Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург.

Защита состоится « 4 » марта 2015г. в 16.00 на заседании диссертационного совета Д002.202.02 в ФГБУН Санкт-Петербургском отделепии Математического института им. В. А. Стсклова Российской академии наук по адресу: 191023, Санкт-Петербург, наб. р. Фонтанки, 27, к. 311.

С диссертацией можно ознакомиться в библиотеке и на сайте ФГБУН Санкт-Петербургского отделения Математического института им. В. А. Стеклова Российской академии наук, http://www.pdmi.ras.ru/pdmi/diss-council-02/disscrtations

Автореферат разослал «_»_2015г.

Ученый секретарь

диссертациошюго совета А. В. Малютин

Общая характеристика работы

Актуальность работы.

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

Одним из основных понятий в теории графов является понятие связности. Граф называется связным, если между любыми двумя его вершинами существует путь. Граф называется (вершшию) к-связным, если в нем по менее к + 1 вершин и при удалении любых к — 1 вершин получается связный граф. Понятие вершинной fc-связности является обобщением понятия связности и по этой причине имеет большое теоретическое и практическое значение.

Одно из направлений исследований по вершинной связности — это исследование структуры разбиения fc-связных графов fc-разделягощими множествами (то есть, ¿-вершинными множествами, удаление которых делает граф несвязным). Интерес к этому объясняется тем, что в изучении свойств связных графов важную роль играет структура разбиения графа точками сочлыьения — вершинами, удаление которых делает этот граф несвязным. Точки сочленения разбивают граф на блоки — максимальные по включению двусвязпые подграфы, структуру этого разбиения удобно отображать с помощью дерева блоков и точек сочленения.

Многими исследователями делались попытки обобщить эти конструкции на разбиение fc-связного графа его ¿.--разделяющими множествами. В 19GG году W.T. Tuttc подробно описал конструкцию разбиения двусвязпого графа его 2-раздсляющими множествами. Эта структура является естественным обобщением структуры блоков и точек сочленения для двусвязпого графа и также отображается с помощью дерева. В 1992 году W. Hohberg предложил обобщение этой конструкции на случай разбиения fc-связного графа его ^--разделяющими множествами для произвольного к. Основным недостатком конструкции, которую предложил W. Hohberg, является зависимость получаемых в результате блоков от процесса разбиения и, как следствие, отсутствие единственности структуры разбиения.

F. Harary, Y. Kodama (19G4) и D. W. Matula (1978) предлагали называть fc-блоком или

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

Д. В. Карпов (2002) предложил новый метод изучения структуры взаимного расположения /с-вершиппых разделяющих множеств ^-связного графа — понятие части разбиения графа набором разделяющих множеств. Д. В. Карпов доказал теорему, утверждающую, что если в каждой части разбиения графа набором А;-вершинных разделяющих множеств не менее к вершин, то все множества этого набора могут быть разбиты па группы, образующие так называемые ромашки. Эти ромашки являются естественным обобщением колес в трехсвязном графе, которые описал Т. ТиНе (1900).

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

Д.В.Карпов (2013) описал дерево разбиения, построенное Таттом (1900) для двусвяз-пого графа, в терминах частей разбиения графа разделяющим множеств. Это дерево очень похоже па дерево блоков и точек сочленения. Роль точек сочленения здесь выполняют одиночные разделяющие множества, то есть разделяющие множества, не зависимые ни с одним другим разделяющим множеством, а роль блоков — части разбиения графа набором всех одиночных разделяющих множеств. При этом, если в часть разбиения добавить ребра между вершинами каждого одиночного разделяющего множества, то получится либо трехсвязпый подграф, либо простой цикл. Части разбиения, являющиеся простыми циклами, соответствуют ромашкам в двусвязном графе. Таким образом, все нсодииочпые разделяющие множества в двусвязном графе содержатся в некоторой максимальной ромашке, причем разные ромашки соответствуют разным частям из дерева разбиения и, как следствие, не разбивают друг друга. Используя эту структуру, Карпов нашел простое доказательство теоремы Маклейна о плапарпости двусвязпого графа, доказал несколько оценок на хроматическое число двусвязпого графа и описал критические двусвязпые

графы.

Таким образом, вопрос об изучении свойств ромашек в ¿-связном графе является актуальным.

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

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

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

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

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

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

Степень достоверности и апробация результатов. Все результаты, представленные в работе, являются достоверными, математически строго доказанными фактами. Основные результаты диссертации обсуждались на семинаре по дискретной математике Санкт-Петербургского отделения Математического института им. В. А. Стсклова РАН, на семинаре по дискретной математике в Уральском федеральном университете (Екатеринбург), на Петербургском топологическом семинаре им. В. А. Рохлина (ПОМИ РАН) и на первом "Российско-Финском симпозиуме по дискретной математике".

Публикации. Основные результаты диссертации содержатся в двух работах, опубликованных в рецензируемых журналах [1, 2].

Структура и объем диссертации. Диссертация состоит из введения, двух глав и библиографии. Общий объем диссертации 135 страниц. Библиография включает 28 наименований на 3 страницах.

Содержание работы

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

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

Определение 1. 1) Пусть Я, X С Будем говорить, что множество Я разделяет

множество X, если не все вершины из X \ Я. лежат в одной компоненте связности графа в-Я.

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

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

Определение 2. 1) Будем называть множества 5, Г £ 9i*(G) независимыми, если S не разделяет Т иТ не разделяет 5. В противном случае, назовем эти множества зависимыми.

2) Каждому набору © С iRit(G) поставим в соответствие граф зависимости Dcp(©), вершины которого — множества набора 6, а две вершины смежны тогда и только тогда, когда соответствующие множества зависимы.

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

Нетрудно доказать, что если Т не разделяет S, то S не разделяет Т, то есть, эти множества независимы.

Определение 3. Пусть © с iH*(G).

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

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

Первая глава начинается с определения самого важного понятия в диссертации — обобщенной ромашки в fc-связпом графе.

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

k — IPI

0<|P|<fc, Qj П Р = 0, \Qi\ = —^—-.

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

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

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

Определение 4. 1) Индексы у пас являются вычетами по модулю то, и удобно представлять их себе как числа от 1 до то, расставленные по кругу — по часовой стрелке для определенности.

Пусть г ^ {j,j — 1}. Тогда под индексами от i до j будем понимать индексы, лежащие па той из дуг между г и j, па которой находится индекс г + 1. Для i = j — 1 под индексами от г до j будем понимать г и j.

Различные индексы г и j будем называть соседними, если г — j — 1 или j = г — 1, и несоседними в противном случае.

2) Назовем Q; и Qj близкими, если включение Qk С Qij выполняется либо для всех к от г до j, либо для всех А; от j до г.

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

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

2) Пусть © С SHt(G) — это набор разделяющих множеств Sb ..., St, которые делят граф па т1:..., mt частей соответственно. Рассмотрим набор 0 = {71,...,/'} такой, что для всех j от 1 до t множество Р является разбиением чисел от 1 до mj на несколько (более одной) групп. Обобщенной частью разбиения графа набором разделяющих множеств ©, согласованной с набором разбиений 3, назовем максимальный по включению индуцированный подграф, целиком лежащий в одной из обобщенных частей разбиения

графа каждым из множеств набора. Множество всех обобщенных частей разбиения графа набором б, согласованных с набором разбиений 3, будем обозначать через Раг1э(б) и называть обобщенным разбиением графа набором б, согласованным с X

3) Вершины части А 6 Раг1(б), не входящие ни в одно из множеств набора 6, будем называть внутренними, а множество всех таких вершин — внутренностью части А, которую будем обозначать через 1п1(Л). Вершины части А, входящие в какие-либо множества из б, мы будем называть граничными, а множество всех этих вершин — границей части А и обозначать через Воипс1(Л).

Теперь можно определить обобщенную ромашку.

Определение 6. 1) Пусть существует такие набор б С состоящий из множеств

вида где г и ] — несоседние, и набор разбиений 3, что обобщенное разбиение Раг^б) состоит из то частей 61,2, £»2,3,..., причем Воиш1(£?^+1) = Кроме того, пусть

из того, что и С^ пересекаются, следует, что они близки. Тогда назовем набор Р обобщенной ромашкой.

2) Множество Р назовем центром, а множества <21,..., <2т — лепестками этой ромашки. Разбиением графа (3 обобщенной ромашкой Р назовем Раг1э^) = {С?! 2, ■ ■., <Зтд}, а подграфы будем называть частями этого разбиения.

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

Определение 7. Внутренними множествами обобщенной ромашки назовем множества (¿¡^ для всех пар неблизких лепестков. Обозначим через ОК{Р) набор, состоящий из внутренних множеств ромашки F. Границами ромашки назовем множества для

всех г.

Пусть = (Р; ..., 0т) — обобщенная ромашка. Теорема 1 утверждает, что С причем множество е отделяет Gij от С?^.

Благодаря теореме 2 становится корректно определено понятие разбиения графа ромашкой F. Пусть наборы 6Дб порождают обобщенные ромашки Р$ и РТ соответственно с одинаковым центром и одинаковыми множествами лепестков. Тогда Теорема 2

утверждает, что Раг1(6) = Раг^Х) и Р.,- = рг (то есть, циклические порядки лепестков в этих ромашках одинаковы).

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

Определение 8. Пусть Р — (Р; <21,..., С}т) — обобщенная ромашка. Рассмотрим два ее произвольных лепестка Qi и где г ф Ребро части G^j назовем внешним, если ни для какого х от г до ] — 1 оно не является ребром части б^ц.!. Мпожество внешних ребер части обозначим через Е^4(г,.;).

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

Обозначим через Е количество вершин в лепестке обобщепной ромашки Р = (Р;0 ь...,дт).

В Лемме 10 доказывается, что для к от г 4- 1 до ] — 1 лепесток С)к отделяет от V(С7*:¿) в подграфе GiJ — Еоиг(г, ]) — Р (при некоторых дополнительных ограничениях). После этого в леммах 12 и 13 исследуется возможность добавления лепестков в ромашку — устанавливаются достаточные для этого условия. Эти утверждения оказываются крайне полезными в доказательстве Теоремы 5.

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

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

к-связного графа.

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

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

Определение 9. Назовем лепесток 0-ромашки переключателем, если он состоит из двух несмежных вершин и лежит в объединении двух соседних с ним лепестков. Если лепесток Qi 0-ромашки .Р = является переключателем, то переключением Qi назовем замену <2; на = (<3;_1 и \

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

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

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

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

Определение 12. Допустим, что вершины обобщенной 0-ромашки можно таким образом обозначить через а, Ъ, ¿ь ¿2, ¿з, ¿4, ¿5, что лепестками ромашки являются множества {а, ¡»}, {¿1, с?2}, {¿2, ¿з}, {¿3, ¿4}, {¿4, ¿5}- Будем говорить тогда, что это — ромашка \Vl-muna.

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

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

1° Граф в изоморфен одному из трех исключений, содержащих либо 10, либо 12 вершин и подробно описанных в диссертации.

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

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

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

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

Список публикаций

1. А. Л. ГЛАЗМАН. Обобщенные ромашки в к-связном графе. 11 Записки научных семинаров ПОМИ, 391, 2011, стр. 45-78.

2. А. Л. ГЛАЗМАН. Обобщенные ромашки в к-связном графе. Часть 2. // Записки научных семинаров ПОМИ, 417, 2013, стр. 11-85.

Подписано в печать 20.01.2015 Формат 60x90/16 Бумага офсетная. Усл. печ. л. 2,25 Тираж 100 экз. Заказ 21

Отпечатано в типографии «Адмирал» 199178, Санкт-Петербург, В.О., 7-я линия, д. 84 А