Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

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




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

<== попередня сторінка | наступна сторінка ==>
Основні визначення | Десяткове кодування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.003 сек.