Размещено на http://www.allbest.ru/

1

Дипломная работа

Задача остовных деревьев в k-связном графе

Содержание

остовный граф матрица теорема

Введение

1. Основные определения

1.1 Основные определения теории графов

1.2 Матрицы смежности и инцидентности

1.3 Деревья

2. Связность

2.1 Вершинная связность и реберная вязность

2.2 Двусвязные графы

2.3 Теорема Менгера

3. Выделение k непересекающихся остовных деревьев 2k-реберно связном графе

3.1 Построение k непересекающихся остовных деревьев

3.2 Необходимость условия (G)2k

3.3 Текст программы

Вывод

Введение

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач-проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.

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

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

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

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

1.1 Определения

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

Это приводит к определению графа как абстрактного математического понятия. Рассматривая множество V, состоящее из соединенных некоторым образом точек. Назовем V множеством вершин и элементы vV-вершинами. Граф

G=G(V) (1.1)

c множеством вершин V есть некоторое семейство сочетаний, или пар вида

E=(a, b), a,bV (1.2)

указывающие, какие вершины являются соседними. В соответствии с геометрическим представлением графа каждая конкретная пара (1.2) называется ребром графа; вершины a и b называются концевыми точками, или концами ребра.

Можно использовать и другой подход. Если даны два множества V₁ и V₂ то можно образовать множество всех пар

(v₁,v₂), v₁V₁, v₂V₂.

Это множество пар называется произведением и обозначается через V₁V₂. В нашем случае каждая пара вершин (a, b) есть элемент произведения VV. Таким образом можно сказать, что граф G из (1.1) с данными ребрами (1.2) есть некоторое подмножество произведения VV.

Это определение графа должно быть дополнено в одном важном отношении. В определении ребра (1.2) можно принимать или не принимать во внимание порядок расположения двух его концов. Если этот порядок несуществен, т.е. если

E=(a, b)=(b, a),

то говорят, что Е есть неориентированное ребро; если же этот порядок существен, то Е называется ориентированным ребром. В последнем случае а называется также начальной вершиной, а b-конечной вершиной ребра Е. Можно также говорить, что Е есть ребро, выходящее из вершины а (отходящее от вершины а, исходящее из вершины а) и входящее в вершину b (подходящее к вершине b, заходящее в вершину b). Как в случае ориентированного, так и в случае неориентированного ребра говорят, что ребро Е из (1.2) инцидентно вершинам a и b, а также что а и b инцидентны Е.

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

Граф называется неориентированным, если каждое его ребро не ориентированно, и ориентированным, если ориентированны все его ребра.

На рис.1.2 приведены примеры неориентированных графов. На рис 1.3 изображены ориентированны графы.

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



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

Мы уже отмечали, что при фактическом изображении графа имеется большая свобода в размещении вершин и в выборе формы соединяющих их дуг. Поэтому может оказаться, что один и тот же граф представляется совсем различными чертежами. Будем говорить, что два графа G и G' изоморфны, если существует такое взаимно однозначное соответствие между множествами их вершин V и V', что вершины соединены ребрами в одном из графов в том и только том случае, когда соответствующие им вершины соединены в другом графе. Если ребра ориентированы, то их направления также должны соответствовать друг другу. На рис 1.2 приведены примеры изоморфных графов, образованных ребрами и вершинами правильных многогранников.

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



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

U=U(V), (1.3)

ребрами которого являются всевозможные пары (1.2) для двух различных вершин a и b из V. На рис. 1.4 даны схемы полных графов для множеств вершин из четырех и из пяти элементов.

В ориентированном полном графе U^(d) имеются пары ребер, по одному в каждом направлении. Соединяющие любые две различные вершины a и b.

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



Во-первых, можно получить ребра, у которых обе концевые точки совпадают:

L=(a, a). (1.4)

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

петлю в каждой вершине, так что ребрами U₀ являются все пары (1.2), где допускается и a=b.

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

E_i=(a, b)_i, (1.5)

как это изображено на рис. 1.6. Для ориентированного графа две вершины a и b могут соединяться несколькими ребрами в каждом из направлений:

E_i=(a, b)_i, =(a, b)_j,

(рис. 1.7).

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

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

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

каждого ориентированного графа существует также соотнесенный неориентированный граф G_u, ребрами которого являются ребра G, но уже без ориентаций. Иногда удобно превратить неориентированный граф G в ориентированный граф G_d при помощи процесса удвоения, состоящего в замене каждого ребра G парой с теми же концами и приписывании им противоположных ориентаций.

Граф называется плоским, если он может быть изображен на плоскости так что все пересечения ребер являются вершинами G. Граф на рис 1.8а плоский, а на рис 1.8б неплоский.

1.2 Матрицы смежности и инцидентности

В §1 мы определили ребро Е (1.2) графа G (1.1) как элемент или точку (a, b) в произведении VV. Как обычно, элементы этого произведения можно представить в виде клеток квадратной таблицы М с элементами множества V в качестве координат по двум осям (рис 2.1).



В точку с координатами (a, b) поместим числа 1 или 0 в зависимости от того, существует или не существует в G соответствующее ребро. Таким образом, мы получили конечную или бесконечную матрицу смежности (вершин) М(G), которая полностью описывает G, если имеет однократные ребра. Обычно обозначения выбираются так, чтобы элементы (а, а), соответствующие петлям, располагались на главной диагонали матрицы М. Если G-неориентированный граф, то ребра (a, b) и (b, a) существуют одновременно, таким образом, неориентированным графам соответствуют симметрические матрицы смежности.

