Число компонент связности дерева

§9. Метрические характеристики графа

Пусть G = (S, U) – связный граф и x_i, x_j – две его произвольные вершины.

Определение 9.1. Расстоянием d(x_i, x_j) между вершинами x_i и x_j называется длина кратчайшего маршрута, соединяющего эти вершины.

Из определения 9.1 непосредственно следует:

Определение 9.2. Эксцентриситетом вершины x называется величина

e(x) = (9.1)

Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удалëнной от неë.

Определение 9.3. Диаметром d(G) графа G называется максимальный из всех эксцентриситетов вершин графа G, т.е.

Определение 9.4. Вершина x называется периферийной, если e(x) = d(G).

Определение 9.5. Диаметральной цепью называется простая цепь, расстояние между концами которой равно d(G).

Теорема 9.1. Для любого связного графа G справедливо неравенство

d(G)  rank G. 

Определение 9.6. Радиусом r(G) графа G называется минимальный из всех эксцентриситетов вершин графа G, т.е.

Определение 9.7. Вершина x называется центральной, если e(x) = r(G).

Определение 9.8. Множество всех центральных вершин графа называется его центром.

Заметим, что центр может состоять как из одной, так и из нескольких вершин.

Пример 9.1. Найти эксцентриситеты вершин, радиусы и диаметры графа G, изображëнного на рис. 16, периферийные и центральные вершины. Привести

пример диаметральной цепи.

Р ешение. Найдëм эксцентриситеты всех вершин G: e(x₁) = e(x₄) = e(x₅) = 4,

e(x₂) = e(x₆) = e(x₇) = e(x₈) = 3, e(x₃) = 2.

Следовательно, d(G) = 4, r(G) = 2. Получаем, что вершины x₁, x₄ и x₅ являются периферийными, а вершина x₃ – центральной. Одной из диаметральных цепей является

x₁ – x₇ – x₃ – x₆ – x₅. 

§10. Деревья и их свойства. Лес

Определение 10.1. Любой связный неорграф, не содержащий циклов, называется (неориентированным) деревом.

Определение 10.2. Любой неорграф без циклов называется лесом, или ациклическим графом.

Таким образом, компонентами связности любого леса являются деревья.

На рис. 17 показан лес, состоящий из двух деревьев.

Свойства деревьев сформулируем в виде следующей теоремы.

Теорема 10.1. Пусть G = (S, U) и = n, = m. Тогда следующие условия эквивалентны:

1. G – дерево;
2. G – связный граф и m=n1;
3. G – ациклический граф и m=n1;
4. любые две различные вершины графа соединяет единственная простая цепь;
5. G – ациклический граф, такой, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл. 

Теорема 10.2 (Кэли). Число деревьев с n занумерованными вершинами равно . 

Определение 10.3. Ориентированным деревом (ордеревом) называется

орграф G = (S, U), удовлетворяющий следующим двум условиям:

1. существует единственная вершина x_iS, называемая корнем, не имеющая предшествующих вершин (т. е. );
2. любой вершине x_j, отличной от x_i, в орграфе G непосредственно предшествует ровно одна вершина (т. е. ).

Определение 10.4. Узлом ордерева называется вершина, отличная от корня.

Определение 10.5. Листом ордерева называется вершина x такая, что и

Определение 10.6. Ветвью ордерева называется путь из корня в лист.

Определение 10.7. Высотой ордерева называется длина его наибольшей ветви.

Определение 10.8. Уровнем вершины ордерева называется расстояние от корня до этой вершины.

Отметим, что корень имеет уровень 0.

Определение 10.9. Ярусом ордерева называется множество вершин одного уровня.

Замечание 10.1. Неориентированное дерево можно преобразовать в ориентированное, выбрав в качестве корня произвольную вершину. На рис. 18 корень графа – вершина x₇. 

П ример 10.1. Рассмотрим ордерево, изображëнное на рис. 18. Тогда: все вершины, кроме x₇, являются узлами ордерева; вершины x₁, x₅, x₈, x₁₀, x₁₁, x₁₂ – листами; путь x₇  x₆  x₃  x₂  x₁₀ – одна из ветвей; высота ордерева равна 5; множество вершин x₁, x₅, x₉, x₁₀> уровня 4 образует один из ярусов ордерева. 

Определение 10.10. Остовом неорграфа G = (S, U) называется его часть G = (S, U), такая, что S = S и G – лес, образующий дерево на любой связной компоненте графа G.

Из определения 10.10 следует, что если G – связный неорграф, то остов G является деревом, которое будем называть остовным деревом графа G.

