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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

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

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

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

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

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

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

Научный руководитель

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

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

член-корреспондент РАН доктор физико-математических наук Матиясевич Юрий Владимирович доктор физико-математических наук Дольников Владимир Леонидович кандидат физико-математических наук Пономаренко Илья Николаевич Нижегородский государственный университет им. Н.И.Лобачевского

Защита диссертации состоится года

в час. на заседании Диссертационного совета Д 212.232.29

по защите диссертаций на соискание учёной степени доктора наук при Санкт-Петербургском государственном университете (198504, Сапкх-Петербург, Схарый Петергоф, Университетский пр.. 28, матема-тико-механический факультет Санкт-Петербургского государственного университета).

С диссертацией можно ознакомиться в научной библиотеке Санкт-Петербургского государственного универсихеха но адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Защита состоится по адресу: Санкт-Петербург, наб. р. Фонтанки, 27, Санкх-Пехербур1ское охделение Математическою инсхихуха им. В. А.Стеклова РАН, комната ЗИ.

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

Л1,

" МА+Я. 20(^года.

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

доктор физико-математических наук В. М. Нежинский

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

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

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

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

Многими исследователями делались попьаки обобщить эти конструкции на разбиение ^связного графа его ^разделяющими множествами. В 1966 году W. Т. Tutte подробно описал конструкцию разбиения двусвязного графа его 2-разделяютцими множествами. Эга структура является естественным обобщением структуры блоков и точек сочленения для двусвязного графа и также отображается с помощью дерева. В

1992 году W. Hohberg предложил обобщи " а случай

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

F. Harary, Y. Kodaina (1964) и D. W. Matula (1978) предлагали называть fc-блоком или k-компонентой графа G максимальный по включению fc-связный подграф этого графа. При очевидной аналогии в определении с блоками связного графа, свойства вводимых таким образом fc-блоков имеют мало аналогий со свойствами классических двусвязных блоков.

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

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

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

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

2. Для произвольного набора 6, состоящего из k-разделяющих множеств fc-связного графа G, рассматривается граф зависимости D(&),

вершины которого соответствуют множествам набора 6 и две вершины смежны тогда и только тогда, когда соответствующие множества зависимы, то есть разделяют друг друга. Набор & разбивается на компоненты зависимости — поднаборы, соответсвующие компонентам связности графа зависимости Б(6). Доказано, что существует дерево компонент зависимости вершины которого соответствуют частям разбиения графа G набором <3 и компонентам зависимости набора &, причем каждая часть А разбиения графа G набором 6 является частью разбиения графа G набором из множеств, входящих только в те компоненты зависимости набора 6, которые смежны части Л в дереве Се-

3. Разработана новая методика изучения структуры разбиения к-связного графа теория ромашек. Изучение разбиения к;-связного графа произвольным набором к-разделяющих множеств сводится к изучению разбиения этого графа набором, образующим ромашку (разбиение графа таким набором имеет достаточно простую циклическую структуру). Доказано, что каждая часть разбиения Ге-связиого графа G набором & -разделяющих множеств 6 содержит хотя бы k вершин тогда и только тогда, когда каждая компонента зависимости набора образует ромашку. На языке теории ромашек дано описание структуры разбиения двусвязного графа произвольным набором его 2-разделяющих множеств.

4. С помощью теории ромашек дано детальное описание структуры Ге-разделяющих множеств в слабо нерасщепимом к-связном графе.

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

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

крываег перспективы для изучения свойств графов этого класса.

Апробация работы. Результаты диссертации докладывались на семинаре по дискретной матемашке ПОМИ РАН и на Восьмом Международном семинаре "Дискретная математика и ее приложения" (Москва, МГУ, 2004).

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

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

СОДЕРЖАНИЕ РАБОТЫ Диссертация посвящена изучению свойств к-разделяющих множеств в &-связных графах и частей, на которые наборы таких множеств делят &-евязный граф. (В диссертации рассматриваются конечные неориентированные графы без петель и кратных ребер.)

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

Определение 1. Пусть Я,Х С при $ Е.у д е м говорить,

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

Для произвольного к-связного графа О обозначим через на-

бор из всех разделяющих множеств этого графа, а через — набор

из всех его к-разделяюших множеств.

Определение 2. Пусть

1) Часть разбиения графа G набором & (или часть <5 -разбиения) — это максимальное по включению множество .4 С V{G) такое, что никакое множесшо S £ © не разделяет Л. Будем обозначать через Р(б) множество из всех частей б-разбиения.

Для любого множества S G будем обозначать через P(S)

множество всех частей (Sj-разбиеиия.

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

3) Часть А Е Р{&) назовем вырожденной, если она содержится в одном из разделяющих множеств набора и невырожденной в противном случае.