Если G имеет кратные ребра, то числа 0 и 1 в клетках (a, b) можно заменить кратностями (a, b) ребер, соединяющих а и b. Это дает описание графа G матрицей с целыми неориентированными элементами. Обратно, любая такая матрица может быть интерпретирована как граф, так что любые результаты для графов могут быть сформулированы как свойства таких матриц.

Сказанное приводит к дальнейшему расширению понятия графа, использующему уже все конечные или бесконечные матрицы, элементами которых являются вещественные неотрицательные числа. Такие матрицы встречаются в различных областях математики. Например, стохастические матрицы - в теории вероятностей и в теоретической физике. Где рассматриваемая система имеет некоторое множество V возможных состояний, и любая пара состояний (a, b) связывается некоторой вероятностью перехода (a, b). Другим примером является граф, представляющий схему дорог, в котором (a, b) означает соответствующее расстояние между а и b.

Графы могут быть также описаны матрицами другого вида. Всякий граф состоит из объектов двух типов-вершин и ребер. Можно построить матицу M₁(G), строки которой соответствуют вершинам, а столбцы-ребрам. На месте (а, Е) в этой матрице поместим значение =1, если а-начальная вершина ребра Е, значение =-1, если а-конечная вершина, и =0, если а не инцидентно Е. Если G-неориентированный граф, то можно использовать только значения =1 и =0. Эта матрица M₁(G) называется матрицей инцидентности графа G.

Введем, наконец, матрицу смежности ребер I(G), в которой и строки и столбцы отвечают ребрам G. Для простоты предположим. Что G не имеет петель, а ребра неориентированные и однократные. На месте (E, E') в I(G) поместим =1, если Е и Е'-различные ребра с общим концом, и =0, если Е=Е' или если они не имеют общего конца. Таким образом, I(G)-квадратная матрица, определяемая графом G.

Можно встать и на другую точку зрения и рассматривать I(G) как матрицу смежности вершин для нового графа, также обозначаемого через I(G), вершинами которого являются ребра Е графа G, а ребрами-пары (E, E') с =1. Назовем I(G) графом смежности ребер или смежности графом для G. Существование такого графа, в котором бывшие ребра становятся вершинами и наоборот, объясняет двойственность между вершинами и ребрами, встречающуюся в некоторых вопросах теории графов.

Фактическое построение смежности графа I(G) по чертежу графа G просто. На каждом ребре Е выбираем фиксированную точку е_Е, например середину Е. Пару таких вершин (е, е') соединяем новым ребром, принадлежащим I(G), тогда и только тогда, когда соответствующие ребра Е и Е' имеют общую вершину в G.

Рис. 2.2 дает это построение для графа тетраэдра; смежностным графом для него является граф октаэдра.

Предположим, то в вершине е сходится (е) ребер Е=(е, е') из G. Тогда в I(G) середина e_E ребра Е соединяется ребрами с (е)-1 серединами остальных ребер из G, имеющих конец в е. Таким образом, в I(G) эти новые ребра образуют новый граф U(e) с (е) вершинами. В I(G) вершина e_E соединяется ребрами также с (е')-1 серединами остальных ребер из G, из имеющих конец в e', и эти новые ребра образуют другой полный граф U(e'). Два графа U(e) и U(e') имеют ровно одну общую вершину, именно вершину e_E, определяемую единственным ребром Е, соединяющим e и e'. Таким образом, I(G) имеет такое непересекающееся по ребрам разложение

I(G)= 2.1

На полные графы U(e) с (е) вершинами, что U(e) имеет единственную общую вершину с каждым из (е) других полных графов U(e'). Исключение составляет случай, когда (e, e')-единственное ребро в e', т.е. (е')=1. Тогда не существует графа. U(e').

Предположим, что, наоборот, для графа G₁ существует такое разложение (2.1) на полные графы, что пара (U(e), U(e')) имеет не более одной общей вершины. Тогда G₁ можно рассматривать как смежностный граф G₁=I(G) некоторого графа G, считая, что каждое U(e) имеет ₁(е) общих вершин с другими U(e'). Каждому U(e) поставим в соответствие одну вершину e и соединим e и e' ребром в G тогда и только тогда, когда U(e) и U(e') имеют общую вершину. К этим ребрам добавим (е)- ₁ ребер (e, e''), идущих к новым вершинам e'', в которых существует только одно это ребро.

1.3 Деревья

Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется ациклическим (или) лесом. Таким образом, компонентами леса являются деревья. На рис.12 изображены все деревья шестого порядка.

Существует несколько вариантов определения дерева; некоторые из них отражены в следующей теореме.

Теорема 3.1 Для графа следующие утверждения эквивалентны:

1) G - дерево;

2) G - связный граф и m=n-1;

3) G - ациклический граф и m=n-1;

4) любые две несовпадающие вершины графа соединяет единственная простая цепь;

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

1)2) Воспользуемся индукцией по n. При n=1 утверждение трививально. Пусть n>1, еEG. В дереве G нет циклов, следовательно, согласно лемме 4.1, граф G - е имеет ровно две компоненты Т₁ и Т₂,

