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

о ттохгио — -—

Вершинная связность и ^-связные графы.

Критические к-связные графы и удаление вершин без потери /с-связности.

Разбиение ^-связного графа на блоки. Дерево блоков.

Минимальные к-связные графы и удаление ребер без потери ^-связности.

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

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

1.1. Вершинная связность графа.

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

1.3. Простейшие свойства минимальных фрагментов.

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

2. Избыточные множества и минимальные фрагменты не расщепимого ^-связного графа

2.1. Удаление вершин из минимальных фрагментов.

3. Блоки и деревья блоков Ь-связного графа

3.1. Понятие блока для ^-связного графа.

3.2. Удаление внутренней вершины блока.

3.3. Деревья блоков Ь-связного графа.

4. Избыточные ребра ¿-связного графа 8(

4.1. Избыточные ребра и минимальные фрагменты. 8(

Вершинная связность и к-связные графы

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

Начало активных исследований свойств ^-связных графов, то есть графов, содержащих как минимум к + 1 вершину, и сохраняющих связность при удалении произвольных к — 1 вершин, было положено в 1927 году работой [25]. Примерно с середины 60-х годов XX века начались исследования такого специфического свойства к-связных графов, как сохранение Аьсвязности графа при удалении его вершин и ребер.

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

Критические к-связные графы и удаление вершин без потери к-связности

В 1972 году G. Chartrand, A. Kaugars и D. R. Lick [8] доказали, что в любом ¿-связном графе, степени всех вершин которого не меньо J I ше, чем ^f1-, существует вершина, при удалении которой сохраняется ¿-связность. Этот результат был получен как следствие более сильного утверждения — было доказано существование такой вершины в любом ¿-связном графе, в котором при удалении любого ¿-разделяющего множества (то есть разделяющего множества, содержащего ровно к вершин) не могла образоваться компонента связности, содержащая менее, чем вершин. В данной диссертации такие графы будут называться нерасщепимыми ¿-связными графами.

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

В работе [8] было доказано, что в нерасщепимом ¿-связном графе любая вершина, принадлежащая наименьшему по числу вершин фрагменту (то есть компоненте связности, образующейся при удалении некоторого ¿-разделяющего множества) данного графа является избыточной. Более простое доказательство этого утверждения предложил

W. Мас1ег в работе [19].

В последующие годы, У. О. НагшсЬипе в работе [14] и Н. Д. УеЫшап в работе [31] получили некоторые обобщения данного результата. В 1980 году в работе [14] было доказано, что в любом критическом ¿-связном графе содержатся как минимум две вершины, степени которых меньше, чем Из этого, в частности, следует, что в любом ¿-связном графе, степени всех, кроме может быть одной, вершин которого не меньше, чем рр, существует избыточная вершина.

В 1983 году в работе [31] было доказано, что в любом нерасщепи-мом ¿-связном графе любая вершина, принадлежащая минимальному (по включению) фрагменту данного графа, является избыточной. Из этого следует, что в любом нерасщепимом ¿-связном графе должно содержаться не менее к 4- 1 + ^(¿) избыточных вершин, где ^(¿) = 0 при нечетных к и е(к) = 1 при четных к. Также в работе [31] доказано, что в любом ¿-связном графе, степени всех, кроме, может быть, одной, вершин которого не меньше, чем существует как минимум 2 + е(к) избыточных вершин. Более того, данная оценка является точной.

Глава 2 данной диссертации посвящена развитию этих исследований. В теореме 2.1 доказывается, что любая вершина, принадлежащая произвольному минимальному фрагменту ¿-связного графа, является избыточной при более слабых, чем в работе [31] условиях. А именно, мы доказываем это для любого ¿-связного графа, для любого фрагмента и любого ¿-разделяющего множества которого, множество вершин данного фрагмента не содержится в данном ¿-разделяющем множестве (в данной диссертации такие графы будут называться слабо не-расщепимыми ¿-связными графами). Данное условие не может быть ослаблено, поскольку если какой-либо фрагмент ¿-связного графа содержится внутри некоторого ¿-разделяющего множества, то никакая вершина этого фрагмента, очевидно, не может быть избыточной. Следует, правда, отметить, что доказательство из работы [31] может быть легко обобщено на случай слабо нерасщепимого £;-связного графа, однако, в данной диссертации приведено другое доказательство данного утверждения. Далее, в главе 3, мы усиливаем этот результат — в теореме 3.1 при помощи обобщения понятия блока на случай к-связного графа дается полное описание множества избыточных вершин слабо нерасщепимого ^-связного графа.

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

В теореме 2.2 исследуется следующая ситуация. Пусть Я — произвольное /¿-разделяющее множество нерасщепимого ^-связного графа С. Через С — Я мы будем обозначать граф, образовавшийся в результате удаления из графа С? всех вершин множества Я. В теореме 2.2 доказано, что если нерасщепимый /¿-связный граф (7 удовлетворяет некоторым дополнительным условиям, то можно выбрать по одной вершине в каждой из компонент связности графа (7 — Я так, чтобы полученное множество вершин было избыточным.

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

Понятие блока для к-связного графа. Дерево блоков

При изучении различных свойств связных графов, не являющихся двусвязными, весьма полезным является понятие блока. Любой связный граф может быть представлен в виде обьединения двусвязных блоков, причем это представление, в некотором смысле, можно назвать разбиением графа на блоки. При этом важную роль играет тот факт, что блоки и точки сочленения графа можно рассматривать, как вершины некоторого дерева — так называемого дерева блоков и точек сочленения, или просто дерева блоков данного графа. Основные определения и факты, связанные с понятиями блока и дерева блоков, можно найти в [6, главы 3 и 4], а также в [3, глава 5].

В связи с исключительной важностью теории блоков и точек сочленения для изучения свойств связных графов, неоднократно предпринимались попытки обобщить эту теорию на случай к-связных графов. Ряд авторов (см., например, [16], [6] и [24]) предлагали называть /¿-компонентой или А;-блоком графа G максимальный по включению /¿-связный подграф графа G. Основным недостатком такого определения является то, что при этом нельзя говорить о разбиении /¿-связного графа на (к + 1)-блоки. Таким образом, для данного определения нельзя сколько-нибудь разумным образом определить понятие, аналогичное понятию дерева блоков. В связи с этим, более перспективным представляется другой подход к обобщению понятия блока.

S. Mac Lane в работе [23] и W. Т. Tutte в работе [29] независимо предложили похожие конструкции, дающие естественное обобщение понятия блока и дерева блоков на случай двусвязного графа. Основная идея конструкции из работы [29] состоит в том, что после "разделения" двусвязного графа по некоторому его 2-разделяющему множеству, к каждому из образовавшихся подграфов (порожденному вершинами одной из компонент связности, образовавшейся при удалении 2-разделяющего множества, и вершинами самого 2-разделяющего множества) добавляется так называемое виртуальное ребро, соединяющее вершины данного 2-разделяющего множества. Таким образом, блоки, на которые при использовании данной конструкции разбивается двусвязный граф, вообще говоря, не являются его подграфами. С другой стороны, данная конструкция дает просто описываемый процесс разбиения двусвязного графа на блоки, что позволяет построить дерево, являющееся естественным обобщением понятия дерева блоков связного графа. Детальное описание данной конструкции можно найти также в работах [18] и [5]. Конструкция, предложенная в работе [23] в целом аналогична, хотя и несколько отличается от конструкции, предложенной в работе [29].

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

В главе 3 данной диссертации определяются понятия блока и дерева блоков для ¿-связного графа. Конструкция дерева блоков для ¿-связного графа, предложенная в данной диссертации, отличается от конструкции, предложенной в работе [17], в следующих важных деталях.

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

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

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

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

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

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

Минимальные к-связные графы и удаление ребер без потери ^-связности

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

В 1967-68 годах G.A.Dirac в работе [9] и M.D.Plummer в работе [26] независимо доказали, что в любом минимальном двусвязном графе (т. е. двусвязном графе, который при удалении любого ребра перестает быть двусвязным) есть вершина степени 2. Таким образом, из любого двусвязного графа, степени всех вершин которого не меньше трех, можно удалить одно из ребер без потери двусвязности. В 1969 году R. Haiin в работе [10] обобщил этот результат, доказав, что из любого fc-связного графа, степени всех вершин которого не меньше k +1, можно удалить одно из ребер без потери /¿-связности.

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

В работе [10] фактически доказано, что если Н — фрагмент ¿-связного графа 6?, содержащий наименьшее число вершин, и й — ¿-разделяющее множество, при удалении которого образовался фрагмент Н, то любое ребро графа (7, соединяющее вершину фрагмента Н с вершиной множества Я, является избыточным. Далее, в работе [13], Я. НаНп доказал, что любое ребро графа принадлежащее фрагменту Н, также является избыточным. Более простое доказательство последнего утверждения предложил Мас1ег в работе [19].

Далее, интересным представляется вопрос о наличии существенных ребер в минимальных фрагментах ¿-связного графа. В работах [11], [12] и [19] рассматриваются нетривиальные (т. е. содержащие более одной вершины) минимальные фрагменты минимального ¿-связного графа, и доказываются некоторые свойства, которыми они должны обладать. После этого, в работе [20], XV. Мас1ег доказал, что минимальный ¿-связный граф не может содержать нетривиальные минимальные фрагменты. Однако, результаты, доказанные в работах [11], [12] и [19], по прежнему актуальны, так как использованные в этих работах методы могут быть применены для поиска избыточных ребер в нетривиальном минимальном фрагменте произвольного ¿-связного графа.

В 1972 году Ма(1ег в работе [20] доказал, что любой цикл произвольного ¿-связного графа содержит либо вершину степени ¿, либо избыточное ребро. Таким образом, в любом цикле ¿-связного графа <2, степени всех вершин которого не меньше ¿ +1, обязательно содержится избыточное ребро. Из этого, в частности, следует, что в любом минимальном фрагменте данного графа С? содержится избыточное ребро. Однако утверждение о том, что любое ребро произвольного минимального фрагмента графа 6? является избыточным, вообще говоря, неверно.

В главе 4 данной диссертации проводится исследование вопроса о возможности удаления ребра, принадлежащего данному минимальному фрагменту к-связного графа, или инцидентного одной из вершин этого фрагмента, при котором не нарушается ¿-связность графа. В теореме 4.1 и лемме 4.2 мы обобщаем результаты, полученные в работах [11], [12] и [19] для нетривиальных минимальных фрагментов минимального ¿-связного графа на случай нетривиального минимального фрагмента произвольного ¿-связного графа, степени всех вершин которого не меньше & + 1. При доказательстве этих утверждений мы пользуемся методами, изложенными в работах [11] и [12].

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

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

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

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

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

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

4. Ф. Харари. Теория графов. Москва, Мир, 1973. (Переводе английского. F. Harary, Graph theory. 1969.)7. в. bollobas. Extremal graph theory. London New York - San Francisco: Academic Press, 1978.

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

6. G. A.dlrac. Minimally 2-connected graphs. // Journal fiir die reine und angewandte Matheniatik, 1967, vol. 228, p. 204-216.

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

8. 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.

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

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

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

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

13. S.Mac Lane. A structural characterizations of planar combinatorial graphs. // Duke Math. J., 1937, vol. 3, p. 460-472.93 —

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

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

16. M. D. Plummer. On minimal blocks, j j Transactions of the American Mathematical Society, 1968, vol. 134, p. 85-94.

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

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

19. W. T. Tutte. Connectivity in graphs. Toronto, Univ. of Toronto Press, 1966.

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

21. H. J. veldman. Non-K-critical vertices in graphs. // Diskrete Mathematics, 1983, vol. 44, p. 105-110.