Вершинная и реберная связность
Числом вершинной связности (или просто числом связности)
(каппа)
графа
называется наименьшее число вершин,
удаление которых приводит к несвязному
или одновершинному графу. Если граф
несвязный, то
.
Граф
связен, но его связность можно нарушить,
удалив вершину 3. Поэтому
.
Если же попытаться нарушить связность этого графа путем удаления ребер (а не вершин), то придется удалить не менее двух ребер. Введем еще одно определение.
Пусть – граф порядка
.
Числом реберной связности
графа
назовем наименьшее число ребер, удаление
которых приводит к несвязному графу.
Число реберной связности будем считать
равным 0, если этот граф одновершинный
или несвязный.Вершина графа называется точкой сочленения (или разделяющей вершиной), если граф
имеет больше компонент связности, чем
.Аналогично, ребро графа называется мостом, если его удаление увеличивает число компонент связности.
Т.о., точки сочленения и мосты графа – это своего рода «узкие места» графа.
Граф имеет 2 точки сочленения (4,5) и 3 моста {3,4}, {4,5}, {5,6}.
Для любого графа верны неравенства:
,
– минимальная степень вершин графа.
Без доказательства.
Двусвязные графы
Неориентированный граф называется двусвязным, если он связен и не содержит точек сочленения.
Произвольный максимально возможный двусвязный подграф графа называется компонентой двусвязности или блоком этого графа.
Данный граф содержит 6 блоков.
Неориентированный граф называется реберно-двусвязным, если он связный и не содержит мостов.
Произвольный максимально возможный реберно-двусвязный подграф графа называется листом этого графа.
Связность в орграфах
В неориентированном графе две вершины либо связаны, либо несвязаны. В ориентированном графе отношение связанности несимметрично.
Пусть
- орграф,
и
- его вершины. Говорят, что две вершины
и
сильно связаны в орграфе
,
если существует путь (ориентированная
цепь) из
в
и из
в
.Говорят, что две вершины и односторонне связаны в орграфе , если существует путь (ориентированная цепь) либо из в , либо из в .
Говорят, что две вершины и слабо связаны в орграфе , если они связаны в графе
,
полученном из
отменой ориентации ребер.Если все вершины в орграфе сильно (односторонне, слабо) связаны, то орграф называется сильно (односторонне, слабо) связанным.
Очевидно, что сильная связанность влечет одностороннюю связанность, которая влечет слабую связанность. Обратное неверно.
Слева направо: сильная, односторонняя, слабая связанность.
Компонентой сильной связности (КСС) орграфа - это его максимально сильно связные подграфы.
Каждая вершина графа принадлежит только одной КСС. Если вершина не связана с другими, то считаем, что она сама образует КСС.