Структура связности графа тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Карпов Дмитрий Валерьевич

СТРУКТУРА СВЯЗНОСТИ ГРАФА

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

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

16 СЕН 2015

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

005562379

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

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

Дольников Владимир Леонидович, доктор физико-математических наук, профессор, профессор ФГАОУВПО Московского физико-технического института (государственного университета)

Пяткин Артём Валерьевич, доктор физико-математических наук, доцент, заведующий лабораторией дискретной оптимизации в исследовании операций ФГБУН Института математики им. С.Л.Соболева Сибирского отделения Российской академии наук

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

Ведущая организация —

ФГБУВПОиН Санкт-Петербургский академический университет — научно-образовательный центр нанотехнологий Российской академии наук

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

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

Автореферат разослан

Ученый секретарь диссертационного совета, доктор физико-математических наук

А. В. Малютин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность работы. Теория графов является важным, интересным и динамично развивающимся разделом дискретной математики. Одним из классических направлений исследований в теории графов являются исследования по вершинной связности графов. Понятие ¿-связного графа является естественным обобщением понятия связного графа. Это подчеркивает и классическая теорема Менгера, с которой в 1927 году фактически начались исследования по связности. Их продолжили Уитни, Татт, Форд и Фалкерсон, Дирак, Халии, Мадер и другие. В 60-80 годы XX века был всплеск интереса к связности графов. Сейчас продолжают появляться новые работы по этой тематике, пусть и не в таком количестве, как 30 лет назад.

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

Поэтому неоднократно возникали вопросы об аналогичной структуре для графов большей связности. Но даже структура разбиения двусвязно-го графа его двухвершинными разделяющими множествами, построенная В. Т. Таттом в 196G году, намного сложнее. Главная причина в том, что уже двухвершинные разделяющие множества могут быть зависимы, то есть, разбивать друг друга на части. Поэтому невозможно построить древовидную структуру, последовательно проводя разрезы двусвязного графа по двухвершинным разделяющим множествам: разрезая граф по некоторому множеству, мы теряем информацию обо всех зависимых с ним множествах,

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

С повышением вершинной связности сложность структуры возрастает многократно. Только в 2011 году диссертант и А. В. Пастор завершили работу по построению структуры разбиения трёхсвязного графа его трёх-вершинными разделяющими множествами. Эта структура намного сложнее и разнообразнее, чем структура разбиения двусвязного графа.

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

Цели работы. Основные цели диссертации:

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

— изучить структуру минимальных /с-связных графов с малым числом вершин степени к;

— изучить множества вершин /с-связного графа, одновременное удаление которых не нарушает /с-связиость;

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

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

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

Научная новизна. Все основные результаты диссертации являются новыми.

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

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

Основные положения и результаты, выносимые на защиту.

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

придуманную в 1966 году В.Т.Таттом. Полученные конструкции применены для оценки хроматического числа двусвязного графа и для описания структуры минимальных и критических двусвязных графов.

2. Доказано, что минимальные к-связные графы с наименьшим числом вершин степени к — это графы вида где Т — произвольное дерево, степени вершин которого не превосходят к + 1, и только они. Граф С^т строится из к непересекающихся копий дерева Т. Для каждой вершины а дерева Т обозначим через а\, ..., а^ соответствующие ей вершины копий. Если вершина а имеет степень ] в дереве Т, то добавляются к +1 — ] новых вершин степени к, смежных с {аь ...

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

3. При к < 5 для произвольного минимального к-связного графа с помощью дерева описано взаимное расположение рёбер, соединяющих пары вершин степени более к.

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

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

6. Доказано, что в связном графе с более чем одной вершиной, в вершинами степени 3 и < вершинами степени не менее 4 можно выделить остовное дерево, в котором не менее чем + + а листьев, где а > | и, более того, а > 2, кроме трёх графов-исключений, содержащих не бо-

лсе 8 вершин. Построена бесконечная серия графов, для которых оценка достигается.

7. Доказано, что в связном графе с более чем одной вершиной, s вершинами степеней 1 и 3, и t вершинами степени не менее 4, можно выделить остовное дерево, в котором не менее чем + is +1 листьев. Построена бесконечная серия графов, для которых оценка достигается.

8. Доказано, что при к > 1 в связном графе с п > 2 вершинами, максимальная цепочка последовательно соединённых вершин степени 2 в котором имеет длину не более к, можно выделить остовное дерево, в котором не менее чем ¿¿ц71 + I листьев. Построена бесконечная серия графов, для которых оценка достигается.

Степень достоверности и апробация результатов. Все результаты, изложенные в диссертации, являются достоверными, математически строго доказанными фактами. Основные результаты диссертации докладывались на Седьмом и Восьмом Международных семинарах "Дискретная математика и ее приложения" (Москва, МГУ, 2001 и 2004), на Третьем Российско-Финском симпозиуме по дискретной математике (Петрозаводск, 2014), на Moscow Workshop on Combinatorics and Number Theory (Долгопрудный, 2014), на девятой Международной конференции "Дискретные модели в теории управляющих систем" (Москва, МГУ, 2015). Все результаты диссертации докладывались на семинарах по дискретной математике и математической кибернетике в ПОМИ им. В.А.Стеклова РАН, институте математики им. С.Л.Соболева СО РАН, МФТИ, МГУ, СПбГУ.

Публикации. Все результаты диссертации изложены в работах [1]-[12], опубликованных в рецензируемых журналах. Работы [1]-[11] написаны лично диссертантом. Из работы [12], написанной совместно с А. В. Пастором, в диссертацию включена теорема 8 (теорема 5.2 диссертации). Утверждение этой теоремы и его доказательство, включая основные леммы, придуманы диссертантом.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения и списка литературы. Нумерация разделов, формул, определений, замечаний, лемм, теорем, следствий и рисунков ведется отдельно для каждой главы. Текст диссертации изложен на 243 страницах (исключая список литературы). Список литературы содержит 58 наименований.

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

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

В диссертации рассматриваются конечные неориентированные графы без петель и кратных ребер.

Множество вершин и рёбер графа б обозначаются через и

£(С), соответственно. Для количества вершин и рёбер графа С используются обозначения у{С) и е(С), соответственно. Определение 1. Пусть Я с Ц Е(С).

1) Через С?—Я обозначается граф, полученный из (5 в результате удаления всех вершин и рёбер множества Я, а также всех рёбер, инцидентных вершинам из Я.

2) Множество Я называется разделяющим, если граф С —Я несвязен.

