Центроїд дерева
Центроід дерева - розділ Транспорт, Неорієнтовані графи Гілка До Вершини V Дерева - Це Максимальний Підгр.
Гілка до вершиниvдерева - це максимальна підграфа, що міститьvяк висяча вершина. Вага вершиниk- максимальний розмір її гілок.Центроїд (або центр мас) дереваC– безліч вершин з найменшою вагою:C= vc(v) = >.
Вага будь-якого листа дерева дорівнює розміру дерева. Висота дерева з коренем, розташованим у центроїді, не більша за найменшу вагу його вершин.
Вільне дерево порядкуnз двома центроїдами має парну кількість вершин, а вага кожного центроїду дорівнюєn/2.
Теорема 14.3 (Жордана).Кожне дерево має центроїд, що складається з однієї або двох суміжних вершин.
Приклад 14.1. Знайти найменшу вагу вершин дерева, зображеного на рис. 14.1, та його центроїд.
Рішення. Очевидно, що вага кожної висячої вершини дерева порядкуnдорівнюєn– 1. Висячі вершини не можуть скласти центроїд дерева, тому виключимо з розгляду вершини 1, 2, 4, 6, 12, 13 і 16. Для решти вершин знайдемо їх вагу, обчислюючи довжину (розмір) їх гілок.
Число гілок вершини дорівнює її ступеню. Вершини 3, 5 і 8 мають дві гілки, розміри яких рівні 1 і 14. До вершини 7 підходять чотири гілки розміром 1, 2, 2 і 10. Таким чином, її вага . Аналогічно обчислюються ваги інших вершин: , , . Мінімальна вага вершин дорівнює 8, отже центроїд дерева утворюють дві вершини з такою вагою: 11 і 15.
Ця тема належить розділу:
Неорієнтовані графи
Основні визначення кожне ребро e з e інцидентно рівно двом вершинам і.. цикли.. маршрут у якому початок і кінець збігаютьсяциклічний циклічний маршрут називається циклом якщо він ланцюг.
Що робитимемо з отриманим матеріалом:
Всі теми цього розділу:
Основні визначення Граф - це сукупність двох множин: вершин
Радіус, діаметр і центр графа Обчислення відстаней і визначення маршрутів у графі є одним з найбільш очевидних і практичних завдань, що виникають у теорії графів. Введемо деякі необхідні визначення.
Ейлерова ланцюг Маршрут у неографі, в якому всі ребра різні, називається ланцюгом. Ланцюг у графі називається ейлерової, якщо вона містить усі ребра та всі вершини графа.
Реберний граф Розглянемо два графи G і L(G). Граф G має довільну форму, а вершини графа L(G) розташовані на ребрах графа G. У цьому випадку граф L(G) називається
Розмальовка графа, хроматичний поліном Припустимо, що маємо завдання: розфарбувати карту світу те щоб кожна країна мала свій власний колір. Оскільки на світі існує кілька сотень держав, то, природно, потребує
Ранг-поліном графа Ранг графа визначається як , де n - число вершин, k - число компонент зв'язності графа. До
Основні визначення Ребро у графі G може бути орієнтованим і мати початок та кінець. Таке ребро називається
Маршрути в орграфі Завдання, пов'язані з маршрутами в орграфі, мають велике практичне значення, що і дає стимул до розвитку та вдосконалення методів їх вирішення. Найчастіше постає питання про мінімальні та макс
Транзитивне замикання Прямим (декартовим) твором множин A і B називається безліч
Компоненти сильної зв'язності графа Поняття сильної зв'язності відноситься тільки до орграфів. Основа орграфа – неограф із тими самими вершинами, алеребрами замість відповідних дуг. Орграф називає
Основні визначення Дерево - зв'язковий граф без циклів. Ліс (або ациклічний граф) – неограф без циклів. Компонентами лісу є дерева.
Десяткове кодування Дерева є важливим видом графів. За допомогою дерев описуються бази даних, дерева моделюють алгоритми та програми, їх використовують у електротехніці, хімії. Однією з актуальних завдань