каждая из которых есть дерево. Пусть дерево T_i является (n_i, m_i) - графом, i=1, 2. По индуктивному предположению верно равенство

m_i=n_i-1. (1)

Далее имеем

m=m₁+m₂+1=(n₁-1)+(n₂-1)+1=(n₁+n₂)-1=n-1.

2) 3) Граф G связен и m=n-1. Нужно доказать, что в G нет циклов. Пусть, напротив, в графе G есть цикл и пусть ребро е-ребро этого цикла. Тогда граф G - е связен (лемма 4.8) и имеет n-2 ребра, что противоречит теореме 4.9. следовадельно, G -ациклический граф.

3) 4) Пусть к-число компонент графа G. Пусть, далее, компонента Т_i является (n_i, m_i)-графом. Так как Т_i-дерево, то верно равенство (1). Теперь имеем

n-1=m=m₁+m₂+…+m_k=(n₁-1)+(n₂-1)+…+(n_k-1)=(n₁+…+n_k)-k=n-k;

т.е. к=1. Итак, G-связный граф и потому любые несовпадающие вершины u и v соединены в нем просой цепью. Если бы в G были две несовпадающие простые (u,v)-цепи, то согласно утверждению 4.3 их объединение содержало бы цикл. Следовательно, каждые две вершины соединены единственной простой цепью.

4) 5) пара несовпадающих вершин, принадлежащих одному циклу, соединена по меньшей мере двумя простыми цепами. Следовательно, граф G ациклический. Пусть u и v-две его нечмежные вершины. Присоединим к графу G ребро e=uv. В G есть простая (u,v)-цепь, которая в G+e дополняется до цикла. В силу утверждения 4.4 этот цикл единственный.

5) 1) нужно докакзать, что граф G связен. Если бы вершины u и v принадлежали разным компонентам графа G, то граф G+uv не имел бы циклов, что потиворечит утверждению 5). Итак, G связен и потому является деревом. Доказано.

Следствие 3.2. В любом дереве порядка n2 имеется неменее двух концевых вершин.

Пусть

d₁, d₂, …, d_n (2)

-степенная последовательность дерева. Тогда

(лемма о рукопожатиях) и все d_i>0. Следовательно, хотя бы два числа из последовательности (2) равны 1.

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

Следствие 3.3. число ребер произвольного графа G, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m(G)-|G|+k(G), где m(G) и k(G)-число ребер и число компонент графа G соответственно.

Если (n₁, m₁)-граф Н является одной из компонент графа G, то для превращения ее в остове дерево нужно удалить m₁-(n₁-1) подходящих ребер. Суммируя по всем k(G) компонентам, получим требуемое.

Число (G)=m(G)-|G|+k(G) называется циклическим рангом (или цикломатическим числом) графа G. число ребер остова графа G называется коциклическим рангом графа G. таким образом.

Очевидны три следствия 13.4-13.6.

Следствие 3.4. Граф G является лесом тогда и только тогда, когда (G)=0.

Следствие 3.5. граф G имеет единственный цикл тогда и только тогда, когда (G)=1.

Следствие 3.6. Граф, в котором число ребер не меньше, чем число вершин, содержит цикл.

Утверждение 3.7. Если S и Т -два остова графа G, то для любого ребра е₁ графа S существует такое ребро е₂ графа Т, что граф также является остовом.

Доказательство

Не ограничивая общности, будем считать граф G связным. Граф имеет ровно две области связности; пусть это будут А и В. Поскольку граф Т связен, то в нем существует ребро е₂, один из концов которого входит в А, а другой - в В. Граф Н=S-e1+e₂ связен и число ребер в нем такое же, как в дереве S. следовательно, он сам является деревом. Итак, Н-остов графа G. Доказано.

Теорема 13.8. Центр любого дерева состоит из одной или из двух смежных вершин.

Доказательство

Очевидно, что концевые вершины дерева Т являются центральными только для T=K₁ или T=K₂.

Пусть Т дерево порядка n>2. Удалив из Т все концевые, получим дерево Т'. Очевидно, что эксцентриситет Т на единицу меньше эксцентриситета дерева Т и что центры деревьев Т и Т совпадают. Далее доказательство легео проводится индукцией по числу веншин.Доказано.

2. Связность

Связный граф был определен как граф, у которого любые две вершины соединены цепью. Так, оба графа К_n и C_n связны, однако интуитивно ясно, что при n>3 граф K_n «сильнее» связен, чем C_n. В этой главе вводится и исследуются понятия, характеризующие степень связности графа.

2.1 Вершинная связность и реберная связность

Прежде чем ввести понятия вершинной и реберной связности, рассмотрим одну математическую модель, возникающую, в частности, при проектировании и анализе сетей ЭВМ. Имеется сеть, состоящая из центров хранения и переработки информации. Некоторые пары центров соединены каналами. Обмен информацией между любыми двумя центрами осуществляется либо непосредственно по соединяющему их каналу, если он есть, либо через другие каналы и центры. Сеть считается исправной, если каждая пара центров в состоянии обмениваться информацией. Такой сети естественно сопоставить граф: вершины-центры, ребра-каналы сети. Тогда исправной сети будет соответствовать связный граф. Важным понятием является надёжность (живучесть) сети, под которой обычно подразумевают способность сети функционировать при выходе из строя одного или нескольких центров или (и) каналов. Ясно, что менее надежной следует считать ту сеть, исправность которой нарушается при повреждении меньшего количества элементов. Оказывается, надежность сети можно измерять на основе вводимых ниже определений.