Через йа{х) обозначим степень вершины х в графе б, то есть, количество инцидентных ей рёбер. Минимальная степень вершины графа СУ обозначается через 5((3), а максимальная степень — через Д(С7).

Вершина х графа С называется висячей, если ¿а{х) = 1. Если граф б — дерево, его висячие вершины часто называют листьями.

Для ребра е € Е(С) через С • е обознается граф, полученный в результате стягивания ребра е (концы ребра е = ху стягиваются в новую вершину, с которой в графе С? ■ е будут смежны все отличные от а: и у вершины, смежные в <3 хотя бы с одним из концов ребра е).

Через обозначается хроматическое число графа С, то есть, наименьшее возможное количество цветов в правильной раскраске вершин этого графа.

Для X С К((7) через С(Х) обозначается индуцированный подграф графа (? на множестве вершин X (то есть, граф с множеством вершин X и всеми рёбрами графа С?, оба конца которых лежат в X).

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

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

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

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

Напомним понятия блока и точки сочленения связного графа, а также ряд их свойств. Подробнее о них можно прочитать, например, в книге Харари "Теория графов ".

Определение 2. Пусть С — связный граф. Вершина а € У{С) называется точкой сочленения, если граф — а несвязен.

Блоком называется любой максимальный по включению подграф графа С?, не имеющий точек сочленения.

Отметим, что точки сочленения — это как раз одновершинные раздо-

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

Определение 3. Дерево блоков и точек сочленения графа G — это двудольный граф B(G), вершины одной доли которого соответствуют всем точкам сочленения ai,..., ап графа G, а другой — всем его блокам В\, ..., Вп (мы будем обозначать эти вершины так же, как и блоки). Вершины щ и Bj смежны, если и только если щ 6 V(Bj).

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

Обозначим через ?Rk(G) набор, состоящий из всех fc-вершинных разделяющих множеств графа G. Понятие разбиения графа набором разделяющих множеств, впервые определенное диссертантом в [2], оказалось удобным для описания взаимного расположения разделяющих множеств в графе.

Определение 4. Пусть & С 5K/t(G).

1) Множество А с V{G) назовем частью &-разбиения, если никакие две вершины из А нельзя разделить никаким множеством из <5, но любая другая вершина графа G отделена от множества А хотя бы одним из множеств набора <5.

Множество всех частей разбиения графа G набором разделяющих множеств & мы будем обозначать через Part (6).

2) Вершины части А £ Part(ö) назовем внутренними, если они не входят ни в одно из множеств набора©. Множество таких вершин назовем внутренностью части А и будем обозначать через Int (Л).

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

Несложно доказать, что граница части А состоит из всех ее вершин, имеющих смежные вне А.

Вернемся к случаю к = 1 и отметим, что точки сочленения связного графа G — это его разделяющие множества, из них состоит £Ri(G). Множества вершин всех блоков — это части Part(9ti(G)). С помощью понятия части разбиения удобно описывать свойства блоков и точек сочленения.

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

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

Определение 6. Пусть G — Ar-связный граф. Назовем множества S,T е ÍHk(G) независимыми, если S не разделяет Т и Т не разделяет S. В противном случае мы будем называть эти множества зависимыми.

К сожалению, разделяющие множества, состоящие из к > 2 вершин, могут быть зависимыми. Именно с этим связаны основные трудности в изучении fc-связных графов при к > 2. В работе [12] доказано, что для множеств S, Т е t(G) возможны два варианта: либо они независимы, либо каждое из них разделяет другое. Доказательство этого факта — очень простое.

Наличие пар зависимых множеств мешает построить на множествах из 0\k(G) и частях из Part(9tjt(G)) отображающее их структуру дерево,

похожее на дерево блоков и точек сочленения. Однако, такое дерево можно построить для набора из попарно независимых множеств.

Определение 7. Пусть С — ¿-связный граф, © С 9Чк(С), причем все множества набора © попарно независимы. Построим дерево разбиенияТ(С1, б) следующим образом. Вершины одной доли Т(С?, 6) — это множества из ©, а вершины другой доли — части РаЛ(в). Обозначать вершины &) мы будем так же, как соответствующие множества вершин графа в. Вершины 5 6 © и А £ Раг1;(©) смежны в Т(С?, ©), если и только если 5 С А.

