Двудольный граф дерево доказать

Деревья

Граф без циклов (ациклический граф) называется лесом.

Связный ациклический граф называется деревом.

Для (n, m) — графа G следующие утверждения эквивалентны:

G-дерево;
G-связный граф и m= n – 1;
G-ациклический граф и m= n – 1;
любые две несовпадающие вершины графа G соединены единственной простой цепью.

1) Þ 2) Пусть дан (n,m) граф G – связный и ациклический. Докажем индукцией по n, что m= n – 1.

Индуктивное предположение: допустим при n k m=n-1;

Индуктивный переход: докажем, что при n=k m=n-1.

Удалив ребро, получим два дерева с числом вершин Очевидно . По индуктивному предположению Вернув ребро, получим

2) Þ 3) Пусть дан связный (n, m) граф G и m=n–1. Докажем, что G – ациклический граф.

Предположим противное: в G существует цикл и пусть — ребро этого цикла. Тогда граф — связный по теореме 7 предыдущего параграфа и имеет ребра, что невозможно по теореме 9 предыдущего параграфа. Значит, граф G – ациклический.

3) Þ 4) Пусть дан ациклический (n, m)-граф G и m= n–1.

Докажем, что любые две несовпадающие вершины графа G соединены единственной простой цепью.

Предположим противное: пусть существуют вершины u и v, которые можно соединить по крайней мере двумя различными простыми цепями: u x₁ x₂ … x_kv и u y₁ y₂ … y_sv. Но тогда в графе есть цикл u x₁ x₂ … x_kv y_s … y₁ y₂ u, что противоречит пункту 3). Значит, любые две несовпадающие вершины графа G соединены единственной простой цепью.

4) Þ 1) Пусть любые несовпадающие вершины графа G соединены единственной простой цепью. Значит граф G – связный. Покажем, что в графе G нет циклов.

Предположим противное: пусть в графе G существует цикл. Тогда любые две вершины этого цикла можно соединить по крайне мере двумя различными простыми цепями, что противоречит пункту 4). Значит, граф G – ациклический.

В любом дереве порядка n³2 имеется не менее двух висячих вершин.

Для дерева порядка n справедливо равенство

(1)

Допустим противное: в дереве порядка n³2 либо нет висячих вершин, либо ровно одна висячая вершина.

В первом случае степень каждой вершины не меньше двух, следовательно

Во втором случае степень висячей вершины равна 1, а остальных не меньше 2, следовательно

Оба неравенства противоречат равенству (1).

Висячая вершина дерева называется концевой вершиной.

Центр любого дерева состоит из одной или из двух смежных вершин.

Заметим, сперва, что концевые вершины дерева будут центральными, только если T=K₁ или Т=K₂.

Рассмотрим дерево Т с n вершинами (n > 2) и удалим его все концевые вершины. Получим дерево, у которого центр будет тот же самый, что у дерева Т, а радиус – на единицу меньше, чем у дерева Т. Таким образом, проделав процедуру удаления всех концевых вершин некоторое число раз, мы получим или граф K₁ или граф K₂.

Так как центр при этом не изменится, то центр произвольного дерева Т совпадет с центром графа K₁ или с центром графа K₂, т.е. будет состоять из двух смежных вершин, как у K₂, или из одной, как у K₁.

Простая цепь, реализующая диаметр графа, называется диаметральной цепью.

Граф G = (V, E) будем называть взвешенным, если существует функция f: E®R, т.е. каждому ребру графа G поставлено в соответствие некоторое вещественное число, которое называется весом (стоимостью, длиной) ребра.

Если остовный подграф некоторого графа является деревом, то будем называть его остовным деревом или остовом

(алгоритм нахождения во взвешенном графе остова наибольшего или наименьшего веса).

Пусть дан связный взвешенный граф G = (V, E), çV ê= n.

Цель: построение дерева Т наименьшего (наибольшего) веса являющегося остовом графа G:

0 шаг: в качестве искомого берем Т=Оn

1 шаг: выберем в G ребро наименьшего (наибольшего) веса и добавим его в Т.

i шаг (к тому моменту граф Т содержит уже (i–1) ребро графа G): выбираем из оставшихся ребер графа G ребро наименьшего (наибольшего) веса, не образующий циклов с уже выбранными ребрами, и добавим его в Т.

Критерий останова: алгоритм прекращает свою работу, когда уже выбрано (n–1) ребро, так как в этом случае добавление любого оставшегося ребра будет приводить к образованию цикла.

— остов минимального веса, – остов максимального веса.

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

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

Граф вида называется звездой порядка n.

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

Теорема 5 (Кёнига, критерий двудольности графа)

Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

Необходимость. Пусть двудольный граф содержит цикл длины k.

Докажем, что k – четное число. Концы всех его ребер принадлежат разным долям, поэтому, проходя по циклу, мы каждый раз попадаем из одной доли в другую. На последнем шаге мы возвращаемся в исходную вершину, а значит, делаем четное число таких «переходов», поэтому k – четное число.

