Замечание: Несвязный граф можно всегда представить как объединение связных компонент. Эти компоненты можно рассматривать независимо.
Вершина графа называется точкой сочленения, если ее удаление увеличивает число компонент связности.
В любом нетривиальном графе есть, по крайней мере, две вершины, которые не являются точками сочленения.
Теорема: Пусть р – число вершин, q – число ребер, k – число компонент связности графа. Тогда (p-k) ≤ q ≤ (p-k)(p-k+1) / 2.
Следствие: Если q > (p-1)(p-2) / 2, то граф связен.
Мостом называется ребро, удаление которого увеличивает число компонент связности.
Рассмотрим рисунок:
w c d
b e f
u, v – точки сочленения, х – ребро-мост, awb, buw, awub, cdv, evf – блоки.
Блоком называется связный граф, не имеющий точек сочленения.
Если в графе есть мост, то есть и точка сочленения. Концы всякого моста кроме висячих вершин являются точкой сочленения, но не всякая точка сочленения является концом моста.
Вершинной связностью графа G (обозначается x(G)) называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.
|
|
Пример:
æ(G) = 0, если G несвязен;
æ(G) = 1, если G имеет точку сочленения;
Граф G называется k-связным, если æ(G) = k.
Реберной связностью графа G (обозначается A(G)) называется наименьшее число ребер, удаление которых приводит к несвязному или тривиальному графу.
Пример:
λ(G) = 0, если G несвязен;
λ(G) = 1, если G имеет мост;
λ(Кр) = р-1, значит, граф Кр – полный.