Мосты. Связный граф. Компоненты связности графа. Цикломатическое число графа. Расстояние между вершинами в графе. Эксцентриситет вершины. Радиус и диаметр графа.

Граф называется связным, если любая пара его вершин - связная. Граф называется несвязным, если в нём есть хотя бы одна несвязная пара вершин.

Неориентированный граф называется связным, если между любыми двумя его вершинами есть маршрут.

На рис несвязный граф.

Если провести ребро ДЕ, то граф станет связным. ДЕ –называется мостом.

Ребро (V,W) связного графа G называется мостом, если после его удаления граф G станет несвязным и распадется на два связных графа G^/ и G^//.

Граф G можно разбить на непересекающиеся множества V_i по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств – несвязны. Тогда все подграфы V_i (классы эквивалентности) графа G называют связными компонентами, или компонентами связности. Связный граф имеет одну компоненту связности.

Несвязный граф распадается на несколько частей, каждая из которых является связным графом.

Эти части называются компонентами связности.

Компонентой связности неориентированного графа G(V,Х) называется его подграф G^/(V^/,Х) с множеством вершин и множеством рёбер Х, инцидентных только вершинам из множества V^/ , причем ни одна вершина из не смежна с вершинами из множества V^/∩V. Несвязный граф состоит из нескольких отдельных подграфов – компонент связности, т.е. связных графов.

Связный граф состоит из одной компоненты смежности.

Цикломатическим числом графа G называется число

ν(G) = m(G)+c(G)- n(G),

где m(G) – число его ребер; c(G) – число связных компонент графа; n(G) – число вершин графа.