Связность графа

Понятие цепи

Связность в графах

Пусть - некоторый граф. Последовательность попарно инцидентных между собой вершин и ребер графа называется цепью.

и - концевые вершины цепи.

Длина цепи - число ребер, образующих цепь (и - концевые вершины цепи).

Цепь называется составной, если она содержит повторяющиеся ребра. Цепь называется сложной, если она содержит повторяющиеся вершины за исключением, быть может, первой и последней. Цепь, которая не является ни составной, ни сложной называется простой. Цепь называется циклом, если концевые вершины цепи совпадают. Циклы также бывают простые, составные и сложные. - простой цикл, состоящий из ребер. Пусть и - некоторые вершины графа. Тогда расстояние между вершинами . Введенное таким образом понятие расстояния является метрикой на графах:

1) ;
2) ;
3) .

Диаметром графа называется величина .

Пример

(целая часть числа).

Говорят, что две вершины и связны, если существует простая цепь, в которой и являются концевыми вершинами. Граф называется связным, если любые две вершины его связны. Минимальное количество вершин графа, удаление которых делает граф несвязным (или тривиальным) называется вершинной связностью графа. Обозначается . Минимальное количество ребер графа, удаление которых делает граф несвязным (или тривиальным) называется реберной связностью графа. Обозначается .

Примеры

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

Теорема
Для любого графа .