Компоненты связности

Связность

Def.Говорят, что вершина u достижима из v, если существует маршрут, соединяющий u и v.

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

Замечание. Учитывая свойство 1 маршрутов, в этих определениях слово “маршрут” можно заменить на “простая цепь”.

Теорема 2.3. (1-я теорема о связности) Для связности графа необходимо и достаточно, чтобы в нем какая-нибудь фиксированная вершина u была достижима из любой другой вершины.

Доказательство. Пусть вершина u достижима из любой другой вершины. Выберем две любые вершины v и w. Соединим v и u, а также w и u маршрутами. Объединив их, получим маршрут v, u, w, соединяющий вершины v и w. В силу произвольности v и w, теорема доказана.

Задание. Доказать, что отношение достижимости между двумя вершинами обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является эквивалентностью.

Так как отношение достижимости между двумя вершинами является эквивалентностью, то, по теореме о разбиении, вершины графа можно разбить на непересекающиеся классы V₁, …, V_k, и такие, что вершины, принадлежащие одному классу достижимы друг для друга, но не достижимы для вершин из любого другого класса.

Образуем подграфы G_i = (V_i, E_i), соединив вершины множества V_i ребрами из множества E_i Ì E. Очевидно – граф распался на связные подграфы, не имеющие общих вершин и ребер. Такие подграфы называются компонентами связности графа G. Геометрически они выглядят, как отдельные изолированные куски.

Теорема 2.4. (2-я терема о связности) Если в произвольном неориентированном графе ровно две вершины имеют нечетную степень, то они достижимы друг для друга.

Доказательство. Пусть в графе G только две вершины u и v имеют нечетную степень. По теореме 2.2. о нечетных степенях, в конечном графе число вершин с нечетными степенями четно. Пусть G_u – компонента связности, которой принадлежит вершина u. Так как теорема 2.2 применима и к G_u , то в ней кроме u должна быть еще хотя бы одна вершина с нечетной степенью. Но во всем графе всего одна такая вершина – это v. Следовательно, v Î G_u. Значит, u и v достижимы друг для друга, т.к. принадлежат одной компоненте связности. ЧТД.

Теорема 2.5. (3-я терема о связности) Для n-вершинного графа с m ребрами и k компонентами связности справедливо неравенство m ³ n – k.

Доказательство. Докажем индукцией по m. При m = 0 будет n = k, значит, неравенство выполняется.

Пусть m > 0 и для графов с меньшим числом ребер неравенство верно. Удалим из графа любое ребро. Тогда число его ребер станет m₁ = m – 1, а число компонент связности либо станет k + 1, либо останется равным k. Рассмотрим два случая.

1) Стало k + 1 компонент. Тогда по предположению индукции m₁ = m – 1 ³ n – (k + 1). Значит m ³ n – k.

2) Осталось k компонент. Тогда m₁ = m – 1 ³ n – k. Тем более m ³ n – k.

Теорема доказана.

Тема 3. Алгоритмы обхода вершин в графах общего вида