МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
А Б В ГДва вузли зв’язані дугою, яка вказує на бінарний зв’язок. Множина дуг утворює дерево, вузли якого відповідно пов’язані бінарним зв’язком. Якщо у графі є дуга, то кажуть, що вузли u і v зв’язані зв’язком R, який записують uRv. Скінченний орієнтований граф називається деревом, якщо: а) у ньому наявний єдиний вузол, який не є кінцем жодної дуги, він називається коренем; б) будь-який вузол цього графа, відмінний від кореня, є кінцем лише однієї дуги; в) у цьому графі немає замкнених шляхів (тобто шляхів, кінці яких збігаються з початками. Отже, зображені графи А і Б є деревами, а В і Г – ні. У графі В є два вузли, які не є кінцями будь-якої дуги, тобто корінь не єдиний (не виконано умову а). Крім того, у ньому є вузол, до якого йдуть дві дуги (не виконано умову б). Для графа Г не виконані умови а і в. У ньому ми бачимо замкнений шлях і відсутність кореня. Визначимо кілька понять, важливих для побудови й інтерпретації дерева залежностей. 1. Якщо з u до v йде дуга, то це означає, що u підпорядковує v. Якщо з u до v йде шлях, то v залежить від u. 2. Вузол дерева, який не є початком будь-якої дуги, називається висячим. 3. Множина всіх вузлів дерева, які підпорядковані вузлу u, називається кущем цього вузла, а кількість підпорядкованих вузлів у кущі – його шириною, або шириною розгалуження. 4. Рівнем вузла u називається кількість вузлів у шляху, який іде від кореня до вузла u. Кількість вузлів у найдовшому шляху дерева називається кількістю рівнів у дереві. 5. Дерево, на множині вузлів якого задано відношення порядку, тобто кожен вузол має свій номер (у реченні – кожна словоформа нумерується зліва направо), називається розташованим. Зображувати розташоване дерево треба так: потрібно задати систему координат, у якій по осі абсцис – номери вузлів, а по осі ординат – номери рівнів. Кожен вузол зображений точкою у цій системі координат. Кожна дуга (u, v) – це відрізок, який з’єднує u і v.
0 1 2 3 4 5 6 7 8 9
5 U1 U2 U3 U4 U5 U6 U7 U8 U9
На зображеному розташованому дереві: кількість вузлів – дев’ять; кількість рівнів – п’ять; ширина розгалуження вузла u3 – три; ширина розгалуження вузла u6 – один; група залежностей вузла u7 – складається з вузлів u4, u5, u6, u7, u8, u9; до групи залежностей вузла u3 (корінь дерева) входять усі вузли дерева. На зображеному дереві можна визначити ще три терміни: зиґзаґ – максимальна кількість змін напрямку шляху (на нашому дереві зиґзаґ дорівнює трьом, оскільки напрямок шляху – u3 u7 u4 u6 u5 змінювався тричі). Кількість вузлів, розташованих між вертикальними лініями координатної сітки, які проходять через початок і кінець дуги (u, v), називається протяжністю цієї дуги. У нашому графі максимально довгою є дуга u3 u7 з протяжністю 4. Розташоване дерево називається проективним, якщо виконані дві умови: а) жодні дуги не перетинаються; б) жодна дуга, що виходить з вузла u, не перетинає вертикальних ліній координатної сітки, які проходять через верхні вузли. Наведемо приклади непроективних дерев: а) б)
U1 U2 U3 U4 U5 U1 U2 U3
U1 U2 U3 U4 U5 (в) Є сім розташованих проективних дерев, утворених трьома вузлами і двома дугами, для яких О. Падучева запропонувала таку термінологію:
ліве і праве покриття
ліва і права доріжка
лівий і правий кут
|
||||||||
|