будь-яких двох його вершин існує напівмаршрут, що веде з однієї вершини в іншу. Маршрут в орграфі G називають кістяко вим, якщо він містить усі вершини орграфа G.
Орграф, у якому є джерело й немає жодного півконтуру, на-
зивають кореневимдеревом.
Вхідне дерево − це орграф, який має стік і не має жодного півконтуру.
Орграф називають функціональним, якщо напівстепінь виходу кожної його вершини дорівнює 1. Орграф називають ін'єктив ним, якщо напівстепінь заходу кожної його вершини дорівнює 1.
Ейлеровим контуром в орграфі G називають контур, що містить усі дуги орграфа G. Ейлеровим орграфом називають орграф, у якому є ейлерів контур. Ейлеровим ланцюгом називають незамкнений ланцюг, що містить усі дуги орграфа.
Нижченаведене твердження можна довести так само, як і для звичайних графів.
Слабко зв'язний орграф G = (V, E) є ейлеровим тоді й тільки тоді, коли напівстепінь виходу будь-якої його вершини дорівнює напівстепеню її заходу.
Гамільтоновим контуром називають контур, що містить усі вершини орграфа. Орграф, який має гамільтонів контур, нази-
вають гамільтоновим орграфом.
Простий незамкнений ланцюг, що містить усі вершини орграфа, називають гамільтоновим.
Повний орграф завжди гамільтонів.
Орграф G = (V, E) називають транзитивним, якщо з (v, w) Е і (w, u) Е випливає (v, u) Е.
Існує взаємно однозначна відповідність між множиною всіх безконтурних транзитивних орграфів G = (V, E) із множиною вершин V = {v1, v2, …, vn} і петлями в кожній вершині та множиною всіх відношень часткового порядку на V. Ця бієкція встановлюється так: орграфу G = (V, E) відповідає відношення R
на V таке, що (vi, vj) R тоді й тільки тоді, коли (vi, vj) E, vi, vj V.
197
Завдання для самостійної роботи
1. Нехай задано орграф G = (V, E): (а) V = {1, 2, 3, 4, 5},
E = {(1, 3), (2, 1), (2, 5), (3, 4), (4, 5), (5, 1), (5, 2)};
(б) V = {a, b, c, d}, E= {(a, c), (a, d), (b, a), (b, d), (c, b), (d, c)}.
Побудувати діаграму, матриці суміжності та інцидентності для кожного з цих орграфів.
2.Як визначити напівстепені виходу та заходу певної вершини орграфа G за його матрицею суміжності A?
3.Чи існує орграф із трьома вершинами, напівстепені виходу вершин якого дорівнюють 2, 2 і 0, а відповідні напівстепені за-
ходу − 2, 1 та 1?
4.Довести, що відношення досяжності на множині вершин орграфа транзитивне.
5.Довести, що в повному орграфі може бути не більше однієї недосяжної й не більше однієї тупикової вершини.
6.Довести, що в будь-якому повному орграфі є принаймні один стік.
7.Довести, що для транзитивного повного орграфа завжди існує правильна нумерація.
8.Нехай A − матриця суміжності орграфа G. Довести, що елемент aij(k ) i-го рядка та j-го стовпчика матриці Ak дорівнює
кількості шляхів довжиною k, які ведуть в орграфі G з вершини з номером i у вершину з номером j.
4.12.Граф як модель. Застосування теорії графів
Останнім часом графи й пов'язані з ними методи досліджень використовують практично в усіх розділах сучасної математики, зокрема в дискретній математиці.
Граф – це математична модель найрізноманітніших об'єктів, явищ і процесів, досліджуваних і використовуваних у науці, техніці та на практиці. Коротко опишемо найвідоміші застосування теорії графів.
Наприклад, у вигляді графа можна зображувати такі об'єкти:
198
•електричні та транспортні мережі;
•інформаційні й комп'ютерні мережі;
•карти автомобільних, залізничних і повітряних шляхів, газо- й нафтопроводів;
•моделі кристалів;
•структури молекул хімічних речовин;
•моделі ігор;
•різні математичні об'єкти (відношення, частково впорядковані множини, ґратки, автомати, ланцюги Маркова, алгоритми та програми);
•лабіринти;
•плани діяльності чиплани виконанняпевнихробіт(розклади);
•генеалогічні дерева тощо.
Наведемо приклади застосування теорії графів:
•пошук зв'язних компонент у комунікаційних мережах;
•пошук найкоротших, найдешевших і найдорожчих шляхів у комунікаційних мережах;
•побудова кістякового дерева, тобто досягнення зв'язності з найменшою можливою кількістю ребер;
•пошук максимальної течії для транспортної мережі, у якій означеновхіднітавихіднівершиниіпропускніспроможностіребер;
•ізоморфізм графів: ідентичність структур молекул(ізометрія);
•відшукання циклів графів:
−гамільтонів цикл: обійти всі вершини графа, побувавши в кожній з них лише один раз (задача комівояжера);
−ейлерів цикл: обійти всі ребра (здійснити контроль дієздатності всіх ланок мережі);
•розфарбування графів: розфарбування географічних карт, укладання розкладів, розміщення ресурсів тощо;
•планарність графів: проектування друкованих електронних та електричних схем, транспортних розв'язок тощо;
•знаходження центрів графа – вершин, максимальна відстань від яких до решти вершин графа мінімальна (столиць) тощо.
199
Розділ 5 ТЕОРІЯ АВТОМАТІВ
Однією з найпопулярніших і найпоширеніших математичних моделей, які активно й успішно використовувались і використовуються в теорії та практиці сучасної комп'ютерної науки (інформатики), є скінченний автомат. Варто назвати лише деякі найважливіші приклади застосування цієї моделі.
1.Опис функціонування та логічного проектування найрізноманітніших схем і пристроїв дискретної дії. Зокрема, скінченний автомат широко використовують для розробки й аналізу схем і пристроїв обчислювальної техніки як модель для інтерпретування мікропрограм виконання команд ЕОМ тощо.
2.Скінченний автомат – зручний і ефективний засіб для опису та створення важливого компонента стандартного компілятора мови програмування, який називають лексичним аналізато ром. Цей програмний модуль відповідає за розбивку вхідного тексту на логічні одиниці: ідентифікатори, ключові (резервовані) слова, константи, спеціальні знаки тощо.
3.Скінченний автомат є складовою частиною програмного забезпечення, призначеного для перегляду великих текстових масивів даних (наприклад набору web-сторінок) з метою пошуку
вних потрібної інформації. Ключем для такого пошуку служать або ключові слова, або певні послідовності символів (образи).
4.Модель скінченного автомата використовують у програмному забезпеченні для розробки й аналізу поведінки різноманітних систем, що можуть перебувати у скінченній кількості відмінних один від одного станів. Прикладами таких систем можуть бути протокол безпечного (захищеного) обміну інформацією, протокол, що організує та контролює процедури електронної торгівлі та інших фінансових операцій у комп'ютерних мережах тощо.
5.1.Поняття скінченного автомата. Методи задання автоматів
Скiнченним автоматом (далі – просто автоматом) називають систему
A = (X, Y, U, δ, λ),
у якій X = {x1, x2, …, xm} та Y = {y1, y2, …, yn} – скінченні
жини (алфавіти) відповідно вхідних і вихідних сигналів, U = {a1, a2, …, as} – множина внутрішніх станів автомата. Функ-
ції δ та λ описують алгоритм функціонування (поведінку) автомата A. Функцію δ: U × X → U називають функцією переходів, а
λ: U × X → Y – функцією виходів автомата A.
Необхідно підкреслити одну особливість моделі автомата, яка випливає з її подальшої фізичної інтерпретації. Вважаємо, що автомат A функціонує в дискретному часі, тобто час функціонування автомата розбито на відрізки однакової довжини – та кти. Межи тактів t називають моментами абстрактного дискретного автоматного часу й нумерують натуральними числами, починаючи з одиниці. Значення вхідних і вихідних сигналів та значення станів автомата можуть змінюватися тільки в моменти автоматного часу t = 1, 2, ….
Якщо позначимо через
x(t) X, y(t) Y, a(t) U
значення вхідного й вихідного сигналів і стану автомата в момент автоматного часу t, то робота автомата A описуватиметься співвідношеннями
a(t + 1) = δ(a(t), x(t)), y(t) = λ(a(t), x(t)). (5.1)
Співвідношення (5.1) називають канонічними рівняннями автомата A.
Перше із канонічних рівнянь можна прочитати так: стан автомата A в будь-який момент автоматного часу t + 1 однозначно визначається сигналом, поданим на вхід автомата, і станом автомата A в попередній момент автоматного часу. При цьому кажемо, що автомат A переходить зі стану a(t) у стан a(t + 1).
У математичній моделі автомата можна вважати, що такий перехід відбувається миттєво (стрибкоподібно). За фізичної ін-
201