Определение 10.11. Остовом орграфа G называется его часть G, такая, что ассоциированный с G неорграф F(G) является остовом графа F(G).

Понятие остовного дерева для связного орграфа вводится аналогично.

Замечание 10.2. 1) В каждом графе существует остов, который можно получить, разрушая в каждой связной компоненте циклы, т.е. удаляя лишние рëбра.

2) Остов графа определяется неоднозначно. 

П ример 10.2. На рис. 19 изображены неорграф G и один из его остовов G. 

Для подсчета числа остовов в неорграфе используется матрица Кирхгофа.

Теорема 10.3 (Кирхгофа). Число остовных деревьев в связном неорграфе G порядка n  2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа. 

Из определения дерева вытекает следующая теорема.

Теорема 10.4. Пусть G = (S, U) – произвольный неорграф, = n, = m , k – число компонент связности графа G. Число рëбер, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m – n + k.

Доказательство. Пусть i-я компонента связности G_i содержит n_i вершин и m_i рëбер. По условию G – связный граф. Следовательно, остов G_i графа G_i является деревом, а значит, он содержит (n_i – 1) ребро. Таким образом, для получения остова G_i из i-й компоненты связности G_i требуется удалить m_i – (n_i – 1) ребер.

Просуммируем удаляемые ребра по всем компонентам связности, учитывая, что Получим 

Определение 10.12. Число  (G) = m  n + k называется цикломатическим числом или циклическим рангом графа G.

Определение 10.13. Число *(G) = n  k называется коциклическим рангом или корангом.

Таким образом, *(G) равно числу рëбер, входящих в любой остов графа G. Очевидно, что  (G) +*(G) = m.

Из теоремы 10.4 непосредственно вытекают два следствия.

Следствие 10.4.1. Неорграф G является лесом тогда и только тогда, когда

Следствие 10.4.2. Неорграф G имеет единственный цикл тогда и только тогда, когда  (G) =1. 

Пример 10.3. Найти для графа G, изображенного на рис. 19, цикломатическое число и коциклический ранг.

Решение. Граф G имеет 8 вершин, 14 ребер и 1 компоненту связности. Тогда, согласно по теореме 10.4, цикломатическое число  (G) = 14 – 8 +1 = 7, а коциклический ранг *(G) = 8 – 1 = 7 . 

Источник

Поиск компонент связности

Компонентой связности неориентированного графа называется подмножество вершин, достижимых из какой-то заданной вершины. Как следствие неориентированности, все вершины компоненты связности достижимы друг из друга.

Дан неориентированный граф $G$ с $n$ вершинами и $m$ рёбрами. Требуется найти в нём все компоненты связности, то есть разбить вершины графа на несколько групп так, что внутри одной группы можно дойти от одной вершины до любой другой, а между разными группами путей не существует.

Для решения задачи модифицируем обход в глубину так, чтобы запустившись от вершины какой-то компоненты, от пометил все вершины этой компоненты — то есть все достижимые вершины — заданным номером этой компоненты. Для этого можно массив used заменить массивом номеров компонент для каждой вершины, изначально заполненный нулями:

  Теперь проведем серию обходов: сначала запустим обход из первой вершины, и все вершины, которые он при этом обошёл, образуют первую компоненту связности. Затем найдём первую из оставшихся вершин, которые ещё не были посещены, и запустим обход из неё, найдя тем самым вторую компоненту связности. И так далее, пока все вершины не станут помеченными.

Записывается это очень компактно:

После этого переменная num будет хранить число компонент связности, а массив component — номер компоненты для каждой вершины, который, например, можно использовать, чтобы быстро проверять, существует ли путь между заданной парой вершин.

Итоговая асимптотика составит $O(n + m)$, потому что такой алгоритм не будет запускаться от одной и той же вершины дважды, и каждое ребро будет просмотрено ровно два раза (с одного конца и с другого).

Источник

3.9. Деревья и леса

Каждая компонента связности леса – дерево, следовательно, для -связного леса существует дизъюнктное разбиение на деревьев.

Пример 1. Граф не является деревом, не является лесом. Граф — дерево. Граф — лес.

Лемма. Если граф – дерево, то каждое его ребро является мостом.

Доказательство.В параграфе 3.6 было доказано, что если ребро графа не содержится ни в одном цикле, то оно является мостом. Дерево граф ациклический, следовательно, каждое его ребро мост.■

Теорема (основная теорема о деревьях). Для графа следующие утверждения равносильны:

