Тема 13. Дерева і ліс.

Питання теми

1. Поняття дерева як ациклічного графа.

2. Поняття лісу.

3. Роль поняття дерева у різних прикладних задачах

4. Плоскі і планарні графи.

Основні терміни теми : дерево, ліс, планарність.

1. Дерева

Особливий інтерес представляють зв’язні ациклічні графи , які називаються деревами. Дерево на множині р вершин завжди має q = p - 1 ребер, тобто мінімальну кількість ребер, необхідну для того, щоб граф був зв’язним. Дійсно, дві вершини зв’язані одним ребром, і для зв’язку кожної подальшої вершини з попередньої необхідно ребро, таким чином, для зв’язку p вершин необхідно і достатньо (p – 1)  ребер.

При додатку до дерева ребра утворюють цикл, а при відокремленні хоча б одного ребра дерево розпадається на компоненти, кожний з яких представляє собою також дерево або ізольовану вершину (рис. 10, а).

2. Поняття лісу

Незв’язний граф, компонентами якого є дерева, називається лісом (ліс із k дерев, який вміщує p вершин, має p - k ребер). Проілюструємо це на прикладі дерева (рис. 10, а), який перетворюється в циклічний граф додаванням ребра (рис. 10, б) та розпадається на ліс з двох дерев Т1  і  Т2 при відокремленні ребра e (рис. 10, в).

   

  а)  б)

 

в)

Рис. 10. Дерево.

а - дерево; б - утворення циклу при додаванні ребра;

в – ліс, який утворюється після відокремлення ребра е.

Дерева вважаються суттєво різними, якщо вони не ізоморфні. На рис. 11 показані всі можливі різні дерева з шістьма вершинами. З збільшенням кількості вершин кількість різних дерев сильно збільшується. Серед дерев розрізняють два часних випадки: послідовне дерево та зоряне дерево.

 

Рис. 11. Суттєво різні дерева з шістьома вершинами.

Розглядають також дерева з орієнтованими ребрами (дугами). Орієнтоване дерево  називається прадеревом з коренем V , якщо існує шлях між вершиною V  та якою завгодно його вершиною. Прадерево має тільки один корінь.

 

Рис. 12. Прадерево з коренем v

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

Ребра графа, які належать його дереву називаються гілками. Якщо дерево покриває граф, тоді підмножина його ребер розбивається на дві підмножини: підмножину гілок та підмножину ребер доповнення дерева, що називаються хордами. При цьому зв’язаний (p,q)-граф вміщує v = p - 1 гілок та g = q – p + 1 хорд. Якщо граф незв’язний, то сукупність остовів k його компонент створює покриваючий ліс. У цьому випадку v = p – k  i g = q – p + k.

Р. Роль поняття дерева у різних прикладних задачах

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

.

1. Плоскі і планарні графи

 

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

 

 

в

  а)

  б)  в)

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

 

Рис. 13

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

Слід зауважити, що визначення плоского і планарного графів зберігаються і для мультиграфів, і для псевдографів. Перш ніж перейти до пошуку критерію планарності графа, розглянемо добре відому задачу-головоломку про три будинки і три колодязі. Є три будинки: 1, 2, 3 і три колодязі: 4, 5, 6 (рис. 14). Кожний мешканець може користуватися будь-яким із трьох колодязів. Одного дня мешканці будинків вирішили прокласти доріжки до колодязів так, щоб виключити можливість зустрічі, тобто прокласти доріжки так, щоб вони не перетинались. Виникає питання: чи можна прокласти доріжки так, як цього вимагає задача? Всі спроби прокласти дев'ять доріжок так, щоб вони не перетинались і з'єднували будинки з колодязями, закінчуються невдало. Виявляється, що це зовсім не випадково.

Наведена задача дає привід думати, що існують не тільки планарні графи.

 

Рис. 14

Безпосередньо з визначення планарності графа випливають такі очевидні твердження:

Твердження 1. Всякий підграф планарного графа теж планарний.

Твердження 2. Якщо граф включає непланарний підграф, то і сам граф непланарний.

.