Построение Т(С1,©) аналогично построению дерева блоков и точек сочленения. Аналогичными будут и его свойства.

Теорема 1.1. Пусть С — к-связный граф, а 6 С — набор, состоя-

щий из попарно независимых множеств. Тогда выполняются следующие утверждения.

1) Т(С1, ©) — это дерево.

2) Для каждого множества 5 £ 6 выполняется равенство

<1Т (С,в) (5) = |РаЛ(5)|.

Более того, для каждой части А £ Раг^й1) существует единственная часть В 6 Рах1;(©), такая, что В а А и В смежна с 5 в Т(С,<5). Все висячие вершины дерева Т(С,<Б) соответствуют частям Раг1;(©).

3) Множество 5 разделяет в графе (7 части В, В' 6 Рай(©) тогда и только тогда, когда 5 разделяет В и В' в Т{С, ©).

Частным случаем описанной конструкции является дерево разбиения двусвязного графа. Дадим необходимые определения. Пусть граф С дву-связен. Объектом рассмотрения будут множества из *Л2(С).

Определение 8. Назовем множество 5 € одиночным, если оно

независимо со всеми другими множествами из Обозначим че-

рез О (С) набор, состоящий из всех одиночных множеств графа б.

Понятно, что одиночные множества попарно независимы, что позволяет нам дать следующее определение.

Определение 9. 1) Дерево разбиения ВТ(СУ) двусвязного графа С — это дерево Т(С,0(С)).

2) Будем использовать обозначение Раг^б) вместо Раг1(0(С)) и называть части этого разбиения просто частями графа (3. Часть А € Раг^б) назовем крайней, если она соответствует висячей вершине дерева разбиения ВТ(С).

В 1966 году В.Т.Татт описал структуру взаимного расположения двухвершинных разделяющих множеств в двусвязном графе именно с помощью дерева, которое он назвал Т(С). Это дерево — почти что дерево разбиения двусвязного графа одиночными разделяющими множествами (только эти множества и само дерево были определены в книге Татта более сложным образом).

Из теоремы 1.1 следует, что ВТ(СУ) — дерево, все висячие вершины которого соответствуют крайним частям РагЬ(С). Если А е Раг^б) — крайняя часть, то Воипс1(А) — одиночное множество графа б.

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

Определение 10. 1) Для двусвязного графа С? обозначим через С граф, полученный из й добавлением всех отсутствующих в Е(С!) ребер вида аЪ, где {а, 6} £ 0(6).

2) Назовём часть А е Раг^СУ) циклом, если граф С (А) — простой цикл и блоком, если граф С(А) трёхсвязен. Если часть А — цикл, то мы будем называть |Л| длиной цикла А.

Теорема 1.2. Пусть СУ — двусвязный граф. Тогда выполняются следующие утверждения.

1) Каждая часть графа С? — блок или цикл.

2) Множество Я. = {а,Ь} — неодиночное множество изО\2(<?), если и только если а и Ъ — несоседние в циклическом порядке вершины неко-

! торой части-цикла.

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

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

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

Теорема 1.4. Для двусвязного графа С выполняются следующие утверждения.

Списочные раскраски (list colorings) появились относительно недавно и являются сейчас весьма популярным объектом для исследований. Каждой вершине графа v е V(G) ставится в соответствие список L(v) из к цветов, после чего рассматривается правильная раскраска вершин, в которой каждая вершина v должна быть покрашена в цвет из списка L(v). Минимальное такое натуральное число к, что для любых списков из к цветов существует правильная раскраска вершин графа G, обозначается через ch(G) (и называется choice number или списочное хроматическое число). Очевидно, ch(G) > x(G). С помощью дерева разбиения доказана следующая оценка на ch(G).

