Дерева та їх властивості приватний вид графів

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Міністерство освіти Республіки Білорусь

Установа освіти
«Білоруський державний університет
інформатики і радіоелектроніки »
РЕФЕРАТ
на тему:
«ДЕРЕВА І ЇХ ВЛАСТИВОСТІ (ПРИВАТНИЙ вид графа)»
Мінськ, 2008

Розглянемо окремий вид графів, широко використовуваних, наприклад, в теорії електричних ланцюгів, хімії, обчислювальної техніки та інформатики.
Визначення 1. Деревом називається зв'язний граф, який не містить циклів. Кожен (в тому числі незв'язний) граф без циклів називається ациклічним. Незв'язний граф, кожна компонента зв'язності якого є деревом, називається лісом. Можна сказати, що дерева є компонентами лісу. На рис.1 зображені два дерева G1, G2 і ліс G3.

Рис.1
Сформулюємо основні властивості дерев. Зробимо це у вигляді сукупності тверджень, які еквівалентні між собою (тобто з будь-якого твердження випливає будь-яке інше) [].
Теорема 1. Нехай G (X, E) - неорієнтований граф з p вершинами і q ребрами. Тоді наступні твердження еквівалентні.
1. G є дерево.
2. Будь-які дві різні вершини x і y графа G з'єднані єдиною простий ланцюгом.
3. G - зв'язний граф, що втрачають цю властивість при видаленні будь-якого з його ребер.
4. G - зв'язний граф і p = q + 1.
5. G - ациклічний граф і p = q + 1.
6. G - ациклічний граф, причому якщо будь-які дві його вершини x і y з'єднати ребром e, то отриманому графі буде рівно один простий цикл.
Для доведення теореми достатньо довести наступний ланцюжок наслідків: 1 Þ 2 Þ 3 Þ 4 Þ 5 Þ 6 Þ 1, так як це означає, що з будь-якого затвердження 1 - 6 виводиться будь-яке інше.
1 Þ2. Так як граф зв'язний, то будь-які дві його вершини можна з'єднати простий ланцюгом. Нехай m1 і m2 - дві різні прості ланцюги, що з'єднують вершини x і y. Якщо кола m1 і m2 не мають спільних вершин, за винятком вершин x та y, то є простий цикл. Припустимо, що ланцюги m1 і m2 мають спільні вершини, відмінні від x та y. Нехай z - перша з таких вершин при русі від вершини x до вершини y і нехай m1 (x, z) і m2 (x, z) - частини кіл m1 і m2, взяті від вершини x до вершини z. Тоді - Простий цикл. Це суперечить тому, що граф аціклічен, і тому m1 = m2, тобто твердження 2 доведено.
2 Þ3. Граф G - зв'язний, оскільки будь-які дві його різні вершини x і y з'єднані простий ланцюгом. Візьмемо деякий ребро графа e = (x, y). Згідно з 2 простий ланцюг m = {e} між вершинами x та y єдина. Якщо ребро e видалити, то вершини x і y буде неможливо поєднати простий ланцюгом, і отриманий граф буде незв'язних. Затвердження 3 доведено.
3 Þ4. За умовою 3 граф зв'язний. Співвідношення p = q + 1 доведемо по індукції. Якщо граф має дві вершини і задовольняє 3, то він виглядає так:

У цьому випадку p = 2, q = 1 і співвідношення p = q + 1 виконується. Припустимо тепер, що співвідношення вірно для всіх графів, які відповідають 3 та мають менше, ніж p вершин, і доведемо його для графа G з p вершинами. Видалимо з графа G довільне ребро e. Тоді новий граф Gґ буде незв'язних і складатиметься з двох зв'язкових компонент G1 і G2. За припущенням індукції маємо
p1 = q1 + 1, p2 = q2 + 1,
де pi - число вершин компоненти Gi, qi - число її ребер. Отже,
p = p1 + p2, q = q1 + q2 + 1,
тому p = q1 + q2 + 2 = q + 1, і властивість 4 доведено.
4 Þ5. Припустимо, що граф G, що задовольняє 4, має простий цикл m довжиною l ³ 1. Цей цикл містить l вершин і l ребер. Для будь-якої з p - l вершин, що не належать циклу m, існує Інцидентне їй ребро, що лежить на найкоротшій ланцюга (тобто ланцюга мінімальної довжини), що йде від даної вершини до деякої вершині циклу m. Всі такі ребра попарно різні. Якщо вершини x1 і x2 інцидентних одному такому ребру e, то e = (x1, x2), і найкоротша ланцюг m1 для вершини x1 проходить через вершину x2, а найкоротша ланцюг m2 для вершини x2 проходить через вершину x1 (рис. 2). Це суперечить тому, що ланцюги m1 і m2 - найкоротші. Загальне число ребер q у графі G в цьому випадку не менше, ніж l + p - l = p, тобто q ³ p, що суперечить співвідношенню p = q + 1. Звідси випливає, що G - ациклічний граф, та затвердження 5 доведено.

