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

Связность и компоненты графа

Две вершины графа называют связанными, если между ними существует путь. Любая вершина по определению связана сама с собой.

Неорграф называется связным, если любая пара вершин в нем связана. Орграф называется связным, если соответствующий ему неорграф связен. Орграф называется сильно-связным, если для любой пары несовпадающих вершин v_i и v_j существуют оба маршрута (v_i ‑ v_j) и (v_j ‑ v_i).

Бинарное отношение связности в неорграфе (сильной связности в орграфе) является отношением эквивалентности на множестве вершин, поскольку оно рефлексивно, симметрично и транзитивно. И по теореме о разбиении множества на классы эквивалентности, множество вершин графа можно разбить на такие непересекающиеся подмножества, что в каждом из этих подмножеств вершины будут попарно связаны между собой и не связаны с вершинами никаких других подмножеств. Вершинно-порожденные подграфы каждого из подмножеств в этом разбиении называются компонентами графа (сильными компонентами в орграфе). Таким образом, справедливо следующее утверждение: любой неорграф разбивается единственным образом на попарно непересекающиеся компоненты (или, как говорят, в прямую сумму своих компонент, а орграф – в прямую сумму сильных компонент).

На рисунке 26 изображены два графа: неорграф (слева) связным не является и состоит из четырех компонент – , , и . Орграф (справа) связен, но не сильно-связен, имеет три сильные компоненты – , и .

1) Связный граф состоит из одной компоненты, а число компонент в несвязном графе всегда больше единицы.

2) Изолированная вершина является компонентой.

3) В связном графе любые два пути максимальной длины имеют общую вершину.

4) Удаление циклического ребра не нарушает связности графа.

Связный граф без циклов называется деревом. Граф, каждая компонента которого является деревом, называется лесом. На рисунке 27 изображен лес, состоящий из двух деревьев.

Теорема 3.9.1. (Оценка числа ребер в простых графах)

Пусть G =(V, E) – простой граф с в вершинами и k компонентами. Тогда число его ребер р удовлетворяет неравенству:

Доказательство: 1) рассмотрим левую часть неравенства. Если граф связен, то число его компонент k равно 1. Удалим из графа все циклические ребра, в результате этого будет получено дерево. Дальнейшее удаление ребер из дерева будет нарушать связность. Поэтому среди всех связных простых графов дерево имеет наименьшее число ребер. Но число ребер в дереве равно максимальной длине пути, построенного на в вершинах, и по свойствам путей равно (в ‑1). Тем самым, в связном графе число ребер р ³ в ‑1, что совпадает с оценкой снизу при k =1. Пусть теперь G несвязный граф. Тогда он разбивается на k связных компонент, для каждой из которых число ребер р_i ³ в_i ‑1, где i =1,2,¼, k и р_i, в_i – это число ребер и вершин в i‑ ой компоненте. Но и , а . Поэтому р ³ в‑k, и левая часть неравенства доказана.

2) Теперь рассмотрим правую часть неравенства (оценку сверху). Если граф связен, то добавим к нему новые ребра, соединяя все пары несмежных вершин. В результате этого будет получен полный граф. Дальнейшее добавление ребер к полному графу будет нарушать его простоту. Поэтому среди всех связных простых графов полный граф имеет наибольшее число ребер. Для подсчета этого числа воспользуемся теоремой о степенях вершин в графе. Поскольку каждая вершина полного графа смежна со всеми остальными его вершинами, то степень каждой вершины равна (в‑ 1), а сумма степеней всех вершин равна в ×(в ‑1). По теореме о степенях вершин это число равно удвоенному числу ребер, поэтому число ребер в полном графе равно . И число ребер в связном графе р £, что совпадает с оценкой сверху при k =1. Пусть теперь G – несвязный граф. Тогда число ребер в каждой i‑ ой компоненте р_i £. Однако, простое суммирование этого неравенства по числу компонент, как это было сделано в первом пункте доказательства, ничего не даст, поэтому выполним над графом следующую процедуру. Выберем произвольно две компоненты: i‑ ую и j‑ ую. Можно считать, что число вершин выбранных компонент в_i ³ в_j > 1. Заменим i‑ ую компоненту на полный граф с числом вершин (в_i +1), а j‑ ую компоненту – на полный граф с числом вершин (в_j ‑1). Общее число вершин в выбранных компонентах при этом не изменится, а число ребер изменится на величину, равную

Таким образом, выполненная процедура только увеличивает число ребер. Будем выполнять её над выбранными компонентами до тех пор, пока от j‑ ой компоненты не останется одна изолированная вершина. Затем выберем другую пару компонент с числом вершин больше единицы в каждой. И выполним над этой парой такую же процедуру. И т.д. до тех пор, пока не будет получен граф, в котором с (k ‑1) компонента являются изолированными вершинами и одна компонента – полный граф на (в ‑ k +1) вершинах. Число ребер в полученном графе равно , и оценка сверху доказана.

Следствие. Любой простой граф с в вершинами и числом ребер, большим, чем связен.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник

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

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

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

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

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

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

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

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

Источник