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

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

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

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

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


Глава I

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


Вз1 Определения.

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

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

G=G(V)(1.1)

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

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

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

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

(v1,v2), v1V1, v2V2.

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

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

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

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

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

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

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

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

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

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

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

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

U=U(V), (1.3)

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

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

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

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

L=(a, a). (1.4)

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

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

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

Ei=(a, b)i, (1.5)

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

Ei=(a, b)i, =(a, b)j,

(рис. 1.7).

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

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

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

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

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


Вз2. Матрицы смежности и инцидентности.


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

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

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

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

Графы могут быть также описаны матрицами другого вида. Всякий граф состоит из объектов двух типовтАУвершин и ребер. Можно построить матицу M1(G), строки которой соответствуют вершинам, а столбцытАУребрам. На месте (а, Е) в этой матрице поместим значение =1, если атАУначальная вершина ребра Е, значение =-1, если атАУконечная вершина, и =0, если а не инцидентно Е. Если GтАУнеориентированный граф, то можно использовать только значения =1 и =0. Эта матрица M1(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) середина eE ребра Е соединяется ребрами с (е)тАУ1 серединами остальных ребер из G, имеющих конец в е. Таким образом, вI(G) эти новые ребра образуют новый граф U(e) с(е) вершинами. В I(G) вершина eE соединяется ребрами также с (е’)тАУ1 серединами остальных ребер из G, из имеющих конец в e’, и эти новые ребра образуют другой полный граф U(e’). Два графа U(e) и U(e’) имеют ровно одну общую вершину, именно вершину eE, определяемую единственным ребром Е, соединяющим e и e’. Таким образом, I(G) имеет такое непересекающееся по ребрам разложение

I(G)= 2.1

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

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


Вз3 Деревья

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

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

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

  1. G тАУ дерево;

  2. G тАУ связный граф и m=-1;

  3. G тАУ ациклический граф и m=-1;

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

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

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

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

mi=i-1. (1)

Далее имеем

m=m1+m2+1=(n1-1)+(n2-1)+1=(n1+n2)-1=n-1.

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

3) 4) Пусть ктАУчисло компонент графа G. Пусть, далее, компонента Тi является (i, mi)тАУграфом. Так как ТiтАУдерево, то верно равенство (1). Теперь имеем

-1=m=m1+m2+тАж+mk=(1-1)+(2-1)+тАж+(k-1)=(1+тАж+k)-k=-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. В любом дереве порядка 2 имеется неменее двух концевых вершин.

Пусть

d1, d2, тАж, d (2)

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

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

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

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

Если (1, m1)тАУграф Н является одной из компонент графа G, то для превращения ее в остове дерево нужно удалить m1-(1-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, то для любого ребра е1 графа S существует такое ребро е2 графа Т, что граф также является остовом.

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

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

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

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

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

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

Глава II

Связность


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


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


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

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

Так, например, (K1)=0, (K)=тАУ1, (C)=2.

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

Граф 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, , c и один мост ab.

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

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

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

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

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

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

(G).


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

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

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

Это определение иллюстрируется на рис. 4.3. На этом рисунке граф G1 имеет две 2тАУкомпоненты, а G2тАУдве 3тАУкомпоненты. Сами графы G1 и G2

являются 1тАУкомпонентами графа G1G2. легко заметить, что 2тАУкомпоненты графа G1 имеют одну большую вершину, а 3тАУкомпоненты графа G2тАУдве общие вершины. Следующая теорема показывает, что это обстоятельство не случайно.

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

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

Пусть G1 и G2 тАУразличные kтАУкомпоненты графа G и VG1VG2=X. Предположим, что Xk, и докажем, что тогда граф G1G2 должен быть ктАУсвязным. Для этого в данном случае достаточно показать, что он остается связным после удаления любых kтАУ1 вершин, т.е. YV(G1 G2), |Y|=k-1, то граф (G1 G2) тАУ Y связен. Положим

Yi=(VGi\X) Y, i=1,2, Y3=XY.

Ясно, что

|Yi|kтАУ1, i=1,2,3, Y=Y1Y2Y3.

Поскольку

YiY3kтАУ1, i=1,2,

и графы G1 и G2kтАУсвязны, то графы

Hi=GiтАУ(YiY3), i=1,2,

связны. Так как по предложению Xk, то X\Y3Ш, т.е. связны графы H1 и H2имеют хотя бы одну общую вершину. Следовательно, связен граф H1H2=(G1G2)тАУY. Последнее означает, что граф G1G2kтАУсвязен. Поэтому, вопреки предположению, ни G1 не являются kтАУкомпонентами графа G.


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


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

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

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

  2. если графы G1 и G2 2тАУсвязны и имеют не менее двух общих вершин, то граф G1G2 также 2тАУсвязен;

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

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

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

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

  1. граф 2тАУсвязен;

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

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

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

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

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

1)2). Пусть a и тАУдве вершины графа 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-

Вместе с этим смотрят:


"Инкарнация" кватернионов


* Алгебры и их применение


*-Алгебры и их применение


10 способов решения квадратных уравнений


Cпособы преобразования комплексного чертежа, применение при изображении предметов