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

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

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

      Граф , представленный на рис. 4.26, связен, но он перестает быть связным, если удалить вершину 4. Поэтому .

      Можно нарушить связность графа, удаляя некоторые его ребра (дуги). У графа  (рис. 4.26) для этого придется удалить не менее трех ребер. Например, граф  распадается на две компоненты после удаления ребер  4&5, 4&6, 4&7.

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

      Выше мы показали, что для графа  (рис. 4.26) .

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

      Ребро  графа  называется мостом, если его удаление увеличивает число компонент связности графа.

      Таким образом, точки сочленения и мосты - это своего рода «узкие места» графа.  Граф на рис. 4.27 имеет три точки сочленения - это вершины , , , и один мост - ребро .

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

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

На рис. 4.28 показаны блоки , ,  графа на рис. 4.26.

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

Теорема 4.6. Для любого графа  справедливы неравенства:

.

Граф  называется k-связным, если , реберно- k-связным, если .

      Граф , изображенный на рис. 4.26, 1-связен и реберно-3-связен.