Орієнтований граф без циклів називається орієнтованим ациклічним графом. [4]
Схему можна також представляти у вигляді орієнтованого ациклического графа. у якого вершини вхідний ступеня 0 (входи) позначені вихідними змінними; інші вершини (функціональні елементи) позначені функціями з базису (при цьому вхідні ступінь вершини повинна збігатися з кількістю аргументів її позначки); ребра помічені числами, що вказують номери аргументів; вершини вихідний ступеня 0 (виходи) позначені змінними, що описують результат роботи схеми. Уй, з яких ведуть ребра в дану вершину v, вершина v отримує значення у fv (yi. Ykv), де fv - базисна функція, якою позначена вершина. При переході до графу схеми ми опускаємо несуттєві привласнення, які жодного разу не використовуються на шляху до вихідних вершин, так що вони ніяк не впливають на результат обчислення. [5]
Доведіть або спростуйте, що для великих п всякий орієнтований ациклічний граф з п витоками і п виходами, що задовольняє умові на пропускні спроможності з упр. [6]
Лемма 5.12. Нехай G (У, Е) - орієнтований ациклічний граф з коренем г, a S (V, Т) - кістяк для нього з коренем г, побудоване пошуком в глибину. [7]
Говорячи неформально, можна сказати, що ми будуємо домінатор-ве дерево для даного орієнтованого ациклического графа G (V, E) у такий спосіб. Номери вузлів графа G міняємо на їх номери, породжені пошуком в глибину. Потім застосовуємо до G перетворення з лем 5.12 - 5.14. Вони виконуються двома взаємопов'язаними подпрограммами, одна з яких обробляє прямі ребра, а інша - поперечні. [8]
Мережева модель, що виражає послідовність виробництва продуктів, має вигляд множини не пов'язаних між собою орієнтованих ациклических графів. кожен з яких відповідає цільовому продукту. Вершини графа позначають проміжні і цільові продукти, а дуги - послідовність їх виробництва. [10]
Ми побудуємо алгоритм складності О (е log e), який обчислює домінаторное дерево для кореневого орієнтованого ациклического графа з е ребрами. Основна наша мета - показати, як комбінувати техніку цієї глави і попередньої. Алгоритм заснований на трьох лемах. [11]
Слова в алфавіті А будемо називати текстами в алфавіті А, мережею з текстів (Г - сети) - зв'язний орієнтований ациклічний граф такого вигляду. [12]
Орієнтований граф, що складається з декількох дерев, називається лісом. Ліси та дерева - настільки часто зустрічаються окремі випадки орієнтованих ациклических графів. що для опису їх властивостей варто ввести спеціальну термінологію. [13]
Нарешті відзначимо, що ця програма передбачає ациклічності відносини has share. Тим самим передбачається, що відображення відносини власності фактично є орієнтованим ациклічним графом. Насправді програма також є коректною при менш жорстких обмеженнях, а саме за умови ациклічності відносини controlled. Ця умова безпосередньо випливає з попереднього. [14]
Методи, розвинені в попередніх розділах цієї глави, примі Німи до абсолютно довільним графам. Але на практиці завдання найкоротшого шляху часто потрібно вирішувати для класу орієнтованих ациклических графів. [15]
Сторінки: 1 2