В первой главе доказываются простейшие свойства частей разбиения fc-сиязпого графа набором его fc-раздсляющих множеств. В теореме 1.1 показано, что для любого набора разделяющих множеств графа G разбиение состоит из максимальных по включению множеств вида В теореме 1.2 показано, что в fc-связном 1рафе Gдля любого набора 6 С граница любой части A G -Р(б) есть множество всех вершин части Л, имеющих смежные вершины не из Л. Это утверждение дает определение границы части, в котором не фигурируе1 набор б. Такое определение имеет большое значение, так как одно и то же множество вершин л-связного графа G может быть частью разбиения этого графа различными наборами его fc-разделяющих множеств.

Блок /г-связного графа G определяется в диссертации как максимальное по включению подмножество множества V{G) такое, что для разделения любых двух вершин этою подмножества нужно удалить из

графа хотя бы к вершин. Определенные таким образом блоки fc-связного графа G являются частями разбиения этого графа набором В

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

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

Определение 3. 1) Назовем разделяющие множества S и Т независимыми, если S не разделяет Т и Г не разделяет S. В противном случае мы назовем эти множества зависимыми.

2) Пусть (3 С 5Hfc(G). Граф зависимости этого н а б — это граф, вершины которого соответствуют множествам набора, а две вершины смежны тогда и только тогда, когда соответствующие им множества зависимы.

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

Во второй главе показывается, что структуру компонент зависимости набора & С можно описать с помощью графа компонента зависимости Вершины эюго графа соответствуют компонентам зависимости набора и невырожденным частям (5-разбиения. Пусть 6i,...,©m — все компоненты зависимости набора 6, a Ai,...,A„ — все невырожденные части в .Р(©). Вершина, соответствующая компоненте зависимости ©,-, смежна в графе G& с вершиной, соответствующей части тогда и только тогда, когда никакое множество набора ©\©i по отделяет часть Л,- от объединения всех множеств из &j. Компоненты зависимости и смежны в графе G& тогда и только тогда, когда 6,- = {5}, причем S граница одной из

частей или наоборот.

Теорема 1. Для произвольного к-связного графа G и любого набора в С граф является деревом. Если невырожденная часть А С -Р(б) смежна в графе С?е с компонентами зависимости <5ь...,&т и только с ними, то Л £ Р(и™! ©,•). Более того, существуют такие часми

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

Определение 4. 1) Пусть Р = ... — набор множеств вер-

шин Ге-евязпого графа О, удовлетворяющий следующим условиям.

1° Для всех г £ {1,... ,тп} выполняются соотношения Р П = 0 и = ■Цт"'- Ни одно из множеств не содержится в объединении опальных множеств набора.

2° Существует набор © С 9^(6) такой, что граф зависимости .0(6) связен, а каждое множество представляется в виде

для различных Для каждой существу-

ет такое, чю

3° Множества набора 6 не разделяют ни одно из мно-

жест

Будем называть набор F квазиромашкой, множество Р ее центром, а множества ,<?,„ лепестками этой квазиромагакп. Все множества вида = Qi \jQjU Р мы будем называть множествеши квазиромашки F. Будем говори 1Ь, чю набор в образует квазиромашку Г.

2) Если, кроме того, для любых выполняет-

ся Qi П — 0, ю будем называхь набор F ромашкой.

Теорема 2. Пусть G А:-евязныЙ1раф,анабор © С образу-