Числом вершин связности (или просто числом связности) (G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу.

Так, например, (K₁)=0, (K_n)=n-1, (C_n)=2.

Это вполне согласуется с интуитивным представлением том, что при n>3 граф K_n сильнее связен, чем C_n.

Граф G, представленный на рис. 4.1 связен, но его связность можно нарушить, удалив вершину 4. Поэтому (G)=1. Если же попытаться нарушить связность этого графа путем удаления ребер (а не вершин), то придется удалить не менее трех ребер. Например, G распадается на две компоненты

при удалении ребер {4,5}, {4,6}, {4,7}. Чтобы учесть это обстоятельство, введем еще одно определение.

Пусть G-граф порядка n>1. Числом реберной связности (G) графа G назовем наименьшее число ребер, удаление которых приводит к несвязному графу. Число реберной связности графа будем считать равным нулю, если этот граф одновершинный.

В качестве иллюстрации снова обратимся к графу G на рис. 4.1 Здесь (G)=3 и, следовательно, (G)>(G). Ниже будет показано, что противоположное неравенство невозможно ни для какого графа.

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

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

Таким образом, точки сочленения и мосты - это своего рода «узкие места» графа. Граф, изображенный на рис. 4.2, имеет три точки сочленения a, b, c и один мост ab.

Понятно, что концевая вершина моста является точкой сочленения, если в графе есть другие ребра, инцидентные этой вершине.

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

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

Выясним теперь соотношения между числами (G) и (G). Если граф G не связен или имеет мост, то очевидно, что (G)= (G). Пусть G- связный граф без мостов. Выберем в этом графе множество Е₁, состоящее из =(G) ребер, удаление которых приводит к несвязному графу. Пусть E₂ E₁, |E₂|=-1. Граф G - E₂ связен и имеет мост, который обозначим через uv. Для каждого ребра из множества Е₂ выберем какую-либо инцидентную ему вершину, отличную от u и v. Удалим теперь выбранные вершины из графа. Этим самым будут удалены, в числе прочих, и все ребра, входящие в Е₂. Если оставшийся граф не связен, то =(G)<. Если же он связен, то ребро uv является мостом. Поэтому удаление одной из вершин u или v приводит к несвязному или одновершинному графу, а это означает, что .

Таким образом, доказана

Теорема 4.1: Для любого графа G верны неравенства

(G).

Граф называется к-связным, если , и реберно-к-связным, если . Таким образом, отличный от К₁ граф 1-связен (односвязен) тогда и только тогда, когда он связен, а 2-связные (двусвязные) графы - это связные графы без точек сочленения, не являющиеся одновершинными.

Граф G, изображенный на рис. 4.1 1-связен и реберно-3-связен. Легко видеть, что этот граф содержит подграфы, являющиеся «более связными», чем сам граф. Таков, например, подграф, порожденный множеством вершин {1, 2, 3, 4, 8}. Он 3-связен.

Чтобы учесть эту и подобные ей ситуации, естественно ввести следующее определение: максимальный k-связный подграф графа называется его к-связной компонентой, или просто к-компонентой.

Это определение иллюстрируется на рис. 4.3. На этом рисунке граф G₁ имеет две 2-компоненты, а G₂-две 3-компоненты. Сами графы G₁ и G₂

являются 1-компонентами графа G₁G₂. легко заметить, что 2-компоненты графа G₁ имеют одну большую вершину, а 3-компоненты графа G₂-две общие вершины. Следующая теорема показывает, что это обстоятельство не случайно.

Теорема 4.2: Две различные к-компоненты графа имеют не более чем к-1 общих вершин.

Доказательство

Пусть G₁ и G₂ -различные k-компоненты графа G и VG₁VG₂=X. Предположим, что |X|k, и докажем, что тогда граф G₁G₂ должен быть к-связным. Для этого в данном случае достаточно показать, что он остается связным после удаления любых k-1 вершин, т.е. Y V(G₁ G₂), |Y|=k-1, то граф (G₁ G₂) - Y связен. Положим

Y_i=(VG_i\X) Y, i=1,2, Y₃=XY.

Ясно, что

|Y_i|k-1, i=1,2,3, Y= Y₁Y₂Y₃.

Поскольку

|Y_i Y₃|k-1, i=1,2,

и графы G₁ и G₂ k-связны, то графы

H_i=G_i-(Y_iY₃), i=1,2,

связны. Так как по предложению |X|k, то X\Y₃Ш, т.е. связны графы H₁ и H₂ имеют хотя бы одну общую вершину. Следовательно, связен граф H₁H₂=(G₁G₂)-Y. Последнее означает, что граф G₁G₂ k-связен. Поэтому, вопреки предположению, ни G₁ не являются k-компонентами графа G.

2.2 Двусвязные графы

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

Рассмотрим вначале некоторые простые свойства 2-связных графов, вытекающие непосредственно из определений:

1) степени вершин 2-связного графа больше единицы;

2) если графы G₁ и G₂ 2-связны и имеют не менее двух общих вершин, то граф G₁G₂ также 2-связен;

3) если граф G 2-связен и Р-простая цепь, соединяющая две его вершины, то граф GP также 2-связен;