Теорема 1.5. Для двусвязного графа G выполняются следующие утвер-

1)

2) 3)

X(G) < шах(3, max x(G(,4)) + 1).

ждения.

1) ch(G) < max ch(GM)) + 2.

¿ePart(G) V V "

2) ch(G) < max(3, max ch(G(^))+2).

A -- блок О

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

Определение 11. Пусть G — ¿-связный граф.

1) Граф G называется критическим, если v{G) > fc + 2 и для любой вершины х е V(G) граф G — х не является ¿-связным.

2) Граф G называется минимальным, если для любого ребра е € E(G) граф G — е не является ¿-связным.

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

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

Теорема 1.6. Двусвязный граф G является минимальным тогда и только тогда, когда выполняются следующие условия:

(а) если {а, Ь} € ^(G), то вершины a ub несмежны;

(б) для любого блока А графа G граф) G(A) не имеет ни одного ребра.

Из теоремы 1.6 следует еще несколько фактов о структуре минимальных двусвязных графов.

Следствие 1.5. Пусть G — минимальный двусвязный граф. Тогда выполняются следующие утверждения.

1) Если А — блок графа G, то Int (Л) = 0.

2) Пусть А — крайняя часть графа (7, смежная в ВТ(С) с одиночным множеством 5. Тогда А — цикл, а все его вершины, кроме двух вершин множества Б, имеют степень 2.

3) Множество внутренних вершин частей графа С? состоит из всех вершин этого графа, имеющих степень 2.

Вернемся к случаю ¿-связного графа для произвольного ¿ и дадим определения разреза и частей разбиения графа разрезом.

Определение 12. Пусть (7 — ¿-связный граф.

1) Будем называть разрезом к-элементное разделяющее множество из вершин и рёбер графа С, содержащее хотя бы одно ребро. Множество всех разрезов графа (7 обозначим через Т(б).

2) Для разреза Т € обозначим через У{Т) множество всех входящих в Т вершин, а через Ш(Т) — множество, состоящее из всех вершин, входящих в разрез Т и всех вершин, инцидентных рёбрам разреза Т.

Разрез — объект, по свойствам похожий на вершинное разделяющее множество, но имеющий свою специфику. Для любого разреза Т € Т(С?) граф б — Т имеет две компоненты связности. Для каждого ребра е £ Т эти компоненты содержат по одному концу е.

Определение 13. 1) Пусть Т е Т(С), а [Д и Щ — компоненты связности графа — Т. Назовем множества А{ = Щ и V(T) частями разбиения графа С разрезом Т. Мы будем использовать обозначение

РаН(Т) = {АиА2}.

2) Границами разреза Т мы будем называть множества вершин

АХС\\¥(Т) и А2ПШ{Т).

Определение 14. Пусть 6 С £(<?).

Назовем частями разбиения графа б множеством разрезов & максимальные по включению множества вида

А = Р| А3, где Л5 е РаЛ(5).

5е6

Миожество всех частей разбиения графа G множеством разрезов © будем обозначать через Part(©).

3) Границей части А 6 Part(6) будет множество Bound(A) всех вершин этой части, являющихся вершинами разрезов из ©. Внутренностью части А будет множество Int(A) = А \ Вошк1(Л).

Определение 15. Разрезы S, Т е 1k(G) называются независимыми, если можно ввести такие обозначения

Part(S) = {Ль А2}, Part(Т) = {Ви В2},

что Ai Э В2 и В\ Э А2. Иначе мы будем называть разрезы S и Т зависимыми.

Определение 16. 1) Пусть © — множество, состоящее из попарно независимых разрезов графа G. Дерево разрезов множества © — это двудольный граф BT(G, ©): одну долю образуют разрезы из ©, а вторую — части из Part(ö), причем множество 5 S © и часть A G Part(6) смежны тогда и только тогда, когда А содержит одну из границ разреза S.

2) Если часть А Е Part(©) соответствует висячей вершине дерева BT(G, ©), то назовем такую часть крайней.

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

Теорема 1.7. Пусть G — k-связный граф, а © с T(G) — набор из попарно независимых разрезов, причем в © нет двух разрезов, содержащих одно и то же ребро. Тогда выполняются следующие утверждения.

1) Граф BT(G, ©) - дерево.

2) Любой разрез S 6 © смежен в BT(G, ©) ровно с двумя частями Part(6), причем эти две части содержатся в разных частях Part(S).

3) Разрез S g © отделяет вершину В от вершины С в BT(G, 6), если и только если S отделяет множество В от множества С в графе G.

