Определение дерева эквивалентные определения

Содержание

Тема 4. Деревья
4.2. Остов
Эквивалентные определения дерева
Лекция № 15

Тема 4. Деревья

Деревья – это графы специального вида. Они весьма широко используются во многих отраслях знаний и, в частности, в информационных технологиях – методах поиска информации, хранения данных, сортировке и мн. др.

Существует несколько определений дерева.

1) Связный граф с n вершинами и n – 1 ребрами.

2) Связный граф без циклов.

3) Граф, в котором каждая пара вершин соединена точно одной цепью.

Докажем эквивалентность этих определений.

1)  2). Докажем, что в связном графе с n вершинами и n – 1 ребрами нет циклов. Предположим противное, т.е. цикл есть и e = (u, v) – ребро этого цикла. Удалим это ребро. Тогда граф останется связным, т.к. из u в v можно добраться по другой половинке цикла. В графе G\e n вершин, n – 2 ребер и он связан, т.е. у него 1 компонента связности, k = 1. По 3-й теореме о связности должно быть m = n – 2  n – 1 – противоречие. Следовательно, циклов нет.

2)  3). Хотя бы одна цепь, соединяющая u и v должна быть, т.к. граф связный. Предположим, что цепей не одна, а хотя бы две. Тогда, по свойству 3 маршрута, из них можно составить цикл – противоречие, т.е. 2-й цепи нет.

3)  1). Из 3) следует, что граф связный. Так как каждая пара вершин соединена точно одной цепью, то удаление любого ребра увеличит на 1 число компонент связности. Пусть в графе m ребер. По 3-й теореме о связности должно быть m  n – 1. Удалив 1 ребро, получим m – 1 n – 2, т.к. станет k = 2. Удалив 2 ребра, получим k = 3 и m – 2 n – 3, и т.д. Удалим n – 1 ребер, получим k = n и m – (n – 1) n – n. Но, т.к. k = n, то ребер больше нет. Следовательно, они были удалены за n – 1 шагов, поэтому m = n – 1, ЧТД.

Задание 1. Пусть Т – дерево, Т₁, Т₂ – его поддеревья. Доказать, что – тоже дерево.

Задание 2. В дереве n > 1. Доказать, что имеется по крайней мере 2 висячих вершины.

4.2. Остов

Def. Пусть G = (V, E) – неориентированный граф с n вершинами. Остовным деревом (остовом) графа G называется дерево T = (V, E₁), E₁  E.

Остов можно построить с помощью алгоритма поиска любого вида (в глубину и в ширину). Для этого во время поиска в G параллельно строится новый граф Т: если найдена новая еще непомеченная вершина u в списке инцидентности вершины v, то ребро (v, u) добавляется в строящийся граф. Если исходный граф несвязный, то задача не имеет решения.

Читайте также: Кухня глянец плюс дерево

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

Задача построения остова имеет большое прикладное значение. Она возникает при прокладке трасс и сетей коммуникаций, которые должны связать n заданных точек. Обычно требуют, чтобы остов обладал некоторым оптимальным свойством. Например, если каждое ребро имеет некоторый вес, то остов должен иметь минимальный вес.

Алгоритм Краскала. Этот алгоритм применяется для построения остова минимального веса. Пусть имеем граф G = (V, E), в котором каждому ребру присвоен вес (e) – некоторое вещественное число. Основная идея алгоритма: начиная с полностью несвязного графа Т = (V, ), присоединяем к нему ребра графа G в порядке возрастания их веса; если после присоединения очередного ребра в Т может образоваться цикл, то это ребро не присоединяем, а переходим к следующему. Можно доказать, что таким образом строится остов минимального веса.

Машинная реализация алгоритма Краскала. Сложность машинной реализации заключается в следующем.

1). Перед выполнением необходимо, чтобы ребра графа были отсортированы в порядке возрастания веса. Эта операция имеет сложность О(m 2 ), а если граф близок к полному, то О(n 4 ) – достаточно высокая.

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

begin T:= ; for i:=1 to n do КОМП[i]:= i;

begin a:=НАЧАЛО[e[j]];

if КОМП[a] <> КОМП[b] then

begin Т:= T;

if КОМП[i] = КОМП[b] then

КОМП[i] := КОМП[a];

