30. Ейлерів цикл у графі

Ейлерів цикл у неорієнтованому графі це цикл, що проходить кожне ребро рівно один раз. Ейлеровим циклом у зв‘язному мультиграфі назив. простий цикл який містить всі ребра графа. Ейлерів шлях – це простий шлях який містить всі ребра графа. Граф називається ейлеровим якщо він має ейлерів цикл.

31. Гамільтонів цикл у графі

Гамільтоновим назив. Цикл що містить всі вершини графа(з певерненням в ту саму вершину)

Гамільтонів шлях містить всі вершини графа(без повернення в ту саму вершину)

Плоским назив граф який можна зобразити на площині так щоб ніякі два його ребра не перетиналис

32. Планарний граф — граф, який може бути зображений на площині без перетину ребер.

Два графи назив гомеоморфними якщо їх можна отримати з одного графа додаванням до його ребер нових вершин степенем 2

33. Розфарбовування графів

Розфарбовуванням простого графа G назив. Таке приписування кольорів його вершинам що ніякі 2 суміжні вершини не набувають однакового кольору. Найменшу можливу кількість кольорів у розфарбовуванні назив. Хроматичним числом.

Якщо найбільший зі степенів вершин графа = r то цей граф можна розфарбувати в r+1 колір.

Будь-який планарний граф можна розфарбувати в 5 кольорів.

34. Основні означення та властивості дерев

Деревом називається простий граф зв‘язний без циклів. Граф який не міститьпростих циклів і скл. з К-компонентів назив лісом з дерев.Будь-яку вершину дерева можна означ. як корінь тоді кожне ребро отрим напрям.Дерево разом з виділеним коренем назив. кореневим деревом. Вершини дерева, які не мають синів назив. листками. Вершини що мають синів назив. внутрішніми.Кореневе дерево назив. м-арним якщо кожна його внутріш. Вершина має не більше ніж м-синів. Дерево назив м-арним якщо кожна його внутріш. вершина має точно м-синів.

35. Рекурсія. Обхід дерев

Рекурсія — метод визначення класу чи об'єктів методів попереднім заданням одного чи декількох (звичайно простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається.

Іншими словами, рекурсія — часткове визначення об'єкта через себе, визначення об'єкта з використанням раніше визначених. Рекурсія використовується, коли можна виділити самоподібність задачі. Визначення у логіці, що використовує рекурсію, називається індуктивним. Розглядаючи обхід бінарного дерева можна означити такі впорядкування:

1)обхід у прямому порядку(R A B)

2)обхід у внутрішньому порядку(A R B)

3)обхід у зворотньому порядку, або знизу вверх

Розглядаючи розв’язування задач як єдиний послідовний процес відвідування вершин дерева у повному порядку можна вважати їх розміщеннями одна за одною

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

36. Бінарне дерево пошуку

Бінарне дерево забезпечує дуже зручний метод організації данних у разі вик. якого можна легко знайти будь-які конкретні дання чи вмявити чи їх немає.Найнеефективніший спосіб пошуку це послідовний перелік всіх данних. Бінарне дерево дає змогу уникнути цього. Єдина умова введ. якогось лінійного порядку. У бінарному дереві пошуку кожній верш. присвоєно значення яке називається ключем. Ключ – це елем. якоїсь лінійно-впорядк. множини в якій будь-які два елементи можна порівняти.