Курсова робота на тему: «ДЕРЕВА ТА ЇХ ЗАСТОСУВАННЯ»

Зміст

Вступ ……………………………………………………………………………………3

  1. Дерева (теорія графів)………………………………………………..5
  2. Дерева та їх прості властивості …………………………..……8
  3. Зв’язані визначення ……………………………………………10
  4. Двійкове дерево. ……………………………………………….11
  5. N-арні дерева .…………………………………………………..12
  6. Властивості дерев ……………………………………………….12
  7. Підрахунок дерев…………………………………………..……12
  8. Кодування дерев..………………………………………………13
  9. Побудова не пересічних остових дерев ………………..……14

Висновок………………………………………………………………………19

Вступ

Роком виникнення теорії графів одностайно вважається рік 1736, коли Леонард Ейлер опублікував розв’язок так званої задачі про кенігсберзькі мости, а також знайшов загальний критерій існування Ейлерового циклу в графі.

Отримання дальших суттєвих результатів у цій галузі датують серединою ХIХ століття. Однак початок проведення активних систематичних досліджень та становлення теорії графів як окремого авторитетного розділу сучасної математики відбулося ще майже 100 років по тому, тобто в середині ХХ століття. Саме з цього часу граф стає однією з найпоширеніших і найпопулярніших математичних моделей у багатьох сферах науки і техніки. Картинка у вигляді набору точок на площині та ліній, проведених між деякими з них, стала зручною і наочною формою зображення найрізноманітніших об’єктів, процесів та явищ.

Великою мірою це пов’язано з виникненням, бурхливим розвитком та поширенням електронних обчислювальних машин і, як наслідок, значним зростанням ролі задач дискретного характеру. Математика від “обслуговування” переважно фізики переходить до проникнення своїх методів у інші сфери людської діяльності. Одним з потужних інструментів такого проникнення є граф.

Із суто формальної точки зору граф можна розглядати як один з різновидів алгебраїчної системи (а саме, як модель), а отже, і всю теорію графів як розділ сучасної алгебри. Справді, результати та методи алгебри широко використовуються в теорії графів. Однак за останні півстоліття активного інтенсивного та екстенсивного розвитку теорія графів виробила свою достатньо специфічну власну проблематику і методологію. На сьогодні теорія графів є однією зі складових математичного апарату кібернетики, важливим розділом дискретної математики. Тому теорія графів включається до навчальних програм університетів і технічних вузів як окрема дисципліна, або як розділ курсу “Дискретна математика”.

Безумовно, в невеликому навчальному посібнику неможливо викласти весь спектр досягнень сучасної теорії графів. Метою посібника є ознайомлення з основами теорії графів, деякими класичними проблемами теорії та методами їх розв’язання. Цей ввідний курс повинен полегшити зацікавленому читачеві подальше знайомство з результатами та різноманітними застосуваннями теорії графів за допомогою монографій і підручників, список яких наведено в кінці посібника.

Крім традиційних, можна сказати, класичних розділів теорії графів до матеріалу посібника включено фрагмент теми, яку відносять до прикладної теорії алгоритмів і називають “Алгоритми на графах”, або ширше “Комбінаторні алгоритми” .

Дещо спрощено відмінність різних підходів до однієї й тієї ж проблеми, пов’язаної з графами, можна продемонструвати на прикладі задачі перевірки ізоморфності двох заданих графів. Класична (абстрактна) теорія алгоритмів констатує, що ця проблема є розв’язною. Класична теорія графів уточнює, що для її розв’язання потрібно перебрати і перевірити не більше, ніж n! варіантів (n кількість вершин в обох графах). Прикладна теорія алгоритмів (і зокрема, її розділ під назвою “Алгоритми на графах”) займається конструюванням нетривіальних процедур, що дозволяють визначити, чи є задані графи ізоморфними, і в більшості випадків здійснити цю перевірку достатньо ефективно за рахунок суттєвого скорочення перебору можливих варіантів.

Розділ “Алгоритми на графах” є своєрідним містком між класичною теорією графів та прикладною теорією алгоритмів і програмуванням. Цей місток з кожним роком розширюється і міцніє. Деякі математики вже сьогодні відносять розділ “Алгоритми на графах” до загальної теорії графів.

1. Дерева (теорія графів)

Дерева
це особливий і дуже важливий клас графів. Особлива роль дерев визначається як широким їхнім застосуванням у різних галузях науки і практики, так і тим особливим положенням, яке дерева займають у самій теорії графів. Останнє випливає з граничної простоти будови дерев. Часто при розв’язуванні різних задач теорії графів їхнє дослідження починають з дерев. Зокрема, порівнюючи нескладною є проблема перевірки ізоморфності дерев.

Граф без циклів називається ациклічним.

