11. Связные графы и компоненты связности. Неравенство между количеством

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

Определение. Вершины 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.

12. Эйлеровы и гамильтоновы пути. Критерий существования эйлерового пути.

Определение. Пусть дан граф G = (V, E,) и количество ребер равно m . Эйлеровым путем называется замкнутый путь длины m состоящий из различных ребер без повторений. Если условие замкнутости убрать, то получим определение полуэйлерового пути.

Определение. Пусть дан граф G = (V, E,) и количество вершин равно n . Гамильтоновым путем называется замкнутая цепь длины n. Если условие замкнутости убрать, то получим определение полугамильтонового пути.

Теорема. Связный граф имеет эйлеров путь тогда и только тогда, когда степени всех вершин четны.

Теорема. Связный граф имеет полуэйлеров путь тогда и только тогда, когда имеется только две вершины с нечетными степенями.

Доказательство. Предположим граф содержит эйлеров цикл. Пройдем по этому циклу, тогда вершина посещенная k раз (за исключением начальной) должна иметь степень 2k , так как при каждом посещении по одному ребру входим и по одному выходим, увеличивая степень вершины на 2. Для начальной вершины, при первом посещении только выходим по некоторому ребру, а при последнем только входим, следовательно, степень будет равна 2(k − 1).

Пусть степени всех вершин чётны. Рассмотрим цепь максимальной длины: C = v0e0v1e1 . . . ekvk+1.

Все ребра инцидентные vk+1 уже встречаются в этой цепи, иначе её можно было бы

продолжить. По предположению, число таких ребер четно, следовательно vk+1 =v0 , так как ek инцидентно vk+1 , а все остальные вхождения vk+1 увеличивают степень вершины на 2. Предположим, что C не эйлеров цикл. Тогда существует ребро e’ не принадлежащее циклу C . Eсли e’ не инцидентно никакой вершине цикла C , то рассмотрим путь соединяющй, например, вершину v0 и один из концов ребра e’ и выберем первое ребро e не принадлежащее циклу C . Тогда это рeбро

ицидентно некоторой вершине vi цикла, и пусть имеет вид e = {vi, u}.

Тогда цепь C’ = ueviei. . . ekvk+1e0v1, . . . vi−1ei−1vi имеет длину большую чем C , что противоречит выбору C .