4) Если крайняя часть А е Ра11(©) смежна в ВТ((3, ©) с разрезом Т, то А е РаЛ(Т).

5) Крайние части Рай(©) — это в точности минимальные по включению части среди всех частей разбиения графа С одним разрезом из множества ©.

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

Напомним, что все вершины ¿-связного графа имеют степень не менее к. Через мы обозначим множество всех вершин графа (7, имеющих степень к, пусть

Дирак в 1967 году и Пламмер в 1968 году исследовали минимальные двусвязные графы. Из результатов этих работ можно вывести, что ^г(С) > для минимального двусвязного графа С.

В 1979 году В. Мадер доказал результат, обобщающий написанное выше:

для минимального ¿-связного графа С. Эта оценка точная: для любого ¿ > 2 существуют бесконечные серии минимальных ¿-связных графов, для которых неравенство (1) обращается в равенство. Далее мы рассмотрим такие графы и будем называть их экстремальными минимальными ¿-связными графами.

Определение 17. Пусть ^г.аТ - дерево с Д(Т) < ¿ + 1. Граф Ск,т строится из к копий Ту,... дерева Т с непересекающимися множествами вершин. Для каждой вершины а е У(Т) обозначим через а* соответствующую вершину копии Т*. Если ¿с{а) = _7, то мы добавим к + 1 —j новых вершин степени к, смежных с {01,..., а*;}.

Очевидно, если v(T) = п, то v(Gк,т) = (2к — 1)п + 2. Несложно проверить, что Gk,r — минимальный ¿-связный граф и, следовательно, он — экстремальный. Одним из основных результатов диссертации является следующая теорема, в которой доказано, что других экстремальных минимальных ¿-связных графов нет.

Теорема 2.1. Любой экстремальный минимальный k-связный граф — это граф Gk,r для некоторого дерева Т с Д(Т) < к 4- 1.

В 1982 году Оксли представил алгоритм построения экстремальных минимальных двусвязных и трёхсвязных графов. Было доказано, что любой экстремальный минимальный двусвязный граф может быть получен из полного двудольного графа з несколькими операциями замены вершины степени 2 на граф K2t2, присоединенный к двум вершинам из окрестности заменяемой вершины. Аналогичное утверждение было доказано и для трёхсвязных графов. Из теоремы 2.1 несложно вывести аналогичный алгоритм построения всех минимальных fc-связных графов.

Следствие 2.3. Пусть G — экстремальный минимальный к-связный граф. Тогда G может быть получен из Кк,к+1 серией операций замены вершины степени к на полный двудольный граф Кк,к (в ходе операции добавляется паросочетание, соединяющее к вершин одной доли Кк k с вершинами, входящими в окрестность заменяемой вершины степени ¿).

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

v2(G) > ^-.

Определение 18. Через G A4 (п) обозначим множество всех минимальных двусвязных графов на п вершинах, в которых ровно T^f^l вершин степени 2.

Понятно, что равенство v2 (G) = V(GJ+4 может достигаться только при

у(С) = Зт+2. Из теоремы 2.1 следует, что множество5М(Зт+2) состоит из графов вида С2,т, где Т — дерево с ь(Т) = тп и Д(Т) < 3.

Оксли исследовал структуру минимальных двусвязных графов из 0М(п). Для п сравнимых с 0 и 1 по модулю 3 было доказано, что графы из 0М(п) можно получить несколькими операциями замены вершины степени 2 на граф К2$ из одного из начальных графов, перечисленных в работе. Начальные графы — это К3, три графа несколько более сложной структуры и две бесконечные серии графов. Мы дадим описание минимальных двусвязных графов из 0Л4(п) с помощью графов вида С2,т и стягивания рёбер.

Теорема 2.2. Пусть тп > 2. Тогда выполняются следующие утверждения.

1) ЯМ(Зт + 1) состоит из графов вида С2<т • ху, где Т — дерево с у{Т) — тп и А{Т) = 3,х,уе Уг{в2,т) ихуе Е(в2,т).

2) Для любого графа С £ 0Л4(Зт +1) представление в виде С2р • ху из пункта 1 единственно с точностью до изоморфизма.

Похожее, но несколько более сложное описание дано в диссертации и для графов из 0М(3т) при т > 2.

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