ет квазиромашку F с центром Р и лепестками (¿х,..., <5т. Тогда лепестки квазиромашки F можно циклически пронумеровать таким образом, что Р{&) = {С112,С2.з,...,Ст,1}, 1дс Л(С(,1+1) = <5,-,>+1 для всех i. (Здесь и далее мы считаем, что = (¡>1.)

Из теоремы 2 следует, что если два разных набора образуют квазиромашки с одним центром и одним и тем же набором лепестков, то разбиения графа О этими наборами совпадают. Таким образом, можно говорить о разбиении Ге-связного графа квазиромашкой. Подробное описание свойств разбиения Ге-сиязпого грифа квазиромашкой приведено в разделе 3.1 диссертации (теоремы 3.1 и 3.2).

Отметим, что при малых значениях к легко описать все возможные виды ромашек в Ге-связном графе. Так в двусвязном графе центр любой ромашки пуст, а каждый лепесток еотоит из одной вершины. Таким образом, ромашка в двусвязном графе представляет собой "цикл", в котором любые две соседние вершины являются границей части разбиения графа этой ромашкой, а две несоседние вершины образуют разделяющее множество, которое разбивает граф на две части так, как соответствующая им хорда разбивает цикл. Такая конструкция играет важную роль п изучении структуры двуевязного графа (^Т.ТиИе, 1966). В трехсвяз-ном графе у любой ромашки и центр, и каждый лепесток еотоит из одной вершины. Таким образом, ромашка в трехсвязном графе представляет собой "колесо", и котором любые две соседние вершины вместе с центром являются границей части разбиения графа этой ромашкой, а две несоседние вершины вместе с центром представляют собой разделяющее множество.

В разделе 3.2 диссертации доказывается следующая теорема.

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

1° Каждая часть 6-разбиения содержит хотя бы к вершин.

2° Каждая компонента зависимости набора €5 либо состоит ровно

из одного множества, либо образует ромашку.

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

В четвертой главе рассматривается класс слабо нерасщепимых графов.

Определение 5. Будем называть k-связный граф G слабо нерасщепи-мым, если в графе G нет множеств S,T Е 9ti(G) таких, что для одной из частей выполняется

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

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

Пусть G — слабо нерасщепимый &-связный граф, a N(0) — множество всех невырожденных блоков графа О, содержащих хотя бы по к вершин. Так как блоки являются частями £Н* (С)-разбиения графа О, хо каждое множество 5 6 делит N(0) на группы блоков, лежащих

в одной части из Р(5). Будем считать множества 5 и Т эквивалентными, если они лежат в одной компоненте зависимости набора и делят N(0) на одинаковые группы. Таким образом, все ^разделяющие множества графа О оказываются разбиты на классы эквивалентности. Эти классы являются удобным инструментом для изучения структуры &-разделяющих множеств слабо нерасщепимого &-связного графа.

Определяются понятия зависимых и независимых классов, обо-щаюшие понятия зависимых и независимых А:-разделяющих множеств (определения приведены в начале пятой главы). Строится граф зависимости классов, вершины которого соответствуют классам множеств, и две вершины смежны тогда и только тогда, когда соответствующие классы зависимы. Набор из множеств всех классов, входящих в одну компоненту связности графа зависимости классов, называется комплексом. Комплекс называется большим, если он состоит из множеств более чем одного класса, и малым в противном случае. В следующих двух теоремах описывается структура множеств, входящих в один комплекс.

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

удовлетворяющие следующим условиям.

1° Часть Л содержит все множества из К.. Любое отличное от Т\ и множество принадлежит комплексу

2° Часть Л не содержит ни одного блока из ЩО). 3° Если степени всех вершин графа О не менее , то А = ДиТг-Теорема 5. Пусть О слабо нерасщепимый Рг-связный граф, а — большой комплекс графа О. Тогда существует квазиро-

машка F с центром Р и циклически упорядоченными лепестками Li,Ri,L,2,R2,... ,Lm,fím (возможно, L¡ = fí¡ при некоторых г), удовлетворяющая следующим условиям.

1° Любая часть из P(F) с границей L¡Ui?,-UP пуста и не содержит ни одного блока из N(G).

2° Любая часть из P(F) с границей i?,-U U Р содержит хотя бы один блок из N(G).

3° Для любого множества S € О существуют i и j такие, что

Подробно описание структуры множеств комплекса дано в пятой главе (теоремы 5.2-5.5).

Таким образом, в слабо нерасщеиимом fc-связном графе G каждая компонента зависимости набора оказывается разбита на комплек-

сы. В теореме 5.6 доказывается, что взаимное расположение комплексов и блоков слабо иераещенимого fc-связпою ipacpa G отображается с помощью дерева, структура которого аналогична дереву компонент зависимости набора л-разделяющих множеств.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Д. D. КАРПОВ, А. В. ПАСТОР. О структуре k-связного графа. // Записки научных семинаров ПОМИ, 266, 2000, стр. 76-106.

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

[3] Д. В. КАРПОВ. Зависимые разделяющие множества в к-связном графе. // ПОМИ ПРЕПРИНТ 12-2003. Электронный адрес: http: //www. pdrai. ras. ru/preprint/2003/03-12. html

[4] Д. В. КАРПОВ. Структура разбиения слабо нерасшепимого k-связ-ного графа. // ПОМИ ПРЕПРИНТ 18-2003. Электронный адрес: http: //www. pdmi. газ. ru/preprint/2003/03-18. html

ЛР№ 040815 от 22.05.97.

Подписано к печати 13.04.2004 г. Формат бумаги 60X84 1/16. Бумага офсетная. Печать ризографическая. Объем 1 п.л. Тираж 100 экз. Заказ 3229. Отпечатано в отделе оперативной полифафии НИИХ СПбГУ с оригинал-макета заказчика. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26.

Ш 1 О 4 2 2

Введение

Связность

Блоки в ¿-связном графе. Структура разбиения ¿-связного графа

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

Разделяющие множества и части разбиения.

Блоки ¿-связного графа.

Зависимые и независимые множества. Компоненты зависимости .■.

Ромашки.

Слабо нерасщепимые графы.

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

1 Основные понятия

1.1. Части разбиения.

1.1.1. Представление части разбиения в виде пересечения

1.1.2. Граница и внутренность.*.

1.1.3. Блоки.

1.2. Зависимые и независимые разделяющие множества

1.2.1. Независимые разделяющие множества.

1.2.2. Разбиение ¿-связного графа парой зависимых ¿-разделяющих множеств

1.3. Свойства правильных частей разбиения.

2 Компоненты зависимости набора разделяющих множеств

2.1. Пополнение и замыкание набора разделяющих множеств

2.2. Компоненты зависимости набора разделяющих множеств

2.3. Новые свойства пополнения и замыкания набора разделяющих множеств.

2.4. Разбиение графа набором из попарно независимых множеств

2.5. Процесс разбиения ^-связного графа.

3 Ромашки и квазиромашки

3.1. Циклический порядок лепестков квазиромашки.

3.2. Разбиения без малых частей.

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

4 Слабо нерасщепимые графы. Основные свойства

5 Структура разбиения слабо нерасщепимого ¿¡-связного графа

5.1. Классы /^-разделяющих множеств.

5.2. Доминирующие множества. Границы и внутренняя область класса.

5.3. Множества независимого класса.

5.4. Множества большого комплекса.

5.5. Разбиения графа комплексами.

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

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

Связность

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

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

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

Начало исследований свойств вершинной связности графа положил в 1927 году K.Menger [27], доказавший следующую теорему: для любых двух несмежных вершин ж, у связность ка(х,у) равняется набольшему количеству непересекающихся простых путей между х и у в графе С.

С 60-х годов XX века активно проводились исследования по вершинной связности графов. Многих исследователей интересовали вопросы о сохранении ¿-связности графа при удалении его вершин и ребер и об описании критических и минимальных к-связных графов (то есть, к-связных графов, перестающих быть ¿-связными при удалении любой вершины или любого ребра соответственно). Наиболее сильные результаты по минимальным ¿-связным графам получили Я. НаПп [12, 13, 14, 15] и \У.Мас1ег [22, 23, 24, 25]. В работах [11, 22, 32, 16, 7] изучались критические ¿-связные графы и вопросы о том, при каких условиях в ¿-связном графе существует вершина, удаление которой не нарушает ¿-связность графа, и какие вершины данного графа удовлетворяют этому свойству.

Еще одно направление, в котором активно проводились исследования по вершинной связности — это построение редукционных теорий, позволяющих при помощи последовательности таких операций, как удаление и стягивание ребер, свести произвольный ¿-связный граф к ¿-связному графу достаточно простой структуры (при этом все промежуточные графы, возникающие на данной последовательности операций, также должны быть ¿-связными). Классическим примером такой теории является теория Татта [30, 9, 31], утверждающая, что из любого трехсвязного графа при помощи удаления и стягивания ребер можно получить колесо — граф, состоящий из простого цикла и вершины, смежной со всеми вершинами этого цикла. Аналогичные теории для к = 2 и к — 4 описаны в работах [18] и [28] соответственно. Вопрос о возможности построения подобной теории для произвольного к обсуждается в работе [29].

Блоки в А;-связном графе. Структура разбиения к-связного графа

Еще одно направление исследований по вершинной связности — это исследование структуры разбиения ¿-связных графов минимальными по количеству вершин разделяющими множествами. Интерес к этому направлению объясняется тем, что важную роль в изучении свойств связных графов играют блоки, точки сочленения и их структура. Блоком связного графа С? называется его максимальный по включению дву-связный подграф, а точкой сочленения — вершина, удаление которой Делает граф несвязным. Структуру блоков и точек сочленения связного графа отображает дерево блоков и точек сочленения ([10, глава 4]). Вершины этого дерева соответствуют блокам и точкам сочленения связного графа С, а ребра соединяют любой блок с содержащимися в нем точками сочленения. Таким образом, можно говорить о разбиении связного графа на блоки. Подробно структура и свойства блоков и точек сочленения связного графа описана в [2, 10]. В [10] можно найти примеры использования этой структуры, причем не только в теории связности.

Конструкция разбиения графа на блоки полезна для описания структуры связности графа. Так, все вершины, при удалении которых граф остается связным — это внутренние вершины блоков (то есть, вершины, не являющиеся точками сочленения). Более того, при одновременном удалении нескольких внутренних вершин разных блоков граф остается связным. Это обстоятельство, в частности, позволяет построить в связном графе, степени всех вершин которого не менее трех, остовное дерево с большим количеством висячих вершин [3].

В связи с важностью теории блоков и точек сочленения для изучения свойств связных графов неоднократно предпринимались попытки обобщить эту теорию на случай ¿-связных графов. Авторы ряда работ (например, [17], [10] и [26]) предлагали называть ¿-блоком или ¿-компонентой графа максимальный по включению ¿-связный подграф графа О. При очевидной аналогии в определении с блоками связного графа, свойства вводимых таким образом ¿-блоков имеют мало аналогий со свойствами классических двусвязных блоков связного графа.

Более перспективным оказался другой подход к определению блока ¿-связного графа, также имеющий аналогию с классическими двухсвязными блоками связного графа. Рассмотрим процесс последовательного разбиения связного графа (7 его точками сочленения. Пусть V — точка сочленения графа С?, а С15., Сп — компоненты связности графа (7 — V. Пусть граф получен из добавлением вершины V и всех выходящих из нее к вершинам графа С{ ребер графа Тогда графы . оказываются связными, все их точки сочленения являются точками сочленения графа (? и, наоборот, любая точка сочленения графа О является точкой сочленения одного из полученных графов. Продолжим процесс разбиения до тех пор, пока все полученные графы не окажутся двусвязными. В [2, 10] доказано, что вне зависимости от порядка операций мы получим разбиение графа (? на блоки. При таком определении блоков сразу же видно, что структуру их взаимного расположения отображает дерево.

Первую попытку предложить похожую конструкцию для описания разбиения двусвязного графа на блоки сделал Б. МасЪапе [21] в 1937 году. В 1966 году Т. Тиие [31] подробно описал конструкцию разбиения двусвязного графа его 2-разделяющими множествами (то есть, множествами из двух вершин, удаление которых делает граф несвязным). Эта конструкция является естественным обобщением для двусвязного графа алгоритмического подхода к определению классического блока. Основное отличие шага процесса разбиения двусвязного графа [31] от шага процесса построения классических блоков состоит в том, что после "разреза" двусвязного графа по некоторому его 2-разделяющему множеству к каждому из образовавшихся подграфов (порожденному вершинами одной из компонент связности, образовавшейся при удалении 2-разделяющего множества, и вершинами самого 2-разделяющего множества) добавляется так называемое виртуальное ребро, соединяющее вершины данного 2-разделяющего множества. Процесс продолжается до тех пор, пока все полученные графы не окажутся трехсвязными. Данная конструкция дает просто описываемый процесс разбиения двусвязного графа на блоки, что позволяет построить дерево, являющееся естественным обобщением для двусвязного графа понятия дерева блоков связного графа. Детальное описание данной конструкции можно также найти в работах [20] и [9].

Однако, долгое время не было попыток обобщить понятие блоков на к-связные графы при к > 2 и построить структуру разбиения ¿-связного графа его ¿-разделяющими множествами. В 1992 году W.Hohberg в работе [19] предложил обобщение описанной выше конструкции последовательного разбиения графа на случай ¿-связного графа для произвольного к. В работе [19] содержится ряд полезных свойств разделяющих множеств графов. Основным недостатком предложенной в [19] конструкции является то, что получаемые в результате блоки сильно зависят от процесса разбиения и, тем более, нельзя говорить о единственности структуры разбиения.

Диссертант и А. В. Пастор в работе [7] рассмотрели класс слабо не-расщепимых ¿-связных графов (этот класс является достаточно большим: в него входят все ¿-связные графы, степени вершин которых не менее ^р). Разбиение слабо нерасщепимого ¿-связного графа на блоки, также определяемые как результат процесса последовательных разрезов графа по ¿-разделяющим множествам, оказывается в некотором смысле единственным: между блоками, получающимися в результате различных способов разбиения, можно установить взаимно однозначное соответствие так, что соответствующие блоки будут изоморфны, а множества их внутренних (то есть, не входящих в ¿-разделяющие множества) вершин будут совпадать.

В настоящей диссертации мы используем другой подход к определению блоков в ¿-связном графе, впервые предложенный диссертантом в работе [4]. Блок ¿-связного графа G определяется, как максимальное по включению подмножество множества У{р) такое, что вершинная связность любых двух из этих вершин не менее к + 1. Отметим, что при данном определении блок — это не граф, а множество вершин. Такое определение намного проще алгоритмического определения блока и, на первый взгляд, больше похоже на подход к определению блока из [17, 26, 10]. Более того, наш блок является объединением множеств вершин нескольких максимальных по включению ¿-связных подграфов графа С?, которые предлагалось рассматривать в качестве блока в этих работах. Однако, в главе 2 диссертации показана связь между нашими блоками и процессом последовательного разбиения графа его ¿-разделяющими множествами. Новый подход значительно упрощает работу с блоками ¿-связного графа.

Результаты диссертапди Обозначения

Пусть G — произвольный граф. Для IV С V(О) через О — \У мы будем обозначать граф, который получается при удалении из бг всех вершин множества Ц? и всех выходящих из них ребер. Для Е С Е{0) через Сг — Р мы будем обозначать граф, который получается при удалении из О всех ребер множества Е (то есть, G — F = (У(С?), Е(0)\Е)). Через 8 (О) мы будем обозначать минимальную степень вершины графа С.

Разделяющие множества и части разбиения

Определение 1. Пусть С — произвольный граф. Назовем множество II С У(Сг) разделяющим множеством графа (2, если граф С? — К несвязен. В случаях, когда необходимо указать количество элементов

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

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

В ¿-связном графе нет разделяющих множеств, состоящих менее, чем из ¿ вершин. Обозначим через 1Н(Ст) набор из всех разделяющих множеств ¿-связного графа С, а через (С?) — набор из всех его ¿-разделяющих множеств.

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

2) Пусть II, ТУ С У(С). Будем говорить, что множество Я отделяет множество II от множества И^, если и <£ Я: IV <£ Я и никакие две вершины и Е 11\Я я т £}¥\Я не лежат в одной компоненте связности графа О — Я.

Определение 3. Пусть <5 С Ш((7).

1) Часть разбиения графа набором (3 (или часть &-разбиения) — это максимальное по включению множество А С У{0) такое, что никакое множество 5 6 © не разделяет А. Будем обозначать через Р(&) множество из всех частей ©-разбиения. Если набор & сотоит из одного множества 5, то будем обозначать множество всех частей {¿^-разбиения через Р(5).

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

3) Часть А Е Р{&) назовем вырожденной, если она содержится в одном из разделяющих множеств набора и невырожденной в противном случае.

Диссертация посвящена изучению ¿-разделяющих множеств в ¿-связном графе и частей разбиения ¿-связного графа наборами его ¿-разделяющих множеств. В теореме 1.1 показано, что для любого набора разделяющих множеств <5 = {£1,., 5П} графа (7 разбиение Р(&) состоит из максимальных по включению множеств вида П"=1 Аг, где Д- € Нетрудно понять, что для любого множества 5 6 £Я(0) количество частей в Р(5) равно количеству компонент связности графа С — 5. Для любой части А 6 Р(3) ее внутренность 1(А) есть множество вершин одной из компонент связности графа С - а Д(А) =

В теореме 1.3 показано, что в ¿-связном графе (7 для любого набора © С граница любой части А € Р{&) есть множество всех вершин части А, имеющих смежные вершины не из А. Это утверждение дает определение границы части, в котором не фигурирует набор (5. Одно и то же множество вершин А может быть частью разбиения ¿-связного графа <2 различными наборами ¿-разделяющих множеств, этого графа, но в силу чказанного выше граница и внутренность А, как части любого из этих разбиений, одна и та же. Так как А = Л (А) и 1(А), то внутренность части А есть множество всех ее вершин, не смежных с вершинами не из А. Следовательно, граница Я(А) отделяет внутренность 1(А) от множества У(С) \ А.

Блоки ¿-связного графа

Блоки ¿-связного графа <2 являются частями разбиения этого графа набором 9^(6?)- Таким образом, блоки удовлетворяют всем свойствам частей разбиения ¿-связного графа набором ¿-разделяющих множеств. Отметим простейшие свойства блоков ¿-связного графа, родственные свойствам классических двусвязных блоков связного графа.

1) Для любых двух различных пересекающихся блоков В\ и В2 графа (7 существует множество 5 £ 9^.(6?), содержащее В\ П В2.

2) Для любых двух смежных вершин х и у графа О существует блок, содержащий обе эти вершины.

3) Для любой граничной вершины х блока В существует другой блок В\ такой, что х £ В,(В{).

4) Если В — непустой блок графа С, то для любой вершины х £ 1{В) граф — х является ¿-связным.

Зависимые и независимые множества. Компоненты зависимости

Определение 4. Назовем разделяющие множества 5 и Т независимыми, если 5 не разделяет ТиТне разделяет ¿7. В противном случае мы назовем эти множества зависимыми.

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

Определение 5. 1) Пусть <3 £ 9^(6?). Граф зависимости этого набора I)((5) — это граф, вершины которого соответствуют множествам набора, а две вершины смежны тогда и только тогда, когда соответствующие им множества зависимы,

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

Граф зависимости набора ¿-разделяющих множеств ¿-связного графа С является важным инструментов для изучения разбиения графа этим набором.

Основная часть второй главы посвящена исследованию структуры компонент зависимости набора © С ^¿(Сг), которую отображает граф компонент зависимости О®. Вершины этого графа соответствуют компонентам зависимости набора © и невырожденным частям ©-разбиения. Пусть ©1,., ©то — все компоненты зависимости набора ©, а Ах,., Ап — все невырожденные части в -Р(©). Вершина, соответствующая компоненте зависимости ©г- смежна в графе Сг@ с вершиной, соответствующей части тогда и только тогда, когда никакое множество набора © \ ©г- не отделяет часть А{ от объединения всех множеств из Компоненты зависимости ©^ и ©^ смежны в графе С?© тогда и только тогда, когда ©г- = {5}, причем Б — граница одной из частей Р(©^), или наоборот.

Теорема 1. Для ¿-связного графа О и набора © С граф Ое является деревом. Если невырожденная часть А 6 -Р(©) смежна в графе с компонентами зависимости ©1,-.,©т и только с ними, то А 6 ©¿). Более того, существуют такие части Ах € Р(в 1), .,Ате Р(6т), что т т

А = р| Аг и Л(А) = уя(Аг). г=1 г—1

Более подробное описание и доказательства свойств дерева компонент зависимости можно найти в главе 2 (теорема 2.1).

Ромашки

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

Определение 6. 1) Пусть F = {P)Q\,. ,Qm} — набор множеств вершин ¿-связного графа G, удовлетворяющий следующим условиям.

1° Для всех i G {1,. ,m} выполняются соотношения Р П Qi = 0 и \Qi\ = • Ии одно из множеств Qi не содержится в объединении остальных множеств набора.

2° Существует набор © С %ïk(G) такой, что граф зависимости £)(©) связен, а каждое множество S G © представляется в виде S = Р U Qi U Qj для различных G {l,.,m}. Для каждого i G {1,., rri} существует S G © такое, что S D Qi.

3° Множества набора © не разделяют ни одно из множеств Qi,. ,Qm

Будем называть набор F квазиромашкой, множество Р —■ центром, а множества Qi,., Qm — лепестками этой квазиромашки. Все множества Qij — Qi U Qj U P мы будем называть множествами квазиромашки F. Будем говорить, что набор © образует квазиромашку F.

2) Если, кроме того, для любых i,j G {l,.,m} выполняется Qi П Qj — 0, то будем называть набор F ромашкой.

Теорема 2. Пусть G — ¿-связный граф, а набор © С ïRk(G) образует квазиромашку F с центром Р и лепестками Q i,., Qm. Тогда лепестки квазиромашки F можно циклически пронумеровать таким образом, что Р(&) = {<31,2, <^2,3, ■ •. ,GTO>i}, где R(Gi,i+1) = Qi,i+i для всех i. (Здесь и далее мы считаем, что Qm+i = Qь)

Если два разных набора образуют квазиромашки с одним центром и одним и тем же набором лепестков, то разбиения графа (2 этими наборами совпадают. Таким образом, можно говорить о разбиении ¿-связного графа квазиромашкой. На рисунке изображено разбиение графа ромашкой с 8 лепестками. Более подробное описание разбиения ¿-связного графа квазиромашкой приведено в главе 3 (теоремы 3.1 и 3.2).

Отметим, что при малых значениях ¿ легко описать все возможные виды ромашек в ¿-связном графе. Так в двусвязном графе центр любой ромашки пуст, а каждый лепесток сотоит из одной вершины. Таким образом, ромашка в двусвязном графе представляет собой "цикл", в котором любые две соседние вершины являются границей части разбиения графа этой ромашкой, а две несоседние вершины образуют разделяющее множество, которое разбивает граф на две части так, как соответствующая им хорда разбивает цикл. Такая конструкция играет важную роль в изучении структуры двусвязного графа (см. [31]). В трехсвязном графе у любой ромашки и центр, и каждый лепесток сотоит из одной вершины. Таким образом, ромашка в трехсвязном графе представляет собой "колесо", в котором любые две соседние вершины вместе с центром являются границей части разбиения графа этой ромашкой, а две несоседние вершины вместе с центром представляют собой разделяющее множество. Здесь интересно вспомнить работу [30], в которой из любой трехсвязный граф сводился при помоши некоторых операций к колесу.

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

Теорема 3. Для любого набора ¿-разделяющих множеств © в ¿-связном графе G следующие два утверждения равносильны.

1° Каждая часть ©-разбиения содержит хотя бы к вершин.

2° Каждая компонента зависимости набора © либо состоит ровно из одного множества, либо образует ромашку.

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

Слабо нерасщепимые графы

Определение Т. Будем называть ¿-связный граф G слабо нерасщепи-мым, если в графе G нет множеств S,T G £И*.(С?) таких, что для одной из частей F 6 P(S) выполняется I(F) С Т.

Слабо нерасшепимые графы впервые рассмотрены Д. В. Карповым и A.B.Пастором в работе [7]. В этой работе показано, что ¿-связный граф, степени вершин которого не менее —¡р, является слабо нерас-щепимым. Таким образом, класс слабо нерасщепимых графов достаточно широк. Две последние главы настоящей диссертации посвящены детальному изучению структуры ¿-разделяющих множеств и блоков в слабо нерасщепимом ¿-связном графе.

Пусть О — слабо нерасщепимый ¿-связный граф, а N(0) — множество всех невырожденных блоков графа С? содержащих хотя бы по к вершин. Так как блоки являются частями ^(С)-разбиения графа G, то каждое множество 5 Е делит А7" (С?) на группы блоков лежащих в одной части из Р(Б). Будем считать множества Б и Т эквивалентными, если они лежат в одной компоненте зависимости набора и делят N(0) на одинаковые группы. Таким образом, все ¿-разделяющие множества графа О оказываются разбиты на классы эквивалентности. Эти классы оказываются удобным инструментом для изучения структуры ¿-разделяющих множеств слабо нерасщепимого ¿-связного графа.

Определяются понятия зависимых и независимых классов, обо-щающие понятия зависимых и независимых ¿-разделяющих множеств (определения приведены в начале главы 5). Строится граф зависимости классов, вершины которого соответствуют классам множеств и две вершины смежны тогда и только тогда, когда соответствующие классы зависимы. Набор из множеств всех классов, входящих в одну компоненту связности графа зависимости классов, называется комплексом. Комплекс называется большим, если он состоит из множеств более чем одного класса и малым в противном случае.

Теорема 4. Пусть О — слабо нерасщепимый ¿-связный граф, а К — одиночный комплекс в графе <7. Тогда существуют независимые множества ТЪТ2 6 и часть А е Р({ТЬТ2}) с границей Тх и Т2, удовлетворяющие следующим условиям.

1° Часть А содержит все множества из 1С. Любое отличное от Т\ и Т2 множество Б С А принадлежит комплексу К.

2° Часть А не содержит ни одного блока из N(0).

3° Если степени всех вершин графа С не менее [^у^], то А = Тх и Г2.

Теорема 5. Пусть С — слабо нерасщепимый ¿-связный граф, а О — большой комплекс. Тогда существует граничная квазиромашка Р с центром Р и циклически упорядоченными лепестками ¿1, Й1, Ь2, Я2, • • •, Ято (возможно, Ьг ~ Яг при некоторых г), удовлетворяющая следующим условиям.

1° Любая часть из Р(Р) с границей Ь^ЩиР пуста и не содержит ни одного блока из N(0).

2° Любая часть из -Р(-Р) с границей Л» и 1 и Р содержит хотя бы один блок из N(0).

3° Для любого множества 5 Е О существуют ъ и 3 такие, что 5 == Бг и в, и Р, где С и Д,, С Ь5 и Щ и =

Более подробно описание структуры множеств комплекса дано в главе 5 (теоремы 5.2-5.5).

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

Структура диссертащш

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

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

2. О. Ope. Теория графов. // Москва, "Наука", 1968. (Перевод с английского. О.Ore, Theory of graphs, 1962.)

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

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

5. Д. В, Карпов. Зависимые разделяющие множества в к-связном графе. // ПОМИ ПРЕПРИНТ 12-2003.

6. Д. В. Карпов. Структура разбиения слабо нерасщепимого к-связ-ного графа. // ПОМИ ПРЕПРИНТ 18-2003.

7. Д.В.Карпов, А. В. Пастор. О структуре k-связного графа. // Записки научных семинаров ПОМИ, 266, 2000, стр. 76-106.

8. Ю. м. лифшиц. Полные разбиения к-связного графа. // ПОМИ ПРЕПРИНТ 11-2003.

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

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

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

12. R. HALIN. A theorem on n-connected graphs. // Journal of Combinatorial Theory, 1969, vol. 7, p. 150-154.

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

14. R. Halin. Zur Theorie der n-fach zusammenhängenden Graphen. // Abh. Math. Sem. Univ. Hamburg, 1969, vol. 7, p. 133-164.

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

16. Y. o. hamidoune. On critically h-connected simple graphs. // Discrete Mathematics, 1980, vol. 32, p. 257-262.

17. F.Harary, Y. Kodama. On the genus of an n-connected graph. // Fund. Math., 1964, vol. 54, p. 7-13.

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

19. W. Hohberg. The decomposition of graphs into k-connected components. // Discrete Mathematics, 1992, vol. 109, p. 133-145.

20. J. E. Hopcroft, R. E.Tarjan. Dividing a graph into triconnected components // SIAM J. Comput., 1973, vol. 2, p. 135-158.

21. S. MacLane. A structural characterizations of planar combinatorial graphs. // Duke Math. J., 1937, vol. 3, p. 460-472.

22. W. Mader. Eine Eigenschaft der Atome endlicher Graphen. // Arch. Math., 1971, vol. 22, p. 333-336.

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

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

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

26. D.W. Matula. k-Blocks and Ultrablocks in Graphs. // Journal of Combinatorial Theory, Series B, 1978, vol. 24, p. 1-13.

27. K. Menger. Zur allgemeinen Kurventheory. // Fund. Math., 1927, p. 10, p. 96-115.

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

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

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

31. W. T. Tutte. Connectivity in graphs. // Toronto, Univ. Toronto Press, 1966.

32. H. J. Veldman. Non-k-critical vertices in graphs, jf Diskrete Mathematics, 1983, vol. 44, p. 105-110.