Оценим вычислительную сложность без сортировки. Просмотр списка ребер – O(m) операций. Внутренний цикл по i от 1 до n – повторяется n – 1 раз, по числу добавляемых ребер. Итого О(m) + О(n 2 ) = О(n 2 ).

Источник

Эквивалентные определения дерева

Существует несколько определений дерева.

1) Связный граф с n вершинами и n – 1 ребрами.

2) Связный граф без циклов.

3) Граф, в котором каждая пара вершин соединена точно одной цепью.

Докажем эквивалентность этих определений.

1) Þ 2). Докажем, что в связном графе с n вершинами и n – 1 ребрами нет циклов. Предположим противное, т.е. цикл есть и e = (u, v) – ребро этого цикла. Удалим это ребро. Тогда граф останется связным, т.к. из u в v можно добраться по другой половинке цикла. В графе G\e n вершин, n – 2 ребер и он связан, т.е. у него 1 компонента связности, k = 1. По 3-й теореме о связности должно быть m = n – 2 ³ n – 1 – противоречие. Следовательно, циклов нет.

2) Þ 3). Хотя бы одна цепь, соединяющая u и v должна быть, т.к. граф связный. Предположим, что цепей не одна, а хотя бы две. Тогда, по свойству 3 маршрута, из них можно составить цикл – противоречие, т.е. 2-й цепи нет.

3) Þ 1). Из 3) следует, что граф связный. Так как каждая пара вершин соединена точно одной цепью, то удаление любого ребра увеличит на 1 число компонент связности. Пусть в графе m ребер. По 3-й теореме о связности должно быть m ³ n – 1. Удалив 1 ребро, получим m – 1³ n – 2, т.к. станет k = 2. Удалив 2 ребра, получим k = 3 и m – 2³ n – 3, и т.д. Удалим n – 1 ребер, получим k = n и m – (n – 1)³ n – n. Но, т.к. k = n, то ребер больше нет. Следовательно, они были удалены за n – 1 шагов, поэтому m = n – 1, ЧТД.

Задание 1. Пусть Т – дерево, Т₁, Т₂ – его поддеревья. Доказать, что – тоже дерево.

Задание 2. В дереве n > 1. Доказать, что имеется по крайней мере 2 висячих вершины.

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

Источник

Лекция № 15

1. Эквивалентные определения дерева. Дерево – это связный граф, в котором нет циклов. Следующая теорема показывает только меньшую часть возможных равносильных определений дерева.

Теорема 1. Пусть – -граф. Тогда следующие условия эквивалентны:

() любые две вершины в графе соединены единственной простой цепью;

Доказательство. ()Þ(). Так как – связный граф, то любые две вершины и в графе соединены цепью, простой, поскольку еще –граф без циклов.

Если вершины и соединены двумя цепями, то получится цикл:

()Þ(). Непосредственно по условию граф связный. Доказываем равенство

индукцией по числу ребер (или вершин).

Уберем одно ребро между вершинами и . В силу единственности соединяющей цепи между вершинами и , граф распадается на два графа, удовлетворяющих условию ().

Если эти графы имеют по и вершин и по и ребер, то по индуктивному предположению для них выполняется равенство (1):

Сложив по частям (2) и (3), учитывая, что и , то получим равенство (1).

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

Получается, что граф имеет число ребер , что противоречит (1).

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

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

2. Пример. Деревья с числом вершин не больше 5. Приведем все попарно неизоморфные деревья с числом вершин, не больше 5:

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

Приведем пример графа и одного из его остовов:

Обходы всех вершин графа совершаются как обход некоторого его остова. Методами обхода графа являются поиск в глубину и поиск в ширину.

Алгоритм поиска в глубину: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

Пример графа и поиска в глубину этого графа:

1 — 2 — 3 — 4 -3- 5 -3-2-1- 6 -7-6- 8 -6- 9 — 10 — 11 -10-9- 12 -9-6-1.

Порядок поиска в ширину: началу обхода приписывается метка 0; вершинам, смежным с вершинами метки i, – метка i +1 (i =0,1,2,…). Затем нумеруем вершины: вначале вершины с меткой 0, затем с меткой 1 и т. д.

Пример графа и поиска в ширину этого графа:

Источник