Теорема 2.4. Пусть к < 5, а (7 — минимальный к-связный граф. Тогда для каждого ребра е € Ек+1 можно выбрать содержащий е разрез 5е е так, что все выбранные разрезы попарно независимы.

К описанному в теореме 2.4 множеству попарно независимых разрезов можно применить конструкцию дерева разрезов и использовать многочисленные свойства, доказанные в теореме 1.7 и ее следствиях.

Для формулировки результата третьей главы нам потребуются гиперграфы. Для гиперграфа H мы будем применять такие же обозначения, как и для графа: множества вершин и гиперребер будем обозначать через V(H) и Е(Н), соответственно. Главное отличие гиперграфа от обычного графа в том, что гиперребро — это произвольное подмножество V(H), состоящее хотя бы из двух вершин. Поэтому удобно оперировать с гиперрёбрами как с множествами вершин графа.

Для множества вершин X С V(H) определим гиперграф H — X следующим образом: V{H — X) = V{H) \ X, а Е(Н — X) состоит из всех множеств вида R\X (где R S Е(Н)), содержащих хотя бы две вершины.

Определение 19. 1) Последовательность различных вершин а\а2 ... а^ называется путём, если существуют такие гиперребра ei, ег, - ejt-i, что а<, ai+1 е ej.

2) Если, кроме того, существует гиперребро е^ Э ait,ai, то последовательность ахаг ... ajt называется циклом

Определение 20. 1) Гиперграф называется связным, если любые две его вершины связаны, то есть, соединены путём.

2) Компоненты связности гиперграфа определяются так же, как и компоненты связности графа — это максимальные по включению множества попарно связанных вершин.

Определение 21. Гиперграф H называется гипердеревом, если он связен, ни одно его гиперребро не является подмножеством другого и для любого цикла в этом гиперграфе существует гиперребро, содержащее все его вершины.

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

Определение 22. Рассмотрим конечное множество вершин V. Пусть каждой вершине w е V соответствует разбиение Vw множества V \ {ю} на несколько классов (возможно, такой класс всего один).

Будем говорить, что вершина w разделяет вершины vi и ь2, если vi и v2 лежат в разных классах Vw.

Назовем вершины vi,v2 ё V соседними, если их не разделяет никакая отличная от них вершина множества V.

Построим гиперграф разбиения Struct(V) на вершинах множества V, гиперребра которого — это максимальные по включению множества попарно соседних вершин.

Приведем пример множества вершин и гиперграфа разбиения, показывающий, какое отношение имеет эта конструкция к теории связности. Пусть F — связный граф, 9ii(.F) — множество всех его точек сочленения, а для каждой точки сочленения а Е £Hi {F) классы разбиения (£Hi(F))„ состоят из точек сочленения, лежащих в одной компоненте связности графа F — а.

Нетрудно понять, что гиперребра Struct(9ti(F)) — это множества всех точек сочленения, лежащих в каком-либо некрайнем блоке. Можно проверить, что гиперграф Struct(Dii(F)) является гипердеревом. Именно классическая структура взаимного расположения точек сочленения связного графа подсказывает нам результат теоремы 3.2.

Теорема 3.2. Пусть для любых a,b,c € V если а разделяет Ь и с, то b не разделяет а и с. Тогда выполняются следующие утверждения.

1) Гиперграф Struct(Vr) является гипердеревом.

2) Пусть для некоторой вершины a G V гиперграф Struct(V) —а распадается на. компоненты связности W\,..., Wt. Тогда Va = {W\,..., We}.

Отметим, что с помощью теоремы 3.2 можно доказать приведенные в главе 1 диссертации результаты о структурных деревьях (теоремы 1.1 и 1.7): достаточно проверить для множества рассматриваемых объектов

(попарио независимых разделяющих множеств или разрезов) условие из теоремы 3.2, после чего можно перейти от гипердерева к дереву с помощью конструкции, описанной в теореме 3.1. Мы дали в этих теоремах более элементарные доказательства. Однако, иногда обойтись без теоремы 3.2 гораздо сложнее — например, в случае компонент зависимости, о которых идет речь в четвертой главе диссертации.

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

Определение 23. Пусть G — fc-связный граф, а 6 С iHfc(G).

1) Граф зависимости Dep(©) набора © — это граф, вершины которого соответствуют множествам набора, а две вершины смежны тогда и только тогда, когда соответствующие им множества зависимы.

2) Компонентой зависимости набора © называется любой набор Тс©, состоящий из всех множеств, соответствующих вершинам одной из компонент связности графа зависимости Dep(©).

3) Через Сотр(©) обозначается множество всех компонент зависимости набора ©.

В четвертой главе изучается взаимное расположение компонент зависимости набора 6.

Доказывается, что для любых двух различных компонент зависимости 1,1' е Сотр(©) существует единственная часть А € Part(1), которая содержит все множества компоненты 1', а любая отличная от А часть Part(1) не содержит ни одного множества из 1'.

Каждой компоненте зависимости 1 € Сошр(©) соответствует разбиение остальных компонент зависимости на классы: каждый класс образуют компоненты зависимости, содержащиеся в одной из частей Part(1).

