МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||
А Б В ГДва вузли зв’язані дугою, яка вказує на бінарний зв’язок. Множина дуг утворює дерево, вузли якого відповідно пов’язані бінарним зв’язком. Якщо у графі є дуга, то кажуть, що вузли 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 (в) Є сім розташованих проективних дерев, утворених трьома вузлами і двома дугами, для яких О. Падучева запропонувала таку термінологію:
ліве і праве покриття
ліва і права доріжка
лівий і правий кут
|
||||||||
|