• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Центроїд дерева

Гілка до вершини v дерева – це максимальний підграф, що містить|утримує| v як висячої вершини. Вага вершини k – найбільший розмір її гілок. Центроїд (або центр мас) дерева C – безліч вершин з|із| найменшою вагою: C = {v| з|із|(v)= }.

Вага будь-якого листа|аркуша| дерева рівна розміру дерева. Висота дерева з|із| коренем, розташованим|схильним| в центроїді, не більше найменшої ваги його вершин.

Вільне дерево порядку|ладу| n з|із| двома центроїдами має парну кількість вершин, а вага кожного центроїда рівна n/2.

Теорема 14.3 (Жордана|). Кожне дерево має центроїд, що складається з однієї або двох суміжних вершин.

Приклад|зразок| 14.1. Знайти найменшу вагу вершин дерева, зображеного|змальованого| на мал. 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.

Читайте також:

1. Вимоги до побудови «дерева цілей».
2. Довідником називається об'єкт програми, що дозволяє користу вачу вводити, зберігати і одержувати інформацію, структуруючи її у вигляді дерева.
3. Догляд за деревами і чагарниками
4. Метод аналізу ризику з використанням дерева рішень
5. Побудова дерева цілей
6. Сортування за допомогою дерева
7. Структуруючи її у вигляді дерева.
8. Таблична форма дерева залежностей

Переглядів: 1038