Міністерство освіти Республіки Білорусь
Установа освіти
В«Білоруський державний університет
інформатики та радіоелектроніки В»
РЕФЕРАТ
на тему:
В«ДЕРЕВА І ЇХ ВЛАСТИВОСТІ (ПРИВАТНИЙ ВИД графів) В»
Мінськ, 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}.
Очевидно, що по даного дереву послідовність будується однозначно. Покажемо тепер, що по даної послідовності вер...
