Математическое моделирование на графах. Часть 1. Берцун В.Н. - 16 стр.

UptoLike

Составители:

Рубрика:

16 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1

1.4. Компоненты связности графа

Точкой сочленения связного графа называется вершина, после

удаления которой граф становится несвязным (ребро с таким же

свойством называется мостом). Неразделимым графом называется

связный, непустой, не имеющий точек сочленения граф. Блок графа

– это максимально неразделимый подграф. На рис. 1.17 граф имеет

две точки сочленения, мост и четыре блока.

D С Х

, – точки сочленения, – мост

Блоки

Рис. 1.17

Вершинной связностью χ графа G называется наименьшее число

вершин, удаление которых приводит к несвязному или тривиально-

му (одновершинному) графу. Следовательно, связность несвязного

графа χ = 0, связность связного графа с точкой сочленения χ = 1. Ес-

ли в полном графе K

удалить n – 1 вершину, то получим тривиаль-

ный граф, поэтому для такого графа χ = n – 1. Для простого цикла

всегда χ (C

) = 2. На рис. 1.18 для полного графа K

и простого цикла

вершинная связность χ(K

) = 3, χ(C

) = 2.

Рис. 1.18