4) если вершина v не является точкой сочленения связного графа, то любые две его вершины соединены цепью, не содержащей v; в частности, в 2-связном графе для любых трех несовпадающих вершин a, b, v имеется (a, b)-цепь, не проходящая через v.

Этими свойствами мы будем пользоваться без каких-либо пояснений и дополнительных ссылок на них.

Теорема 5.1 пусть G-связный граф и |G|>2. Тогда следующие утверждения эквивалентны:

1) граф 2-связен;

2) любые две вершины графа принадлежат простому циклу;

3) любая вершина и любое ребро принадлежат простому циклу;

4) любые два ребра принадлежат простому циклу;

5) для любых двух вершин a и b и любого ребра е существует простая (a,b)-цепь, содержащая е;

6) для любых трех вершин a,b,c существует простая (a,b)-цепь, проходящая через с.

1)2). Пусть a и b-две вершины графа G. Рассмотрим множество всех простых циклов графа G, содержащих а. Обозначим через U множество всех вершин, входящих в эти циклы. Ясно, что UШ. Действительно, простой цикл, содержащий а, можно получить, объединить два ребра ax и ay (x?y) и простую (x, y)-цепь, не проходящую через а (существующую согласно свойству 4)). Предположим, что bU, и положим =VG\U. Поскольку граф G связен, то в нем найдется такое ребро zt, что zU, t(рис. 5.1). Пусть S-простой цикл, содержащий a и z. Так как G - 2-связный граф, то в нем имеется простая (a, t)-цепь P, не содержащая z. Пусть v - первая, считая от t, вершина, входящая в S, т.е. (t, v)-подцепь цепи P не имеет с S общих вершин, отличных от v. Теперь легко построить простой цикл, содержащий a и t. Он получается объединением (v, z)- цепи, проходящей через а и являющейся частью S, с ребром zt и (t,v)-подцепью цепи Р (на рис. 5.1 этот цикл показан пунктирной линией). Следовательно, t; но это противоречит выбору ребра zt. Таким образом, =Ш, т.е. a и b лежат на общем простом цикле.

2)3). Пусть а-вершина и zt-ребро графа G. По условию G содержит цикл S, проходящий через вершины a и z. Не теряя общности будем считать, что ztS. Если при этом окажется, что S проходит через вершину t, то требуемый цикл строится очевидным образом. Пусть S не проходит через t. Тогда рассмотрим простой цикл S', проходящий через вершины t и a. Такой цикл, по условию, существует. Частью этого цикла является простая цепь Р, соединяющая t с некоторой вершиной vS. Цепь Р можно выбрать так, чтобы



VPVS={v}. искомый цикл теперь строится точно так же, как в предыдущем пункте.

3)4). Пусть ab и tz-два ребра графа G. По условию G имеет простые циклы S и S', первый из которых содержит ab и z, а второй - ab и t. Далее искомый цикл строится так же, как в предыдущих пунктах.

4)5). Пусть a,b VG, tzEG. Будучи связным, граф G содержит простую цепь P=(a,x,…,b). Согласно утверждению 4) а графе G есть простой цикл S, содержащий ребра ax, tz. Легко видеть, что в объединении SP имеется требуемая цепь.

5)6). Пусть a,b,cVG, cdEG. По условию в графе имеется простая (a,b)-цепь, проходящая через cd и, следовательно, содержащая c.

6)1). Пусть vVG. Покажем. Что граф G - v связен, т.е. любая a,b его вершин соединена цепью. Действительно, согласно утверждению 6) в графе G имеется простая (v,b)-цепь, которая, очевидно, не проходит через v и, следовательно, является (a, b)-цепью и в графе G - v. Доказано.

Если в формулировке теоремы 34.1 заменить всюду слова «простая цепь» и «простой цикл» соответственно на слова «цепь» и «цикл», то получим аналогичную теорему о 2-реберно-связном графах.

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

Максимальные относительное включения элементы множества связных подграфов графа G, не имеющих точек сочленения, называются его блоками. Таким образом, каждый блок графа либо 2-связен, либо совпадает с К₂ или К₁ (граф К₁ - блок тогда и только тогда, когда он является связной компонентой). Связный граф без точек сочленения также называют блоком.

Множество вершин блока будем называть блоковым множеством.

Например, граф, изображенный на рис. 5.2, содержит пять блоков B_i (i=1,2,3,4,5) (они обведены пунктирными линиями). Среди этих блоков В₁, В₂ и В₃ -2-связные графы, а каждый из двух оставшихся является ребром.

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

Утверждение 5.3. Если блок графа содержит вершины a и b, то он содержит и всякую простую (a, b)-цепь этого графа.

Эти утверждения непосредственно следуют из перечисленных в начале параграфа свойств 2-связных графов и теоремы 5.1.

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

Следующая конструкция дает представление о структуре графа «с точностью до блоков». Пусть В=В{B_i} и С={c_i} - соответственно множества блоков и точек сочленения графа G. Сопоставим с G граф bc(G), у которого BC - множество вершин и {B_ic_i: BB, c_iC, c_iB_i} - множество ребер. Тем самым, ребра двудольного графа bc(G) указывают на принадлежность точек сочленения блоками. На рис. 5.3 представлены графы G и bc(G).

Утверждение 5.5. Если граф G связен, то bc(G)-дерево.

