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

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

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

Связность.

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

Граф называется (вершинно) к-связным, если в нем не менее к + 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 от множества И^, если и .

Определение 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) Будем называть компонентой зависимости набора © любой набор Т С ©, состоящий из всех множеств, соответствующих вершинам компоненты связности графа зависимости !)((c)).

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

Основная часть второй главы посвящена исследованию структуры компонент зависимости набора © С ^¿-(Сг), которую отображает граф компонент зависимости О®-. Вершины этого графа соответствуют компонентам зависимости набора © и невырожденным частям ©—разбиения. Пусть (c)1,., ©-то — все компоненты зависимости набора ©, а Ах,., Ап — все невырожденные части вР (©-). Вершина, соответствующая компоненте зависимости ©-гсмежна в графе Сг@ с вершиной, соответствующей части тогда и только тогда, когда никакое множество набора © ©-гне отделяет часть А{ от объединения всех множеств из Компоненты зависимости (c)^ и (c)^ смежны в графе С?©тогда и только тогда, когда ©-г- = {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° Существует набор © С %ik (G) такой, что граф зависимости ?)((c)) связен, а каждое множество 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 — ¿—связный граф, а набор © С iRk (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, Theorie 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, LondonNew York, 1969, p. 91−102.

14. R. Halin. Zur Theorie der n-fach zusammenhangenden 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 zusammenhangenden Graphen. // Arch. Math., 1972, vol. 23, p. 219−224.

24. W. Mader. Endlichkeitssatze fur 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 Erdos 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.