Гиперграф Struct(Comp(©)) описанного выше разбиения называется гиперграфом компонент зависимости набора © и обозначается через

Struct(S).

Теорема 4.1. Пусть G — к-связный граф, а <5 С 9lk(G). Тогда выполняются следующие утверждения.

1) Гиперграф компонент зависимости Struct(6) является гипердеревом.

2) Пусть Т G Comp(S), а С\,... ,Сп — компоненты связности гиперграфа Struct(S) —Т. Тогда компоненты зависимости из множестваCi содержатся в одной части € Part(íT), причем Bi ф Bj при i ф j.

3) Пусть Т G Comp(S), а часть A G Part(T) содержит хотя бы одно множество из ©\Т. Тогда существует единственное гиперребро гиперграфа Struct((5), вершинами которого являются Т и несколько (быть может, одна) компонент зависимости, лежащих в части А.

Мы имеем дело с более общей ситуацией, чем в первой главе: там рассматривался набор из попарно независимых множеств, а значит, его компонентами зависимости были сами множества. Поэтому в рассматриваемой задаче возникает больше технических трудностей при изучении частей Part(S) с помощью гипердерева Struct(S).

Определение 24. Пусть R - {©!,...©„} — гиперребро Struct(©). Для всех i € {1,... ,п} пусть А{ е Part(6¿) — часть, содержащая множества всех остальных компонент зависимости из R. Тогда множество вершин

л = Пд

¿=i

назовем частью, соответствующей гиперребру R (даже в случае, когда А £ Part(©)).

Именно из-за того, что не каждому гиперребру Struct(©) соответствует часть Part(6), не получается ввести на компонентах зависимости и частях Part(S) структуру дерева, как в случае с набором из попарно независимых множеств. В диссертации доказано, что часть Л, соответствующая гиперребру R гипердерева Struct(S), не принадлежит Part(S) только

в одном случае: А € © и гиперребро R состоит ровно из двух компонент зависимости, одна из которых — это {Л}, а другая компонента зависимости имеет часть разбиения с границей А. Следующая теорема описывает части Part(S) с помощью гипердерева Struct(©).

Теорема 4.2. Пусть G — к-связный граф, © с ü\k(G). Тогда выполняются следующие утверждения.

1) Пусть ©' G Сотр(©) и часть А е Part(S') таковы, что А не содержит множеств из © \ ©'. Тогда А £ Part(©).

2) Пусть Н (Е Part(©). Тогда либо часть Н соответствует некоторому гиперребру R гипердерева Struct(©), либо существует такая компонента зависимости 6' G Сотр(©), что Н € Part(6').

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

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

Теорема 5.1. Пусть G — двусвязный граф, а IV — множество, состоящее из внутренних вершин непустых частей-блоков графа G и содержащее не более чем по одной вершине из каждого блока. Тогда граф G — W двусвязен.

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

Определение 25. Пусть S g 9\k{G), а Н — компонента связности графа G — S. Мы будем называть Н фрагментом.

Определение 26. Пусть G — fc-связный граф, А € Part(ÍHj¿(G)). Пусть Int(A) ф 0. Назовем множество S 6 £Hjt(G) существенным для части А, если не существует множества Т G ÍH/b(G), отделяющего S от Int(A).

Обозначим через Вошк^Л) множество всех граничных вершин части А, входящих в два и более существенных для части А множества. Назовем часть А хорошей, если |1^(Л)| > |Вошн12(Л)|.