Доказательство:

Очевидно, что из связности графа G вытекает связность графа bc(G).

Предположим, что bc(G) содержит цикл С. Пусть этот цикл имет вид С=(c, b,c, b,…,c,b,c). Каждый из блоков B содержит (с,с)- цепь и объединение этих цепей дает простой цикл в графе G. Обозначим этот цикл через С'. Ясно, что С' содержит по крайне мере две вершины каждого из блоков B. Поэтому из утверждения 34.3 следует, что цикл С' должен содержаться в каждом их этих блоков. Последнее означает, что каждая пара блоков B имеет не менее |C'|3 общих вершин. Получаем противоречие с утверждением 5.2. доказано.

Граф bc(G) называется bc-деревом связного графа G.

Блоки графа G, соответствующие концевым вершинам его bc-дерева, называются концевыми блоками.

Похожее представление графа можно получить, положив в основу его максимальные реберно-2-связные подграфы, т.е. максимальные связные подграфы, не содержащие мостов. Такие подграфы называют листами. Не останавливаясь на деталях заметим следующее. Каждая вершина графа порядка n>1 принадлежит в точности одному листу и каждое ребро, не являющееся мостом, входит только в один лист. Таким образом, граф состоит из листов и мостов, соединяющих некоторые из них. Для описания строения графа «с точностью до листов» можно ввести граф, аналогичный графу bc(G). Вершины такого графа биективно соответствуют листам графа G и две его вершины соединены ребром в том и только в том случае, когда соответствующая пар листов в G соединена мостом. Можно показать, что введенный таким образом граф является деревом, если исходный граф связен.

На рис. 5.4 граф G имеет 5 листов L₁, L₂, L₃, L₄, L₅ и 4 моста, а граф G' показывает, как связаны между собой листы графа G.

Приведем некоторые результаты о трехсвязных графах, которые будут использованы в главе «Планарность».

Пусть G-связный граф, H-некоторый его подграф. Простую открытую цепь. графа G назовем H-цепь, если выполняются условия

v₁VH, v_kVH, v_iVH, i=

ребро e=uv графа G также будем называть Н-цепь, если uVH, vVH, eEH.

Лемма 5.6. Пусть G-двусвязный граф. Тогда для всякого его подграфа Н, содержащего более одной вершины и отличного от G, существует Н-цепь графа G.

Доказательство

Если Н-остовный подграф, то любое ребро графа G, не входящее в EH, служит Н-цепью.

Пусть подграф не является остовным. Рассмотрим три попарно различные вершины uVH, vVH, wVH. По теореме 5.1 в графе G есть проcтая (u,v) - цепь, проходящая через w. Очевидно существование подцепи этой цепи, являющейся Н - цепью графа G. Доказано.

Ниже для u,vVG положим G_uv = G-u-v.

Теорема 5.7. Во всяком 3-связном графе G есть такое ребро uv, что граф G_uv не имеет точек сочленения.

Доказательство

Если |G|=n=4, то утверждение теоремы очевидно. Поэтому будем считать, что n5. Предположим противное, т.е. что для любого ребра uvEG граф G_uv имеет хотя бы одну точку сочленения. Тогда на 3-связности графа G следует, что при любом выборе ребра uvEG граф G_uv обладает следующими свойствами (рис. 5.5):

1) если а - висячая вершина графа G_uv, то avEG, auEG;

2) всякий висячий блок графа G_uv, не являющийся ребром, содержит такую пару вершин с и d, отличных от точек сочленения графа G_uv, что ucEG, vdEG.

3) всякий блок графа G_uv, имеющий ровно две точки сочленения и отличный от ребра, содержит такую вершину l, не являющуюся точкой сочленения графа G_uv, что или ulEG.

Обозначим через B_uv максимальный по числу вершин блок графа G_uv, а через t_uv- число вершин в этом блоке. Теперь выберем ребро uv так, чтобы число t_uv было наибольшим.

Покажем, что в этом случае t_uv3. Пусть t_uv=2 и а - висячая вершина графа G_uv (являющегося деревом). Так как n5, то существует ребро cdEG_uv. Из свойства 1) вытекает, что в графе G_cd существует цикл (u,a,v,u), т.е. t_cd>t_uv. Получено противоречие, следовательно, t_uv3.

Через D_uv обозначим bc-дерево графа G_uv и рассмотрим следующие случаи.

1. Дерево D_uv не является цепью. Выберем в этом дереве цепь, соединяющую пару висячих вершин и проходящую через вершину, соответствующую блоку B_uv. Этой цепи соответствует последовательность B₁,…,B_p блоков графа G_uv, среди которых содержится блок B_uv, причем блоки B₁ и B_p являются висячими (рис. 5.6).

Пусть B'- произвольный висячий блок графа G_uv, отличный от B₁ и B_p. Из свойств 1) и 2) вытекает существование таких отличных от точек сочленения графа G_uv вершин aVB₁, bVB_p, cVB', ucEG, vaEG, vbEG. Тогда в графе G_uc вершины множества входят в один блок и, следовательно, t_uv<t_uc. Последнее противоречит выбору ребра uv.