1. Граф— дерево.
2. ациклический и.
3. связный и.
4. связный и каждое его ребро является мостом.
5. Любые две вершины графаможно соединить, притом единственной, простой цепью.
6. ациклический, и добавление к нему нового ребра приводит к образованию единственного простого цикла.

Доказательство.Доказательство проведем по следующей схеме:. . Индукцией по числу ребер проверим, что для любого дерева выполняется равенство. Базис индукции.Пусть, тогда, и равенствовыполнено. Индуктивный переход.Предположим, что требуемое равенство выполняется для любого дерева с числом ребер меньшим либо равным. Докажем, что оно справедливо и для дерева с числом ребер. Удалим из графапроизвольное ребро .Согласно лемме, ребро — мост. По теореме о мостах. Следовательно, графсостоит из двух компонент связности,и , каждая из которых – дерево с числом ребер меньшим либо равным. Для каждой компоненты связности справедливо предположение индукции, т.е. выполнены равенстваи. Складывая эти равенства почленно, получим:. Или. . Докажем, что если граф ациклический и, то граф связный. Будем рассуждать от противного, т.е. предположим, что найдется ациклический граф, число ребер которого на единицу меньше числа вершин, который связным не является. Пусть,, — число компонент связности графа. Каждая компонента связности — дерево. Переходуже доказан, следовательно, для каждой компоненты связностиможем записать:. Просуммировав по, получим: . Или . Так как , то пришли к противоречию с условием. Следовательно, наше предположение было неверным. . Докажем, что если граф связный и, то каждое его ребро является мостом. Будем рассуждать от противного. Предположим, что найдется связный граф, такой что, в котором есть ребро , не являющееся мостом. Тогда графсвязный и . То есть для связного графа выполняется условие, что противоречит следствию теоремы о знаке цикломатического числа (см. параграф 3.7). . Из связности графа вытекает, что любые две его вершины можно соединить маршрутом, и, следовательно, простой цепью. Докажем, что эта простая цепь единственна. Доказательство проведем от противного. Предположим, что найдется связный граф, все ребра которого — мосты, такой, что в нем есть две вершиныи , соединенные двумя различными простыми цепямии. Поскольку цепииразличны, то имеется ребро , входящее в цепьи не входящее в цепь. Пусть и— фрагменты цепи. Склеим инвертированный фрагмент, цепьи инвертированный фрагмент. Получим на графе— маршрут, не содержащий ребра . Из этого маршрута выделим-простую цепь и склеим ее с цепью . В результате получим цикл, содержащий , а это противоречит тому, что ребро — мост. . Пусть для графавыполнено условие 5. Проверим сначала, что граф не содержит циклов. Будем рассуждать от противного. Предположим, что на графеимеется цикл. Пусть — одно из ребер этого цикла и вершиныи — концы этого ребра. Тогда— простая цепь, соединяющая вершиныи . Обозначим ее. Удалим из графаребро . Поскольку ребра циклов не являются мостами и графсвязный, то графтакже будет связным. Следовательно, на графесуществует— маршрут. Выделим из этого маршрута-простую цепь и обозначим ее. Таким образом мы показали, что на графеесть две простые цепи, соединяющие вершиныи :и, что противоречит условию 5. Покажем, что добавление к графу нового ребра приводит к образованию, притом единственного, цикла. Возьмем на графедве произвольные вершиныи и соединим их новым ребром; получим граф. По условию на графе имеется единственная простая-цепь. Склеив ее с цепью, получим на графепростой цикл. Докажем, что этот цикл единственный. Предположим, что при добавлении ребраобразовалось два простых цикла. Тогда, удалив из каждого из них ребро, получим на графедве простые-цепи, а наличие двух -цепей противоречит условию. . Будем рассуждать от противного, т.е. предположим, что существует несвязный граф, для которого выполнено условие 6. Возьмем на этом графе две вершины, лежащие в разных компонентах связности, и соединим их ребром. В результате образуется граф, для которого реброявляется мостом и, следовательно, не содержится ни в одном цикле. Таким образом, добавление ребране привело к образованию цикла, что противоречит условию 6.■ Следствие 1.Неодноэлементное дерево имеет не менее двух висячих вершин.Доказательство.Рассмотрим произвольное дерево, имеющее не менее двух вершин. Представим множество его вершинв виде, где— множество висячих вершин этого дерева. Тогда . Но , поэтому . Откуда . ■ Следствие 2.Если граф—-связный лес, то. Последнее следствие рекомендуем доказать самостоятельно.

Источник