Рис. 2
5 Þ6. Так як G - ациклічний граф, то кожна його компонента зв'язності Gi (i = 1, 2, ..., k) є деревом. Для кожної компоненти Gi маємо відповідно до 5 pi = qi + 1, звідки , Тобто p = q + k. З іншого боку, p = q + 1, тому k = 1, тобто граф G зв'язний. Таким чином, G - дерево. Тоді (див. 2) будь-які дві різні вершини x і y графа G з'єднані єдиною простий ланцюгом. Якщо додати ребро між несуміжними вершинами x та y, то воно утворює з зазначеної ланцюгом єдиний простий цикл. Затвердження 6 доведено.
6 Þ1. За умовою 6 G - ациклічний граф. Якщо граф G не є зв'язковим, то візьмемо вершини x і y з різних компонент зв'язності графа G і з'єднаємо їх ребром e. Побудований граф є, як і граф G, ациклічні. Це суперечить властивості G, тому G - зв'язний граф, і властивість 1 доведено. Таким чином, доведена і теорема 1.
Визначення, аналогічне дереву, можна запровадити і для орграфа.
Визначення 2. Орграф G (X, E) називається прадеревом або орієнтованим деревом, що росте з кореня x0, за таких умов:
1. Неорієнтований граф G ', відповідний графу G, є деревом.
2. Єдина простий ланцюг між x0 і будь-який інший вершиною x графа G 'є шляхом у орграфе G, що йде з вершини x0 у вершину x.
На рис. 3 зображено орієнтоване дерево.

Рис. 3
У неорієнтованому графі G (X, E) вершина x називається кінцевий або висячої, якщо d (x) = 1, тобто якщо цій вершині інцидентне єдине ребро e. Це ребро також називається кінцевим або висячим. З висячими вершинами пов'язана наступна теорема.
Теорема 2. У будь-якому дереві G (X, E) з p ³ 2 вершинами є не менше двох кінцевих вершин.
Доказ. Нехай q - число ребер дерева G. У силу теореми 1 p = q + 1. Крім того, із теореми 1.1 маємо
.
Таким чином, отримуємо
. (1)
Припустимо, що x0 - єдина кінцева вершина в дереві G. Тоді d (x0) = 1, d (x) ³ 2, якщо x ¹ x0. Звідси
. (2)
Нерівність (2) суперечить (1), тому або кінцевих вершин немає, або їх принаймні дві. Якщо кінцевих вершин в G немає, то d (x) ³ 2 для всіх xÎX. Тоді
. (3)
Нерівність (3) теж суперечить (1). Звідси випливає, що кінцевих вершин в G два або більше. Теорема доведена.
Важливим є питання про те, скільки існує дерев з заданим числом вершин. Для дерев з позначеними вершинами (наприклад пронумерованими) або для помічених дерев відповідь на це питання дає наступна теорема.
Теорема 3. (А. Келі, 1897 р .). Число помічених дерев з p вершинами одно pp-2.
Доказ. Нехай G (X, E) - дерево з p позначеними вершинами. Для простоти припустимо, що вершини пронумеровані в довільному порядку числами 1, 2, ..., p. Розглянемо спосіб, що дозволяє однозначно закодувати дерево G.
Відповідно до теореми 2 дерево G має кінцеві вершини. Нехай x1 - перша кінцева вершина в послідовності 1, 2, ..., p і нехай e1 = (x1, y1) - відповідне кінцеве ребро. Видалимо з дерева вершину x1 і ребро e1. Отримаємо нове дерево G1 з числом вершин p - 1. Знайдемо тепер перший кінцеву вершину x2 дерева G1 в послідовності вершин 1, 2, ... ..., p з множини {1, 2, ..., p} \ {x1}, далі візьмемо кінцеве ребро e2 = (x2, y2) і вилучимо з G1 x2 і e2. Цю процедуру послідовно повторюємо. Через (p - 2) кроку залишається дерево з двох вершин xp-1, yp-1 і одного ребра ep-1 = (xp-1, yp-1). Розглянемо послідовність вершин
s (G) = {y1, y2, ..., yp-2}.
Очевидно, що за даним дереву послідовність будується однозначно. Покажемо тепер, що по даній послідовності вершин s (G) дерево G можна відновити однозначно. У послідовності 1, 2, ..., p існують вершини, які не належать s (G). Виберемо першу з них x1 і побудуємо ребро e1 = (x1, y1). Потім видалимо x1 з послідовності 1, 2, ..., n і y1 видалимо з s (G). Аналогічним чином побудуємо ребро e2 = (x2, y2). Продовжуючи цей процес, ми однозначно відновимо дерево G. Розглянемо приклад.
Побудова коду
Відновлення
s (G)
s (G) і список вершин
(2,6,5,5,6) 1,2,3,4,5,6,7
(2)


