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

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

Гілка до вершини 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. Таблична форма дерева залежностей

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