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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Глава 1. Основные понятия теории графов 17
Рассмотрим граф на рис. 1.19 с точкой сочленения C. Удалив эту
вершину, получим несвязный граф.
С
χ
()=1
G
Рис. 1.19
Однако чтобы этот граф стал несвязным путем удаления ребер,
надо в нем удалить не менее трех ребер. Числом реберной связности
λ(G) называется наименьшее число ребер, удаление которых приво-
дит к несвязному графу. Для любого графа G верны неравенства
χ(G) ≤ λ(G) ≤ δ(G), где δ(G) – минимальная степень вершин графа G.
Граф связен, если любые две его вершины соединены цепью. Ес-
ли в произвольном графе G вершина x
i
связана с x
j
, а x
j
связана с x
k
,
то x
i
связана с x
к
. Тогда, если V
i
есть множество вершин G, связан-
ных с вершиной x
i
, то множество вершин графа G, которое обозна-
чим через V, можно представить в виде попарно не пересекающихся
подмножеств [2]
i
i
VV=
∪
.
Соответственно
i
i
GG=
∪
,
где G
i
– связные непересекающиеся подграфы G.
Если число таких подграфов P, то, говорят, что G имеет P компо-
нент связности. Любой граф можно рассматривать как совокуп-
ность связных графов. Всякий максимально связный подграф графа
G называется компонентой связности графа G.
Например, графы на рис. 1.16 имеют соответственно одну и две
компоненты связности.
Утверждение 1.5. Граф G связен тогда и только тогда, когда он
состоит из единственной компоненты связности.

Страницы