(6,5,5,6) 2,3,4,5,6,7
(2,6)


(5,5,6) 3,4,5,6,7
(2,6,5)


(5,6) 4,5,6,7
(2,6,5,5)


(6) 5,6,7
(2,6,5,5,6)


Розглянутий приклад дозволяє відзначити наступні дві особливості:
1 У списку s (G) вершини можуть повторюватися.
2. При відновленні дерева останнє ребро з'єднує вершину yp-2 і залишилася в списку 1, 2, ..., p вершину не рівну yp-2.
Отже, існує взаємно однозначна відповідність між безліччю помічених дерев з p вершинами і безліччю послідовностей вершин s (G). Число таких послідовностей одно, очевидно, pp-2, що й потрібно було довести.
Відзначимо, що серед pp-2 помічених дерев з p вершинами можуть бути і ізоморфні.
Визначення 3. Підграф G1 (X1, E1) неорієнтованого графа G (X, E) називається каркасом, або кістяк графа G, якщо G1 - дерево і X = X1.
Теорема 4. Граф G (X, E) тоді і тільки тоді має каркасом, коли він зв'язний.
Доказ. Необхідність цього очевидна. Доведемо достатність. Нехай G (X, E) - зв'язний граф. З'ясуємо, чи є в графі G таке ребро, видалення якого не порушує зв'язності графа G. Якщо таких ребер немає, то граф є дерево, відповідно до теореми 1. Якщо ж таке ребро, наприклад e, існує, то викинемо його і прийдемо до графа G1 (X, E \ {e}). Потім зазначену процедуру проробляємо з графом G1 і т.д. Через кінцеве число кроків буде побудований, очевидно, каркас графа G. Теорема доведена.
Доказ теореми дає алгоритм побудови деякого каркаса в зв'язковому графі. Однак зв'язний граф може мати кілька каркасів, тому природно поставити завдання вибору каркаса, що задовольняє додатковим умовам.
Визначення 4. Графом з навантаженими ребрами (навантаженим графом) називається неорієнтований граф G (X, E), кожному ребру eÎE якого поставлено у відповідність число m (e) ³ 0, зване вагою або довжиною ребра e.
Аналогічно можна визначити навантажений орграф.
Поставимо задачу знаходження такого каркаса G1 (X, E1) в навантаженому графі G (X, E), для якого сума

мінімальна. Каркас з такою властивістю називається мінімальним каркасом. Відповідно до теореми 4 кожен навантажений зв'язний граф має мінімальний каркасом. Ця задача виникає при проектуванні ліній зв'язку та електропередач, доріг, трубопроводів і т.п., коли потрібно з'єднати системою каналів зв'язку задані вузли так, щоб будь-які два вузли були пов'язані (можливо, через інші вузли), а загальна довжина каналів зв'язку була мінімальною ; при цьому вузли можна вважати вершинами навантаженого графа, ваг ребер якого відповідає довжина можливого каналу зв'язку між відповідними вузлами. Тоді шукана мережу каналів буде мінімальним каркасом цього графа.