2. Дерево D_uv-цепь и B_uv-блок графа G_uv, не являющийся висячим. Пусть B₁,…,B_p - последовательность всех блоков графа G, причем блоки B₁ и B_p-висячие, B_iB_i+1Ш (i=), B_uv=B_k (1<k<p) (рис. 5.7). Cогласно свойству 3) найдется вершина bVB_uv отличная от точек сочленения графа G_uv, смежная с u или с v. Пусть ubEG. Согласно свойствам 1) и 2)

существует такие отличные от точек сочленения графа G_uv вершины aVB₁, cVB_p, что uaEG, vcEG. Легко видеть, что в графе G_vc имеется блок, содержащий все вершины множества . Поэтому t_vc>t_uv, и снова получаем противоречие.

3. Дерево D_uv - цепь и B_uv - висящий блок графа G_uv. Если граф G_uv содержит такое ребро xy, что VB_uv{x, y}=Ш, то, используя свойство 2), легко показать, что в графе G_xy есть блок, содержащий множество вершин VB_uv{x, y}, а, значит t_uv<t_xy. Так как B_uv - висячий блок графа

G_uv, то последнее означает, что граф G_uv состоит из блока B_uv и ребер ab₁,ab₂,…ab_l (рис 5.8). Из 3-связности графа G следует, что граф G - а не имеет точек сочленения. Поскольку в графе G- a вершина b₁ смежна только с вершинами u и v, a uvEG, то граф также не имеет точек сочленения, что противоречит предположению.

Таким образом, показано,что во всяком связном графе G существует такое ребро uv, что граф G_uv не имеет точек сочленения. Доказано.

Следствие 5.8. Всякий 3-связный граф с числом вершин n5 содержит ребро, стягивание которого приводит к 3-связному графу.

Доказательство также проведем от противного. Пусть, стягивая некоторое ребро x=uv 3-связного графа G в вершину , получаем граф G_x, для которого (G_x)=2 (Равенство (G_x)=1 невозможно в силу 3-связности графа G). Тогда в графе G_x существуют две вершины, удаление которых делают его несвязным. Одной из них должна быть (в противном случае (G_x)=2). Удалению вершины из G_x соответствует удаление вершины u и v из графа G. Поэтому для любого ребра x=uvEG граф G имеет такую вершину w, что граф G-u-v-w несвязен. Вершина w является точкой сочленения графа G_uv, что противоречит предыдущей теореме. Доказано.

Отметим без доказательства следующую теорему.

Теорема 5.9. Почти все ребра двусвязны.

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

Следствие 5.10. Почти все графы не содержат мостов.

2.3 Теорема Менгера

Из теоремы 5.1 следует, что 2-граф связен тогда и только тогда, когда любые две его несовпадающие вершины a и b соединены парой простых (a, b) цепей, не имеющих общих вершин, за исключением a и b. Аналогичный критерий k-связности справедлив при произвольном k.

Говорят, что множество вершин S разделяет несмежные вершины a и b связного графа G, если в графе G - S вершины a и b принадлежат различным связным компонентам. В этой ситуации множество S называют также сепаратором или (a, b)-сепаратором. Две (a, b)-цепи графа G называют непересекающимися, если у них нет общих вершин, за исключением a и b, и реберно-непересекающимися, если у них нет общих ребер. Очевидно, непересекающиеся цепи являются и реберно-непересекающимися, а обратно, вообще говоря, неверно.

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

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

Приведем доказательство принадлежащее В. Маквайгу (1982 г.).

Ясно, что если k вершин разделяют a и b, то существует не более k попарно непересекающихся (a, b)-цепей. Остается показать, что если в графе G нет множества, содержащего менее чем k вершин, разделяющих несмежные вершины a и b, то в нем имеется k попарно непересекающихся цепей. Используем индукцию по k. утверждение правильно при k=1. Предположим, что оно верно для некоторого k1. Рассмотрим граф G, в котором несмежные вершины a и b нельзя разделить множеством, содержащим менее чем k+1 вершин. По предположению индукции в G имеется k попарно непересекающихся (a, b)-цепей P₁, P₂, …, P_k. Рассмотрим множество вторых (считая а первой) вершин в этих цепях. Это множество состоит из k вершин и, следовательно, но оно не разделяет вершины a и b. Значит, имеется (a, b)-цепь Р, первое ребро которой не принадлежит ни одной из цепей P_i (i=). Пусть v-первая, считая от а, вершина Р, принадлежащая одной из P_i (i=), и пусть P_k+1 обозначает (a, v)-подцепь цепи Р. Цепи P₁, …, P_k, P_k+1 могут быть выбраны, вообще говоря, многими различными способами. Выберем их так, чтобы в графе G - a расстояние v до b было минимально. Если окажется, что v=b, то P₁, P₂, …, P_k+1 будет требуемым набором k+1 цепей. Допустим, что vb. Тогда в графе G - v вершины a и b нельзя разделить множеством, содержащим менее чем k вершин. По индуктивному предположению в этом имеется k непересекающихся (a, b) - цепей Q₁, Q₂, …, Q_k, которые могут быть выбраны разными способами. Выберем их так, чтобы множество

включало минимальное число ребер этих цепей. Иначе говоря, цепи Q_i должны состоять «в основном» из ребер цепей P_i. Рассмотрим теперь граф H, состоящий из вершин и ребер цепей Q₁, Q₂, …, Q_k и вершины v (эта вершина будет в графе H изолированной). Пусть P_r - одна из цепей P_i (i=), у которой ребро, инцидентно вершине а, не принадлежит EH. Ясно, что такая цепь среди P_i (i=) найдется, поскольку число их равно k+1, а цепей Q_i, составляющих H, только k. Пусть, далее, x-первая, считая от а, вершина P_r, входящая в VH.

