Для доведення твердження застосуємо метод математичної індукції за кількістю вершин повного орграфа. База індукції: у повному орграфі з двома вершинами одна з них є джерелом (а інша – стоком). Припустимо, що будь-який повний орграф із n вершинами має джерело. Розглянемо довільний повний орграф G = (V, E) з n + 1 вершиною. Вилучивши одну з його вершин v, отримаємо повний орграф із n вершинами, для якого справджується припущення індукції. Отже, у ньому є принаймні одне джерело. Нехай це буде вершина w. Повернемо на місце вилучену вершину v зі всіма відповідними дугами. Оскільки граф G повний, то його вершини v і w з'єднані дугою. Якщо ця дуга веде з v у w (тобто (v, w) E), то джерелом у графі G буде вершина v. В іншому разі, коли (w, v) E, джерелом залишиться вершина w. ◄
3. Нумерацією орграфа G = (V, E) з n вершинами називатимемо взаємно однозначне відображення
f :V → Nn,
яке кожній вершині v V ставить у відповідність натуральне число f (v) із множини Nn = {1, 2, …, n}.
Довести, що для ациклічного орграфа G = (V, E) існує така нумерація f, що для будь-якої дуги (v, w) E виконується
f (v) < f (w).
Цю нумерацію називають правильною нумерацією, або топо
вершин орграфа G.
Неважко довести (методом від супротивного), що ациклічний орграф G завжди має принаймні один стік. Нехай u1 – стік орграфа G. Покладемо f(u1) = n і вилучимо з G вершину u1. Дістанемо ациклічний орграф G1, у якому існуватиме стік u2. Покладемо f(u2) = n – 1 і вилучимо u2 з G1. Продовжуючи цю процедуру, отримаємо шукану правильну нумерацію. ◄
Послідовність (4.4) називають напівмаршрутом, якщо кожна дуга еі цієї послідовності є такою, що або еi = (vi, vi + 1), або ei = (vi + 1, vi) (можна вважати, що при побудові напівмаршруту ми ігноруємо орієнтацію дуг орграфа). Аналогічно означають
напівланцюг, напівцикл і півконтур.
Орграф називають сильно зв'язним, якщо будь-які дві його вершини досяжні одна з одної. Орграф називають однобічно зв'язним, якщо для будь-яких двох його вершин принаймні одна досяжна з іншої. Орграф називають слабко зв'язним, якщо для
196
будь-яких двох його вершин існує напівмаршрут, що веде з однієї вершини в іншу. Маршрут в орграфі 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.Модель скінченного автомата використовують у програмному забезпеченні для розробки й аналізу поведінки різноманітних систем, що можуть перебувати у скінченній кількості відмінних один від одного станів. Прикладами таких систем можуть бути протокол безпечного (захищеного) обміну інформацією, протокол, що організує та контролює процедури електронної торгівлі та інших фінансових операцій у комп'ютерних мережах тощо.