Свободные деревья

12 3 4 5 6 Следующая ⇒

Лекция № 15

ДЕРЕВЬЯ

Одним из простейших классом графов являются деревья. Граф является деревом, если он удовлетворяет следующей теореме.

Теорема. Для графа G= <X,U> следующие утверждения эквивалентны:

1) G - дерево;

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

3) граф G связен и имеет |X| - 1 ребер;

4) граф G не содержит циклов и имеет |X| - 1 ребер;

5) граф G не содержит циклов, но добавление ребра между любыми двумя несмежными вершинами приводит к появлению одного цикла;

6) граф G связен, но утрачивает это свойство после удаления любого ребра.

Деревья широко применяются в программировании.

Свободные деревья

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

Граф G, в котором q(G) = р(G)- 1, называется древовидным.

В ациклическом графе G z(G) = 0. Пусть и, v — несмежные вершины графа G, х = (и, v) E. Если граф G+x имеет только один простой цикл, z(G+х)= 1, то граф G называется субциклическим.

Пример

На рис. 9.1 показаны диаграммы всех различных (свободных) деревьев с 5 вершинами, а на рис. 9.2 — диаграммы всех различных (свободных) деревьев с 6 вершинами.

Рис. 9.1. Свободные деревья с 5 вершинами

Рис. 9.2. Свободные деревья с 6 вершинами

Основные свойства деревьев

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

Теорема

Пусть G(V, Е) — граф с р вершинами, q ребрами, k компонентами связности и z простыми циклами. Пусть далее х — ребро, соединяющее любую пару несмежных вершин в G. Тогда следующие утверждения эквивалентны:

1. G — дерево, то есть связный граф без циклов, k(G) = 1&z(G) = 0;

2. любые две вершины соединены в G единственной простой цепью,

.

3. G — связный граф, и любое ребро есть мост,

;

4. G — связный и древовидный,

;

6. G — ациклический и субциклический,

;

7. G — связный, субциклический и неполный,

;

8. G — древовидный и субциклический (за двумя исключениями),

;

Доказательство

[1 2] От противного. Пусть существуют две цепи <и, v>; (рис. 9.3, слева). Тогда w, w₂ — простой цикл.

Рис. 9.3. К доказательству теоремы о свойствах деревьев

[2 3.] Имеем: и, v !, следовательно, . Далее от противного. Пусть ребро х — не мост. Тогда в G - х концы этого ребра связаны цепью. Само ребро х — вторая цепь.

[3 4.] Индукция по р. База: р = 1 q = 0. Пусть для всех связанных графов G с числом вершин меньше р, у которых любое ребро суть мост. Тогда удалим из G ребро х (которое является мостом). Получим две компоненты G ' и G ";, удовлетворяющие индукционному предположению. Имеем:

.

[4 5.] От противного. Пусть есть цикл с п вершинами и п ребрами. Остальные р - п вершин имеют инцидентные им рёбра, которые связывают их с циклом, Следовательно, q ≥ р, что противоречит условию q = р - 1.

[5 1.] Граф без циклов, следовательно, его компоненты — деревья. Пусть их k;. Имеем:

_i = У(p_i-1) = Уp_i-k = p-k

Но q=p-1, следовательно, k = 1.

[5 6.] По ранее доказанному 5 1 2. Имеем: . Соединив две несмежные вершины, получим единственный простой цикл.

[6 7.] При р ≥ 3 граф К_р содержит цикл, следовательно, G ≠ К_р. Далее от противного. Пусть G несвязен, тогда при соединении ребром двух компонент связности цикл не возникнет.

[7 2.] Имеем k(G) = 1, следовательно, . Пусть цепь не единственная. Тогда существует цикл Z, причем Z = К₃, = С₃. Действительно, пусть Z > С₃, тогда, соединив две несмежные вершины этого цикла, получим два цикла. Но G связен и G ≠ К₃, следовательно, существует другая вершина w, смежная с Z = К₃ (см. рис. 9.3, справа). Если w смежна более чем с одной вершиной Z, то имеем больше одного цикла. Если w смежна только с одной вершиной Z, то соединив её с другой вершиной, получим два цикла.

[7 8.] Имеем k(G) = 1, следовательно, G ≠ К₂ К₃, G ≠ К₁ К₃. Имеем по доказанному: 7 2 3 4, то есть q = р- 1.

