Абстрактні графи та геометричні реалізіції. Орієнтовані графи. Дерева
Лекція 14
Якщо на кожному ребрі графа обрати певний напрямок, то такий граф буде називатись орієнтованим, а його ребра – дугами.
Орієнтований маршрут – послідовність дуг, що проходить неперервним розчерком вздовж дуг від початкової вершини маршруту до кінцевої.
Орієнтований маршрут без дуг, що повторюються, називається шліхом, замкнений шлях – контуром. Шлях без внутрішніх вершин, що повторюються, зветься простим.
Орієнтовані графи можна визначити аналітично через їх матриці суміжності і інцидентності:
Матриця суміжності A: Х – множина вершин. aij – кількість дуг з вершини хi в вершину xj.
Для неорієнтованих графів матриця суміжності симетрична відносно головної діагоналі, для орграфів – необов’язково.
Матриця інцидентності B: Х – множина вершин, У – множина дуг.
Дерева - зв’язний граф Т без циклів, має властивості:
1) Не має циклів;
2) Зв’язний, число вершин на 1 більше дуг;
3) Не містить циклів, але додавання ребра призводить до появи циклу;
4) Зв’язний, але втрачає цю властивість при видаленні будь-якої вершини;
5) Будь-які дві вершини з’єднує єдиний ланцюг.
Остовним підграфом (коротко – остовом) або каркасом графа називається підграф без циклів, що містить всі вершини графа і максимальне велике чисдо дуг графа.
Зваженим графом називається граф G=(X, Y), кожному ребру якого yi прописана вага – додатне число c(yi). Вагою підграфа з G називається сума ваг ребер підграфа. Задача відшукання остова найменшої ваги у графі часто зустрічається у застосуваннях: проектування комп’ютерних і кабельних мереж, ліній електропостачання, трубопроводів, доріг, тощо. Зважені графи можна визначити за допомогою матриці ваги дуг. В ній знаком нескінченності позначена вага між несуміжними вершинами.
Для розв’зку більшості задач, пов’язаних з оргграфами, виникає потреба спочатку їх впорядкувати.
Згідно матриці ваги дуг побудуємо оргграф (Мал.1).
Для впорядкування графа використаємо алгоритм Фалкерсона:
1. Знаходимо вершини графа, в які не входить ні одної дуги. Вони утворюють першу групу вершин. Нумеруємо вершини групи в довільному порядку.
2. Викреслюємо пронумеровані вершини і дуги, що виходять з них. В отриманому графі знаходимо вершини, в які не входить ні одної дуги. Ці вершини утворюють другу групу дуг. Нумеруємо далі вершини групи в довільному порядку. Другий крок повторюємо до тих пір, доки не впорядкуємо всі вершини.
Для нашого графа вершиною І рівня є вершина х1, позначимо її номером 1 – х11.
Вершина ІІ рівня – х2, її номер 2 – х22. Продовжимо процес.
Відповідно визначених рівнів вершин впорядкований оргграф матиме такий вигляд.
Виявлення маршрутів з заданою кількістю ребер
За допомогою матриці суміжності можливо знайти всі маршрути, що містять задану кількість ребер. Справедлива теорема:
Для визначення кількості маршрутів, що складаються з k ребер (дуг), необхідно звести в - k у степень матрицю суміжності вершин.Тоді елемент pij дасть кількість маршрутів довжини k з вершини xi в xj.
Приклад: маємо неорієнтований граф, приведений на малюнку. Складемо для нього матрицю суміжності та зведемо її до квадраму:
Отримана матриця дає уяву про кількість маршрутів між вершинами, що складаються з 2-х ребер.
Якщо скористатись модифікованою матрицею суміжності, в комірки якої записати назви ребер, то отримаємо ще й маршрути:
Аналогічно маємо справу і з оргграфом.
Розглянемо орграф, приведений на малюнку і визначимо маршрути з 3-ма дугами:
Складемо матрицю суміжності і зведемо його до третьої степені. В результаті маємо кількість маршрутів з 3-х дуг:
Для отримання ланцюгів, тобто маршрутів, до яких дуги входять 1 раз, треба з модифікованої матриці викреслити ті додатні, в яких певний множник зустрічається більше одного разу.
4 Завдання
1. Для матриці ваги дуг побудувати граф та впорядкувати його вершини:
А) В)
2. Для приведених графів скласти матриці суміжності, визначити кількість маршрутів з 2-ребер, перелікувати маршрути:
А) з точки В в точку С В) з точки А в точку С
Дата добавления: 2015-09-27 | Просмотры: 1284 | Нарушение авторских прав
|