Теорема 5.2. Пусть б — к-связпый граф, причем степень любой вершины, входящий в одно из множеств не менее 2к — 1, а любой фрагмент имеет хотя бы вершин. Тогда существует множество IV, содержащее по одной внутренней вершине каждой хорошей части Раг1(ЕН;ь((?)), такое, что для любого V/' С IV граф (7 — IV' является к-связным.

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

Определение 27. Для связного графа С обозначим через максимально возможное количество висячих вершин в остовном дереве графа б.

Если Р — дерево, то нетрудно понять, что и{Р) — количество его листьев.

Пусть б — связный граф. С 1981 года, когда Дж. Сторер предположил, что и(С}) > если все вершины графа (7 имеют степень 3, было опубликовано немало работ о нижних оценках В 1981 году Н. Линиал высказал гипотезу:

и(С?) > + с при 6(в) >й> 3,

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

В 1991 году Д. Клейтман и Д. Вест доказали, что и((3) > | • у(С) + 2 при ¿(¿7) > 3 и

"(С) > \ ■ + | при ¿(в) > 4. (2)

о о

В 1992 году Дж. Григгс и М. Ву еще раз доказали оценку (2) и доказали, что и(С) > ^ • у(С) + 2 при ¿((3) > 5. В обеих работах применялся метод мёртвых вершин, который будет применен и в некоторых доказательствах шестой главы.

С развитием этого метода для ё>6 есть значительные проблемы, дальнейших результатов на настоящий момент нет. Из работ Алона и других следует, что для достаточно больших в, гипотеза Линиала неверна. Однако, для малых значений ¿>5 вопрос остается открытым.

В работе Клейтмана и Веста сказано о еще одной, более сильной гипотезе Линиала:

хеУ(в) '

для связного графа С с 5(О) > 2. Понятно, что раз для больших степеней неверна более слабая гипотеза, то неверна и эта. Однако, она стимулирует попытки получить оценку на и{С), в которую каждая вершина вносит вклад, зависящий от ее степени.

В работе [6] диссертант доказал следующую теорему, с которой начинается шестая глава диссертации.

Теорема 6.1. Пусть С — связный граф с более чем одной вершиной, в — количество его вершин степени 3, а £ — количество его вершин степени не менее 4. Тогда

2 1 8

и(С) = —4 + —я + а, где а > -. 5 5 5

Более того, а > 2, кроме трёх графов-исключений: С\, С| (квадраты циклов на 6 и 8 вершинах) и регулярного графа степени 4 на 8 вершинах, изображенного на рисунке.

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

Клейтман и Вест в 1992 году предположили, что в неравенстве (2) аддитивную константу | можно заменить на 2 для всех графов, кроме двух исключений: это С| и С| (квадраты циклов на 6 и 8 вершинах). Однако, было доказано лишь, что граф-исключение должен быть регулярным графом степени 4, каждое ребро которого входит в треугольник. Из результатов диссертации следует, что на самом деле для задачи, исследованной Клейтманом и Вестом, равно как и для более общей задачи, исследованной в теореме 6.1, исключений три (см. рисунок). Отметим, что в теореме 6.1 допускается наличие в графе вершин степеней 1 и 2. Однако, эти вершины не учитываются в оценке на и(С).

В работе [5] диссертант доказал оценку на «((3), учитывающую вершины степени 1.

Теорема 6.2. Пусть С? — связный граф с более чем одной вершиной, в — количество его вершин степеней 1 и 3, а £ — количество его вершин степени не менее 4. Тогда

«(о >!«+£-+§.

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

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

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

Определение 28. Обозначим через ¿{С) количество вершин в максимальной цепочке последовательно соединённых вершин степени 2 в графе б.

Отметим, что наличие в графе С длинных цепочек из последовательно соединённых вершин степени 2 может сделать величину «(С) сколь угодно близкой к 0: не более чем две вершины из каждой такой цепочки могут быть висячими в остовном дереве графа. Поэтому возникает естественное ограничение на граф: нужно ограничить сверху ¿(С). В работе [4] диссертант доказал следующую теорему, включенную в диссертацию.

Теорема 6.3. Пусть <3 - связный граф, у{С1) > 2, £((3) < к, к > 1. Тогда

В конце главы б построены бесконечные серии примеров, подтверждающие точность оценки из теоремы 6.3.

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

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

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

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

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

Публикации автора по теме диссертации

[1] Д. В. КАРПОВ. Остовпос дерево с большим количеством висячих вершин. Дискретная математика, т. 13, в.1 (2001), стр.63-72.

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

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

[4] Д. В. КАРПОВ. Остовное дерево с большим количеством висячих вершин. Записки научных семинаров ПОМИ т. 381 (2010) стр. 78-87.

[5] Д. В. КАРПОВ. Остовные деревья с большим количеством висячих вершин: новые нижние оценки через количество вершин степеней 3 и не менее 4. Записки научных семинаров ПОМИ, т. 406 (2012), стр. 31-66.

[6] Д. В. КАРПОВ. Остовные деревья с большим количеством висячих вершин: ниэюние оценки через количество вершин степеней1, 3 и не менее 4. Записки научных семинаров ПОМИ, т. 406 (2012), стр. 67-94.

[7] Д. В. КАРПОВ. Дерево разбиения двусвязного графа. Записки научных семинаров ПОМИ, т. 417 (2013), стр. 86-105.

[8] Д. В. КАРПОВ. Минимальные двусвязпые графы. Записки научных семинаров ПОМИ, т.417 (2013), стр. 106-127.

[9] Д. В. КАРПОВ. Дерево разрезов и минимальный к-связный граф. Записки научных семинаров ПОМИ, т.427 (2014), стр. 22-40.

[10] Д. В. КАРПОВ. Минимальные к-связные графы с минимальным числом вершин степени к. Записки научных семинаров ПОМИ, т. 427 (2014), стр.41-65.

[11] д. в. карпов. Удаление вершин из двусвязного графа с сохранением двусвязности. Записки научных семинаров ПОМИ, т. 427 (2014), стр. 66-73.

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

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

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