Ациклічний зв’язний граф називається деревом.

Довільний ациклічний граф називається лісом.

Очевидно, що зв’язними компонентами лісу є дерева, і тому, кожен ліс може бути зображений у вигляді прямої суми дерев.

Існують й інші, рівносильні наведеному, означення дерева, які можна розглядати як характеристичні властивості дерева.

Теорема1: Для графа G  =(V,E ), |V |=n, |E |=m такі твердження рівносильні:

1) G дерево (ациклічний зв’язний граф);

2) G зв’язний граф і m =n 1;

3) G ациклічний граф і m = n 1;

4) для будь-яких вершин v і w графа G існує лише один простий ланцюг, що з’єднує v і w ;

5) G ациклічний граф такий, що коли будь-які його несуміжні вершини v i w з’єднати ребром (v,w), то одержаний граф міститиме рівно один цикл.

Доведення. Для доведення теореми покажемо виконання такого ланцюжка логічних слідувань: 1) Þ 2), 2) Þ 3), 3) Þ 4), 4) Þ 5) і 5) Þ 1).

Оскільки відношення логічного слідування є транзитивним, то звідси випливатиме рівносильність усіх п’яти тверджень.

Для тривіального графа G (n = 1) справедливість твердження теореми очевидна, тому вважатимемо, що n >1.

1)Þ 2). Доведемо це твердження методом математичної індукції за значенням n.

Для n = 2 умову 1) задовольняє тільки один граф K2, він же задовольняє й умову 2).

Припустімо, що твердження виконується для всіх дерев з кількістю вершин n £ t (t ³ 2). Розглянемо довільне дерево G =(V,E ), в якому t +1 вершина. Вилучимо з G деяке ребро e ÎE. Отримаємо граф G ¢, який складається з двох ациклічних зв’язних компонент, тобто з двох дерев T1 і T2. Нехай дерево T1 має n1 вершин і m1 ребер, а дерево T2
n2 вершин і m2 ребер, n1 £ t і n2 £ t. За припущенням індукції маємо: m1= n1 1 і m2= n2 1. Отже, для зв’язного графа G виконується m = m1+ m2 = (n1 1)+(n2 1)+1= =n1+n21=(t +1)1=t.

2)Þ 3). Від супротивного. Припустімо, що в графі G є цикл. Вилучивши в G довільне ребро E цього циклу, дістанемо зв’язний граф G ¢, в якому n 2 ребра. Отже, граф G ациклічний.

3)Þ 4). Знову скористаємось методом доведення від супротивного. Припустімо, що для графа G виконується умова 3), але граф G є незв’язний і має k компонент зв’язності. Тоді кожна з цих зв’язних компонент Ti є ациклічною, тобто деревом. Нехай дерево Ti має ni вершин і mi ребер, i=1,2,…,k. З доведеного вище маємо mi = ni 1, i =1,2,…,k. Тоді n 1=m = m1+m2+…+mk=(n1 1)+(n2 1)+…+(nk 1)=(n1+n2+…+nk) k=n  k. Отже, k = 1 і G є зв’язним графом.

Відтак, припустімо, що граф G задовольняє умову 3), але має дві вершини v і w, які можуть бути з’єднані двома різними простими ланцюгами. Ці ланцюги утворюють циклічний маршрут, що веде з v у v і обов’язково містить у собі деякий цикл (доведіть це самостійно). Останнє суперечить умові 3).

4)Þ 5). Якщо припустити, що в графі G є цикл, тоді будь-які дві вершини цього циклу можуть бути з’єднані між собою принаймні двома простими ланцюгами. Отже, G ациклічний граф. Візьмемо будь-які дві несуміжні вершини v і w у графі G і додамо до нього ребро (v,w); дістанемо граф G  ¢. У графі G¢ є один цикл Z, який складається з простого ланцюга, що веде з v у w у графі G, та доданого ребра (v,w). Припустімо, що в графі G ¢
є ще один цикл Z1 (Z1 
¹ Z). Цикли Z1 і Z мають спільні ребра (у противному разі Z1 є циклом ациклічного графа G ). Якщо серед цих ребер немає ребра (v,w), то знову отримаємо, що Z1 є цикл у графі G. Отже, цикли Z і Z1 мають спільне додане ребро (v,w). Тоді частина циклу Z, що веде з v у w, разом з частиною циклу Z1, що веде з w у v, утворює замкнений (циклічний) маршрут, що веде з v у v у графі G. Зазначені частини циклів Z і Z1 не збігаються, тому цей циклічний маршрут міститиме в собі цикл, що суперечить ациклічності графа G.

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Dereva Ta Jih Zastos (110.0 KiB, Завантажень: 14)

Сторінка: 1 2 3
завантаження...
WordPress: 23.28MB | MySQL:26 | 0,420sec