еннями на досяжність є побудова допоміжного графа, що має більшу кількість вершин, і володіє наступним властивістю: допустимому шляху на вихідному графі з обмеженнями відповідає деякий шлях на допоміжному графі, а неприпустимого шляху не відповідає ні один шлях. Алгоритм побудови такого графа залежить від виду вводяться обмежень. На допоміжному графі, таким чином, всі шляхи є допустимими, а дуги - рівноправними, і його можна розглядати як звичайний орієнтований граф. Для графів з нестандартними досяжних описаних видів розглянуті класичні завдання про найкоротший шлях з вершини в вершину, про максимальний потік в мережі з нестандартною досяжністю і про випадкових блуканнях на таких графах. Найбільшу складність викликають дві останні завдання, так як при побудові допоміжного графа збільшується не тільки кількість вершин, але й кількість дуг. При цьому необхідно правильно розпорядиться вагами дуг, за якими будується кілька дуг на допоміжному графі. Серйозного осмислення щоразу вимагає і перенесення відповідного результату з допоміжного графа на основній граф.
Цілі і завдання роботи. Мета полягає у вивченні графів з нестандартними досяжними, розробці алгоритмів розв'язання задач на таких графах, описі нового класу динамічних графів, програмної реалізації отриманих алгоритмів. <В
Глава 1. Граф. Загальне уявлення
У математичній теорії графів та інформатики граф - це сукупність об'єктів зі зв'язками між ними.
Об'єкти представляються як вершини, або вузли графа, а зв'язки - як дуги, або ребра. Для різних областей застосування види графів можуть змінюватися спрямованістю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребрах.
Багато структури, які мають практичний інтерес в математики та інформатики, можуть бути представлені графами. br/>В
неорієнтовані граф з шістьма вершинами і сім'ю ребрами
Граф або неорієнтовані граф G - це впорядкована пара G: = (V, E), для якої виконані наступні умови:
V це безліч вершин або вузлів, E це безліч пар (у разі неорієнтованого графа - невпорядкованих) вершин, званих ребрами. V (а значить і E) зазвичай вважаються кінцевими множинами. Багато хороші результати, отримані для кінцевих графів, невірні (або будь-яким чином відрізняються) для нескінченних графів. Це відбувається тому, що ряд міркувань стають помилковими у разі нескінченних множин.
Вершини і ребра графа називаються також елементами графа, число вершин у графі | V | - порядком, число ребер | E | - розміром графа.
Вершини u і v називаються кінцевими вершинами (або просто кінцями) ребра e = {u, v}. Ребро, у свою чергу, з'єднує ці вершини. Дві кінцеві вершини одного і того ж ребра називаються сусідніми.
Два ребра називаються суміжними, якщо вони мають спільну кінцеву вершину.
Два ребра називаються кратними, якщо безлічі кінцевих вершин збігаються.
Ребро називається петлею, якщо його кінці збігаються, тобто e = {v, v}.
Ступенем degV вершини V називають кількість ребер, для яких вона є кінцевий (при цьому петлі вважають двічі).
Вершина називається ізольованою, якщо вона не є кінцем ні для одного ребра; висячої (або листом), якщо вона є кінцем рівно одного ребра.
Орієнтований граф (Скорочено орграф) G - це впорядкована пара G: = (V, A), для якої виконані наступні умови:
V це безліч вершин або вузлів,
A це безліч (Впорядкованих) пар різних вершин, званих дугами або орієнтованими ребрами.
Дуга - це упорядкована пара вершин (v, w), де вершину v називають початком, а w - кінцем дуги. Можна сказати, що дуга vw веде від вершини v до вершини w.
Формально, орграф D = (V, E) є безліч E впорядкованих пар вершин. p> Дуга {u, v} інцидентна вершин u і v. При цьому говорять, що u - початкова вершина дуги, а v - кінцева вершина.
Орграф, отриманий з простого графа (Простий граф - граф, в якому немає кратних ребер і петель.) орієнтацією ребер називається спрямованим. На відміну від останнього, в довільному простому орграфе дві вершини можуть з'єднуватися двома різноспрямованими дугами.
Спрямований повний граф називається турніром. Повний граф - простий граф, в якому кожна пара різних вершин суміжна. Повний граф з n вершинами має n (n - 1)/2 ребер і позначається Kn. Є регулярною графом ступеня n - 1. br/>
язність
Маршрутом в орграфе називають чергуються послідовність вершин і дуг, виду v0 {v0, v1} v1 {v1, v2} v2 ... vn (вершини можуть повторюватися). Довжина маршруту - кількість дуг в ньому.
Шлях є маршрут в орграфе без повторюваних дуг, простий шлях - без повторюваних вершин. Якщо існує шлях з однієї вершини в іншу, то друга вершина досяжна з першою.
Контур є замкнутий шлях.
Для полумаршрута знімається обмеження на напрям дуг, аналогічно визначаються полупуть і полуконтур.
Орграф сильно зв'я...
