Так, например, ( 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₃ =X Y.

Ясно, что

|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_i Y₃ ), i=1,2,

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