Если x=b, то, добавив цепь P_r к Q₁, Q₂, …, Q_k, получим требуемый набор из k+1 (a, b) цепей. Допустим, что xb, и рассмотрим другие возможности для x.

Если x=v, то обозначим через R кратчайшую (v, b) - цепь и G - a. Пусть z - первая, считая от v, вершина цепи R, лежащая на некоторой Q_j (j=). Объединим цепь P_r c (v, z) - подцепью цепи R и обозначим полученную (a, z) - цепь через Q_k+1. Цепи Q₁, Q₂, …, Q_k, Q_k+1 обладают тем свойством, что расстояние в графе G - a от z до b меньше, чем расстояние от v до b, а это противоречит выбору P₁, P₂, …, P_k, P_k+1.

Рассмотрим теперь последнюю возможность: x принадлежит некоторой цепи Q_j (j=). В этом случае (a, x) - подцепь цепи Q_i имеет ребра в L, иначе бы две цепи в { P₁, P₂, …, P_k, P_k+1} пересекались в вершинах, отличных от a, b, v. Заменив теперь (a, x) - подцепь Q_i на (a, x) - подцепь P_r, получим непересекающиеся (a, b) - цепи в графе G - v, и эти цепи будут использовать меньше ребер из L, чем Q₁, …, Q_k. Снова получаем противоречие, которое и завершает доказательство теоремы.

Из теоремы Менгера непосредственно вытекает

Теорема 6.1. (Х. Уитни, 1932 г.). граф k-связен тогда и только тогда, когда любая пара его несовпадающих вершин соединена по крайне мере k непересекающимися цепями.

Имеется несколько аналогов и обобщений теоремы Менгера. Здесь мы остановимся на реберном варианте этой теоремы.

Во многих прикладных задачах приходится рассматривать множество ребер (а не вершин, как ранее), разделяющих вершины a и b графа G, т.е. такое множество ребер R, что входит в различные компоненты графа G - R. Минимальное относительно включения множество R с этими свойствами называется (a, b) - разрезом графа.

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

Доказательство этой теоремы легко получить, используя теорему Менгера. С этой целью сопоставим графу G граф G', который получается из G следующим образом. Каждая вершина vVG заменяется группой из deg v

попарно смежных вершин, а ребра графа G', соединяющие вершины из разных групп, находятся в биективном соответствии с ребрами графа G' (рис. 6.1). Если в графе G нет (a, b) - разреза, содержащего менее чем k ребер, то в G' нет множества, имеющего менее чем k вершин, разделяющего какую-либо пару вершин a', b' из групп, соответствующих a и b. Тогда по теореме Менгера вершины a', b' соединены в G' по крайней мере k вершинно-непересекающимися цепями, которым соответствует столько же реберно-непересекающихся (a, b) - цепей графа G.

С другой стороны, ясно, что граф, имеющий (a, b) - разрез из k ребер, может содержать не более k реберно- непересекающихся (a, b) - цепей.

3. Выделение k непересекающихся остовных деревьев 2k-реберно связном графе

Из классического результата теории графов - теоремы Менгера- известно, что для любых двух вершин x и y графа G локальная реберная связность (x, y, G) равняется наибольшему количеству непересекающихся по ребрам путей от x до y в графе G. Однако, при k>1 не во всяком графе G с реберной связностью (G)k существуют k непересекающихся по ребрам связных остовов. Из ранее известных результатов «глобальным ананлогом» теоремы Менгера в некоторой степени является доказанный результат: в графе G с реберной связностью (G)k существуют k остовных деревьев T₁, T₂, …, T_k такие, что для любого j от 1 до k объединение деревьев T₁, T₂, …, T_j дает j-реберно связный граф.

В настоящей работе мы рассматриваем еще один глобальный аналог теоремы Менгера: будет доказано, что при (G)2k в графе G существует k остовных деревьев, не имеющих общих ребер. Мы докажем необходимость условия (G)2k при k>1. Более того, мы построим примеры (2k-1)-связныцх графов, у котороых минимальная степень вешины больше любого заданного числа, но среди любых k связных остовов какие-то два имеют общее ребро.

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

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

Для произвольной вершины x графа G через d_G(x) мы будем обозначать степень вершины x в графе G(V, E). Для xV, AV через d_G(x, A) обозначим количество ребер, соединяющих вершину x с вершинами множества A (с учетом кратных ребер). Минимальную степень вершины в графе G будем обозначать через(G), a максимальную степень- через(G).

Пусть z-вершинa четной степени в графе G. Рассмотрим граф G-z, разобъем на пары все вершины, смежные в графе G с z и соединим вершины в парах. Полученный граф G^z назовем разрезом графа G по вершине z.

3.1 Построение k непересекающихся остовных деревьев

Теорема 7.1. Пусть граф G(V, E) таков что (G)=k, а вершина zV не является точкой сочленения. Тогда существует такой разрез G^z графа G по вершине z, что для любых x,yV\{z} выполняется соотношение (x, y, G^z)=(x, y, G) и, в частности (G^z) (G).

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