Тема 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. Якщо граф включає непланарний підграф, то і сам граф непланарний.
.