АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Абстрактні графи та геометричні реалізіції. Орієнтовані графи. Дерева

Лекція 14

Якщо на кожному ребрі графа обрати певний напрямок, то такий граф буде називатись орієнтованим, а його ребра – дугами.

Орієнтований маршрут – послідовність дуг, що проходить неперервним розчерком вздовж дуг від початкової вершини маршруту до кінцевої.

Орієнтований маршрут без дуг, що повторюються, називається шліхом, замкнений шлях – контуром. Шлях без внутрішніх вершин, що повторюються, зветься простим.

Орієнтовані графи можна визначити аналітично через їх матриці суміжності і інцидентності:

Матриця суміжності A: Х – множина вершин. a_ij – кількість дуг з вершини х_i в вершину x_j.

Для неорієнтованих графів матриця суміжності симетрична відносно головної діагоналі, для орграфів – необов’язково.

Матриця інцидентності B: Х – множина вершин, У – множина дуг.

Дерева - зв’язний граф Т без циклів, має властивості:

1) Не має циклів;

2) Зв’язний, число вершин на 1 більше дуг;

3) Не містить циклів, але додавання ребра призводить до появи циклу;

4) Зв’язний, але втрачає цю властивість при видаленні будь-якої вершини;

5) Будь-які дві вершини з’єднує єдиний ланцюг.

Остовним підграфом (коротко – остовом) або каркасом графа називається підграф без циклів, що містить всі вершини графа і максимальне велике чисдо дуг графа.

Зваженим графом називається граф G=(X, Y), кожному ребру якого y_i прописана вага – додатне число c(y_i). Вагою підграфа з G називається сума ваг ребер підграфа. Задача відшукання остова найменшої ваги у графі часто зустрічається у застосуваннях: проектування комп’ютерних і кабельних мереж, ліній електропостачання, трубопроводів, доріг, тощо. Зважені графи можна визначити за допомогою матриці ваги дуг. В ній знаком нескінченності позначена вага між несуміжними вершинами.

Для розв’зку більшості задач, пов’язаних з оргграфами, виникає потреба спочатку їх впорядкувати.

Згідно матриці ваги дуг побудуємо оргграф (Мал.1).

Для впорядкування графа використаємо алгоритм Фалкерсона:

1. Знаходимо вершини графа, в які не входить ні одної дуги. Вони утворюють першу групу вершин. Нумеруємо вершини групи в довільному порядку.

2. Викреслюємо пронумеровані вершини і дуги, що виходять з них. В отриманому графі знаходимо вершини, в які не входить ні одної дуги. Ці вершини утворюють другу групу дуг. Нумеруємо далі вершини групи в довільному порядку. Другий крок повторюємо до тих пір, доки не впорядкуємо всі вершини.

Для нашого графа вершиною І рівня є вершина х₁, позначимо її номером 1 – х₁¹.

Вершина ІІ рівня – х₂, її номер 2 – х₂². Продовжимо процес.

За допомогою матриці суміжності можливо знайти всі маршрути, що містять задану кількість ребер. Справедлива теорема:

Для визначення кількості маршрутів, що складаються з k ребер (дуг), необхідно звести в - k у степень матрицю суміжності вершин.Тоді елемент p_ij дасть кількість маршрутів довжини k з вершини x_i в x_j.

Приклад: маємо неорієнтований граф, приведений на малюнку. Складемо для нього матрицю суміжності та зведемо її до квадраму:

Отримана матриця дає уяву про кількість маршрутів між вершинами, що складаються з 2-х ребер.

Якщо скористатись модифікованою матрицею суміжності, в комірки якої записати назви ребер, то отримаємо ще й маршрути:

Аналогічно маємо справу і з оргграфом.

Розглянемо орграф, приведений на малюнку і визначимо маршрути з 3-ма дугами:

Складемо матрицю суміжності і зведемо його до третьої степені. В результаті маємо кількість маршрутів з 3-х дуг:

Для отримання ланцюгів, тобто маршрутів, до яких дуги входять 1 раз, треба з модифікованої матриці викреслити ті додатні, в яких певний множник зустрічається більше одного разу.

4 Завдання

1. Для матриці ваги дуг побудувати граф та впорядкувати його вершини:

А) В)

2. Для приведених графів скласти матриці суміжності, визначити кількість маршрутів з 2-ребер, перелікувати маршрути:

А) з точки В в точку С В) з точки А в точку С

Дата добавления: 2015-09-27 | Просмотры: 1278 | Нарушение авторских прав