Достаточность. Пусть граф G не содержит циклов нечетной длины, то есть все имеющиеся в нем циклы четной длины. Разделим все вершины графа G на две части. В первую часть попадут все вершины, расстояние до которых от фиксированной вершины v четное число, и сама вершина v, а во вторую – все остальные вершины. Осталось показать, что никакие две вершины, попавшие в один класс не смежны. Предположим противное, то есть некоторые вершины x и y, принадлежащие одному из двух полученных множеств, смежны. Рассмотрим цикл, полученный в результате объединения ребра (x; y) и кратчайших цепей, соединяющих вершины x и y с вершиной v. Длина этого цикла равна сумме длин этих двух цепей плюс один. Но длины этих двух цепей одинаковой четности, поэтому их сумма – четное число, значит длина получившегося цикла – нечетное число. Пришли к противоречию, значит никакие две вершины, попавшие с один класс, не смежны.

Читайте также: Рукоять ножа рог дерево

Граф является двудольным тогда и только тогда, когда он не содержит простых циклов нечетной длины.

Алгоритм поиска в ширину

Выбираем произвольную вершину в графе и приписываем ей номер ноль. Всем вершинам из ее окружения приписываем номер один. Далее рассматриваем поочередно окружение всех вершин с номером один и еще не занумерованным вершинам приписываем номер два, и так далее, пока это возможно. Если граф G связен, то поиск в ширину занумерует все его вершины.

Далее разобьем множество вершин на две части , отнеся к все вершины с четными номерами, а к — все остальные. Если среди вершин множества нет смежных и среди вершин множества нет смежных (достаточно проверить все пары вершин с одинаковыми номерами), то граф G – двудольный.

Граф G не является двудольным

Алгоритм поиска в ширину позволяет решать следующие задачи.

Поиск кратчайшей цепи, соединяющей две несовпадающие вершины.
Разбиение множество вершин графа на области связности.
Поиск в ориентированном графе всех вершин, достигаемых из заданной вершины.

Незанумерованная вершина недостижима из вершины с номером ноль.

Источник

Важнейшие классы графов

Деревом называется связный граф , не имеющий циклов. В графе без циклов, таким образом, каждая компонента связности является деревом. Такой граф называют лесом .

P_<n data-lazy-src=

Из теоремы 2 «Маршруты, связность, расстояния» следует, что во всяком дереве, в котором не меньше двух вершин, имеется вершина степени 1. Такие вершины называют висячими вершинами , или листьями . В действительности легко доказать, что в каждом дереве не меньше двух листьев, а цепь »/> — пример дерева, в котором точно два листа.

В следующих двух теоремах устанавливаются некоторые свойства деревьев.

Теорема 1. Граф с вершинами и ребрами является деревом тогда и только тогда, когда он удовлетворяет любым двум из следующих трех условий:

m=n-1

(1) связен;
(2) не имеет циклов;
(3) .

Первые два условия вместе составляют определение дерева. Покажем, что выполнение любых двух из условий (1)-(3) влечет за собой выполнение третьего.

Читайте также: Модуль юнга дерево сосна

(1) и (2) $\Rightarrow$ (3). Индукция по числу вершин. При n=1 утверждение очевидно. При $n\ge 2$ в дереве имеется хотя бы один лист. Если из дерева удалить лист, то снова получится дерево, так как циклов не появится, а связность, очевидно, сохранится. В этом новом дереве n-1 вершин и, по предположению индукции, n-2 ребра. Следовательно, в исходном дереве было n-1 ребро.

(2) и (3) $\Rightarrow$ (1). Пусть в графе, не имеющем циклов, n-1 ребро, а его компонентами связности являются G_<1 data-lazy-src= ,G_\ldots G_»/>, причем состоит из вершин, $i=1\ldots k$ . Каждая компонента является деревом, поэтому, как доказано выше, число ребер в равно n_-1 , а всего ребер в графе $\suml_<i=1 data-lazy-src=$ ^\left(n_ -1\right) =n-k=n-1″/>. Значит, k=1 и граф связен.

(1) и (3) $\Rightarrow$ (2). Рассмотрим связный граф с n-1 ребром. Если бы в нем был цикл, то, удалив любое цикловое ребро, мы получили бы связный граф с меньшим числом ребер. Можно продолжать такое удаление ребер до тех пор, пока не останется связный граф без циклов, то есть дерево. Но ребер в этом дереве было бы меньше, чем n-1 , а это противоречит доказанному выше.

Теорема 2. Если — дерево, то

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

Существование пути между любыми двумя вершинами следует из связности дерева. Допустим, что в некотором дереве существуют два различных пути, соединяющих вершины и . Начальные отрезки этих путей совпадают (оба пути начинаются в одной и той же вершине ). Пусть — последняя вершина этого совпадающего начала, а после в одном пути следует вершина y_<1 data-lazy-src= »/>, а в другом — вершина y_<2 data-lazy-src= »/>. Рассмотрим ребро $\left(x,y_<1 data-lazy-src=$ \right)»/>. Если его удалить из графа, то в оставшемся подграфе вершины »/> и будут соединимыми — соединяющий их маршрут можно построить так: взять отрезок первого пути от y_<1 data-lazy-src= »/> до и к нему присоединить отрезок второго от до , взятый в обратном порядке. Но это означает, что ребро $\left(x,y_<1 data-lazy-src=$ \right)»/> не является перешейком. Однако из теоремы 4 «Маршруты, связность, расстояния» следует, что в дереве каждое ребро является перешейком. Этим доказано утверждение 1). Утверждения 2) и 3) следуют из 1).

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

Источник