[8 5.] От противного. Пусть в G есть цикл Z = С_п. Если n > 3, то если внутри Z уже есть смежные вершины, имеем два цикла. Если в Z нет смежных вершин, то, соединив несмежные вершины в Z, получим два цикла. Следовательно, Z = К₃. Этот цикл Z является компонентой связности G. Действительно, пусть это не так. Тогда существует вершина w, смежная с Z. Если w смежна более чем с одной вершиной Z, то имеем больше одного цикла. Если w смежна только с одной вершиной Z, то, соединив её с другой вершиной, получим два цикла. Рассмотрим G:=G - Z. Имеем: р = р' + 3, q = q' + 3. Но q = р - 1, следовательно, q' = р' - 1. Отсюда z(С') = 0, так как один цикл уже есть. Следовательно, компоненты G' — деревья. Пусть их k. Имеем:

_I = У(p_i-1) = Уp_i-k = ṕ-k

но q' = p' -1, следовательно. k = 1. то есть дерево одно. Если в этом дереве сбединить несмежные вершины, то получим второй цикл. Два исключения: деревья, которые не имеют несмежных вершин, — это К₁ и K₂.

Общая схема доказательства представлена на рис. 9.4. Граф доказательства сильно связен, следовательно, теорема доказана.

Вычисление

От противного

Рис. 9.4. Схема доказательства теоремы о свойствах деревьев

Следствие 1 В любом нетривиальном дереве имеются по крайней мере две висячие вершины.

Доказательство

Рассмотрим дерево G(V, Е). Дерево — связный граф, следовательно, .

Далее от противного. Пусть . Тогда

2q = Уd(vi) > 2(р - 1) + 1 = 2р - 1.

Но q = р - 1, то есть 2q = 2р - 2. Имеем противоречие: 2р - 2 2 > 2р - 1.

Следствие 2. Каждая не висячая вершина свободного дерева является точкой сочленения.

Доказательство

Пусть G(V, Е) — дерево, v V и d(v) >; 1. Тогда и, w V(u,v) E& (u, w) E. Граф G связен, поэтому существует цепь (и, w). Если v <и,w>;, то имеем цикл v,<и,w>, v, что противоречит тому, что G — дерево. Следовательно, и, w V <и,w> v <u, w> и по теореме 8.1.2 вершина v — точка сочленения.

Центр дерева

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

Теорема

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

Z(G) = 0&k(G) = 1 → С(G) = К₁ С(G) = К₂.

Доказательство

Для деревьев К₁ и К₂ утверждение теоремы очевидно. Пусть теперь G(V,Е) — некоторое свободное дерево, отличное от К₁ и К₂. Рассмотрим граф G'(V',Е'), полученный из G удалением всех висячих вершин. Заметим, что G ' — дерево, поскольку ацикличность и связность при удалении висячих вершин сохраняется. Далее, если эксцентриситет е_G(v) = d(v,и), то и — висячая вершина в дереве G (иначе можно было бы продолжить цепь «за» вершину и ). Поэтому v V' е_G(v) = е_G_'(v)+1 и при удалении висячих вершин эксцентриситеты оставшихся уменьшаются на 1. Следовательно, при удалении висячих вершин центр не меняется, С(G) = С(G'}. Поскольку дерево G конечно, то удаляя на каждом шаге все висячие вершины, в конце концов за несколько шагов придём к К₁ или К₂.

Ориентированные, упорядоченные и бинарные деревья

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

12 3 4 5 6 Следующая ⇒

Дата добавления: 2015-08-12; просмотров: 2080. Нарушение авторских прав; Мы поможем в написании вашей работы!

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

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при которых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Искусство подбора персонала. Как оценить человека за час Искусство подбора персонала. Как оценить человека за час...

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

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

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

Мотивационная сфера личности, ее структура. Потребности и мотивы. Потребности и мотивы, их роль в организации деятельности...

Классификация ИС по признаку структурированности задач Так как основное назначение ИС – автоматизировать информационные процессы для решения определенных задач, то одна из основных классификаций – это классификация ИС по степени структурированности задач...

Studopedia.info - Студопедия - 2014-2024 год . (0.008 сек.) русская версия | украинская версия