Вершин, ребер и компонент связности

Определение. Вершины A и B графа G = (V, E,) называются связанными, если существует путь из А в В.

Отметим, что можно считать этот путь цепью. Граф G называется связным, если любые его две вершины связанны.

Компонентой связности графа G = (V, E) называется любое связное непустое подмножество K ⊆ V, такое что не существует ребер с началом a ∈ K и концом b K.

Определение. Ребро графа G = (V, E,) называется мостом, если его удаление приводит к увеличению числа компонент связности. (при этом увеличение может быть только на

единицу).

Теорема. Пусть в графе G = (V, E) имеется ровно n вершин, m ребер и k компонент связности. Тогда m + k ≥ n.

Доказательство. Индукция по m. Пусть m = 0. Тогда k = n, и m + k = k = n ≥ n. Предположим, что теорема верна, если количество ребер равно m − 1, m > 0. Докажем теорему для m. Для этого удалим из G какое-нибудь ребро e. Получим граф G’ c m−1 ребром, n вершинами и k’ компонентами связности. При этом k’ − k ≤ 1. По предположению индукции имеем (m − 1) + k’ ≥ n. Тогда

m + k ≥ m + (k’ − 1) = (m − 1) + k’ ≥ n.