Задача остовных деревьев в k–связном графе (стр. 4 из 10)
Пусть 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– связный граф без мостов. Выберем в этом графе множество Е1, состоящее из
= (G) ребер, удаление которых приводит к несвязному графу. Пусть E2 
E1, |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–компонентами графа G1 
G2. легко заметить, что 2–компоненты графа G1 имеют одну большую вершину, а 3–компоненты графа G2–две общие вершины. Следующая теорема показывает, что это обстоятельство не случайно.
Теорема 4.2: Две различные к–компоненты графа имеют не более чем к–1 общих вершин.
Доказательство
Пусть G1 и G2 –различные k–компоненты графа G и VG1 
VG2=X. Предположим, что |X| 
k, и докажем, что тогда граф G1 
G2 должен быть к–связным. Для этого в данном случае достаточно показать, что он остается связным после удаления любых k–1 вершин, т.е. Y V(G1 G2), |Y|=k-1, то граф (G1 G2) – Y связен. Положим
Yi=(VGi\X) Y, i=1,2, Y3=X Y.
Ясно, что
|Yi| k–1, i=1,2,3, Y=Y1 Y2 Y3.
Поскольку
|Yi Y3| k–1, i=1,2,
и графы G1 и G2k–связны, то графы
Hi=Gi–(Yi Y3), i=1,2,
связны. Так как по предложению |X| k, то X\Y3 
Ø, т.е. связны графы H1 и H2имеют хотя бы одну общую вершину. Следовательно, связен граф H1 H2=(G1 G2)–Y. Последнее означает, что граф G1 G2k–связен. Поэтому, вопреки предположению, ни G1 не являются k–компонентами графа G.
§5 Двусвязные графы
Случаям, когда k=2 или k=3, в теории графов отведена особая роль. Это объясняется следующими причинами. Во–первых. 2– и 3–связные графы фигурируют во многих теоретических и прикладных вопросах, в частности, ряд задач достаточно уметь решать для 2–связных компонент. Во–вторых, при к=3 и, особенно, при к=2 удается дать в некоторой степени обозримое описание соответствующих графов.
Рассмотрим вначале некоторые простые свойства 2–связных графов, вытекающие непосредственно из определений: