Определение дерева в математике

5.14. Деревья и их свойства

– замкнутые цепи_.

_{2. Любые 2 вершины v и w соединены единственной цепью.}

_{Доказательство следует из определения дерева.}

_{3. Для дерева справедливо следующее соотношение: p = q + 1 (*), где p – число вершин, q – число ребер.}

_{Доказательство (индукцией по p):}

_{а) p = 1 – дерево состоит из одной вершины, q = 0, тогда соотношение (*) выглядит 1 = 1.}

_{б) Пусть соотношение (*) верно для любых деревьев, у которых вершин меньше, чем p.}

_{в) Рассмотрим дерево с p вершинами. Уберем ребро, соединяющее вершины v и w. Наш граф разбился на 2 подграфа и . , – деревья, так как они связны и не имеют замкнутых цепей. Поэтому для них верно индукционное предположение:}

_{VWV W}

_.

_{4. Если любые 2 вершины v и w в дереве соединить ребром, то получим ровно одну замкнутую цепь.}

_{Доказательство следует из свойства 2.}

_{5. Пусть G = (p, q) – дерево, где p > 1. Тогда в дереве G существуют хотя бы 2 вершины v и w такие, что .}

_{Доказательство. Как известно, (по свойству 3). Предположим, что не существуют 2 вершины, степень которых равна 1, т.е. пусть , а у остальных вершин , где . Тогда получаем, что . Пришли к противоречию, значит, существуют вершины v и w такие, что .}

_{Определение. Вершины в дереве, степень которых равна 1, называются концевыми.}

_{где max(n) – глубина (количество ярусов) дерева, – корень дерева (корень – это некоторая выделенная вершина).}

5.15. Деревья и операции над ними

_{1. Ребро – дерево с корнем (код 01), дереву из одного ребра дается код 01.}

_{2. Если у нас есть дерево с корнем, то результат присоединения этого дерева к ребру – также есть дерево с корнем.}

_{При этом пусть дерево с корнем имеет код А, тогда дереву, полученному в результате операции 2, ставится код 0А1.}

_{3. Если у нас есть два дерева с корнем,}

_{то результат склеивания этих деревьев также есть дерево с корнем. Если при этом у одного дерева код А, а у другого код В, тогда у дерева, которое получается склеиванием этих деревьев, код будет АВ.}

_{Замечание. Любое дерево с корнем можно получить при помощи вышеуказанных трех операций, при этом всегда можно определить его код.}

_{Пример. Пусть дано корневое дерево Т, определить его код, где}

_{Решение: Исходное дерево Т получено из деревьев двукратным применением операции 3, где}

_{1) Дерево получено из дерева с помощью операции 2, где}

_,

_{Дерево получено из дерева операции 1 двукратным применением}

_{операции 3, тогда код дерева A‘ = 010101, следовательно, код дерева A = 00101011.}

_{2) Дерево Т2 получено с помощью операции 1, его код – 01.}

_{3) Дерево Т3 получено из дерева операции 1 двукратным применением операции 2, тогда код дерева Т3 В = 000111.}

_{В итоге код корневого дерева Т есть код А01В = 0010101101000111.}

_{1) Длина кода дерева равна удвоенному числу его ребер (2q).}

_{2) В любом начальном отрезке (если считать код дерева слева) число нулей числа единиц.}

_{3) Во всем коде число нулей равно числу единиц.}

_{Встает логичный вопрос: как восстанавливать по коду дерево?}

_{Берем произвольный код дерева, где , q – число ребер дерева. Идем слева направо и отмечаем такой момент, когда число нулей совпадает с числом 1. При этом возможны два случая:}

_{1) Пусть равенство наступит в конце кода, тогда , т.е. дерево с кодом получено из дерева с кодом с помощью операции 2.}

_{2) Пусть равенство наступит, не доходя до конца кода, т.е. , а это означает, что дерево с кодом получено из деревьев соответственно с кодами и с помощью операции 3.}

_{Аналогично, т.е. согласно пунктам 1) и 2), восстанавливаем по кодам соответствующие им деревья. Этот процесс называется декодированием. Не сложно доказать (мы практически уже показали), что между деревом и его кодом существует взаимно однозначное соответствие.}

_{Пример. Построить корневое дерево по его коду .}

_{Решение: q = 7. , где . Таким образом, дерево с кодом получено из деревьев соответственно с кодами с трехкратным применением операции 3. Аналогично, дерево с кодом получено из дерева операции 1 с применением операции 2; деревья с кодами и – деревья операции 1; дерево с кодом получено из дерева операции 1 с двукратным применением операции 2. В итоге дерево Т выглядит следующим образом:}

Источник

Лекция 11

Дерево. Лес (ациклический граф). Остовный подграф. Остов. Взвешенный граф. Минимальный остов. Кодирование деревьев.

Базовые понятия и утверждения

1. Определение и основные свойства деревьев.

Определение. Граф называется деревом, если он связный и в нем нет циклов.

Одноэлементный граф, т.е. граф, имеющий одну вершину и не имеющий ребер, также считается деревом.

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

Пример 1. Граф (рис. 3.19) не является ни деревом, ни лесом. Граф (рис. 3.20) — дерево. Граф (рис. 3.21) — лес, состоящий из четырех деревьев.

Пример 2. Представьте диаграммами все (с точностью до изоморфизма) деревья с пятью вершинами.

◄ Имеется три различных (с точностью изоморфизма) дерева с пятью вершинами (рис. 3.22 — 3.24). ►

Деревья обладают рядом характеристических свойств, по наличию или отсутствию каждого их которых в рассматриваемом графе можно определить, является граф деревом или нет. Перечислим эти свойства:

1) граф — дерево в том и только в том случае, когда в нем нет циклов и ;

2) граф — дерево в том и только в том случае, когда он связный и ;

3) граф — дерево в том и только в том случае, когда он связный, и каждое его ребро является мостом;

4) граф — дерево в том и только в том случае, когда любые две вершины графа можно соединить простой цепью, притом единственной;

5) граф — дерево в том и только в том случае, когда в нем нет циклов и добавление к нему нового ребра приводит к образованию единственного простого цикла.

Также приведем одно из характеристических свойств леса: граф , имеющий компонент связности, является лесом в том и только в том случае, когда .

2. Остовы графа. Подграф графа называется остовным подграфом, если множество его вершин совпадает с множеством вершин графа .

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

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

Пусть теперь — произвольный граф с компонентами связности. Из каждой компоненты связности этого графа удалим ребро так, чтобы получился остов этой компоненты. В результате получим некоторый остовный подграф графа . Подсчитаем общее число ребер, которое нам пришлось для этого удалить. Сложив равенства , , получим:

.

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

Пример 3. Построим остов графа , диаграмма которого изображена на рис. 3.25. Удалим из графа ребро ; получим граф (рис. 3.26). Из графа удалим ребро ; получим граф (рис. 3.27). Из графа удалим ребро ; получим граф (рис. 3.28), который является одним из остовов графа .

Источник

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

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

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

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

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

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

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

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

Источник