Алгоритм побудови мінімального каркасу

Нехай G (X, E) - зв'язний навантажений граф з p вершинами.
Крок 1. В якості першого ребра шуканого мінімального каркасу вибираємо ребро e1 з найменшою вагою m (e1). Якщо таких ребер кілька, то беремо будь-яке з них.
Крок 2. В якості другого ребра беремо ребро e2 з безлічі E \ {e1}, що має найменшу вагу m (e2), і таке, що множина {e1, e2} не містить простих циклів. Якщо таких ребер кілька, то беремо будь-яке з них.
Крок 3. В якості третього ребра вибираємо таке ребро e3 з безлічі E \ {e1, e2}, яка має найменшу вагу m (e2) і для якого безліч {e1, e2, e3} не містить простих циклів. Якщо таких ребер кілька, беремо будь-яке з них.
Зазначений процес повторюється і через деяке число k кроків дає безліч E = {e1, e2, ..., ek}, до якого не можна додати ребро без появи циклу. Підграф G1 (X, E1) і є мінімальним каркасом графа G (X, E).

Обгрунтування алгоритму

У силу властивості 6 з теореми 1 побудований підграф G1 (X, E1) є деревом, тому k = p -1. Доказ мінімальності каркаса G1 (X, E1) розіб'ємо на два етапи. Нехай спочатку G (X, E) - повний граф, у якого ваги всіх ребер різні, і хай G2 (X, E2) - мінімальний каркас графа G. Якщо E2 ¹ E1, то розглянемо el - перше з ребер безлічі E1, що не належить E2. У графі в силу властивості 6 теореми 1 існує єдиний простий цикл m. Цикл m містить ребро e0ÏE1. Граф G3 (X, E3), де , Не містить циклів і має n - 1 ребро, тому він є деревом. Безліч {e1, e2, ..., el-1, e0} міститься в E2 і тому не містить циклів. Тоді в силу розглянутого вище алгоритму m (e0)> m (el). Звідси випливає, що сумарна вага дерева G3 (X, E3) менше ваги дерева G2 (X, E2). Це суперечить мінімальності каркаса G2, тому E2 = E1 і G1 (X, E1) - єдиний мінімальний каркас графа G.
Нехай тепер G (X, E) - довільний навантажений зв'язний граф. Якщо m (e1) = m (e2), то зробимо заміну
m (e1) ® m '(e1) = m (e1) + e,
m (e2) ® m '(e2) = m (e2) + 2e,
взявши таке e, щоб збереглися співвідношення ваг m (e1) і m (e2) з іншими вагами. Зробимо граф G повним, додавши такі ребра di, що . В отриманому графі єдиним мінімальним каркасом буде каркас, отриманий за допомогою розглянутого алгоритму. Легко бачити, що цей каркас буде мінімальним і у вихідному графі G (X, E).
На рис.4 зображені навантажений граф G і його мінімальний каркас G1.

Рис. 4

ЛІТЕРАТУРА
1. Бєлоусов А.І., Ткачов С.Б. Дискретна математика: Підручник для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: изд-во МГТУ ім. Н.Е. Баумана, 2001 .- 744 с. (Сер. Математика в технічному університеті; Вип XIX).
2. Горбатов В.А. Фундаментальні основи дискретної математики. Інформаційна математика .- М.: Наука, Фізматліт, 2000 .- 544 с .- ISBN 5-02-015238-2.
Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Реферат
34.8кб. | скачати


Схожі роботи:
Опіковий шок як приватний вид опікової хвороби
Матриці графів
Приватний дитячий садок Півник
Державний і приватний сектор економіки
Метод орієнтованих графів
Дойл ak - Приватний детектив Шерлок Холмс
Основні поняття і визначення теорії графів
Мова обробки графів на базі JAVA
Моделі теорії графів для виділення контурів по градиентному зображенню
© Усі права захищені
написати до нас