Орграф, або орієнтований графік, - це графічна модель, що складається з вершин і спрямованих ребер, які дозволяють моделювати різні мережеві процеси. Побудова орграфа по ваговій матриці є важливим завданням в аналізі даних і теорії графів.
Вагова матриця-це квадратна матриця, де кожен елемент вказує вагу ребра між двома вершинами диграфа. Існує кілька способів побудови диграфа по ваговій матриці, і в цій статті ми розглянемо покрокове керівництво для виконання цього завдання.
Перший крок-створення вершин графа. Для кожної вершини необхідно присвоїти унікальне ім'я або мітку. Потім, залежно від розміру вагової матриці, створюється відповідна кількість вершин. Наприклад, якщо в матриці 3x3, то потрібно створити 3 вершини.
Після створення вершин слід додати ребра між ними. Для цього необхідно пройти по кожному елементу ваговій матриці і перевірити його значення. Якщо значення елемента відмінно від нуля, значить між відповідними вершинами існує ребро. Напрямок ребра визначається положенням елемента в матриці-рядок відповідає початковій вершині, а стовпець - кінцевої.
Крок 1. Створення матриці суміжності
Для створення матриці суміжності потрібно знати кількість вершин графа. Позначимо це число як N. потім створюємо порожню матрицю розміром N x N.
Заповнюємо матрицю значеннями ваг ребер. Якщо між вершинами з номерами i і j відсутнє ребро, то елемент матриці з індексом (i, j) буде дорівнює нулю. Якщо ж ребро існує з вагою W, то відповідний елемент буде дорівнює W.
Розглянемо приклад. Нехай у нас є граф з 4 вершинами, і його вагова матриця виглядає наступним чином:
1 0 4 02 0 0 30 1 0 00 0 0 0
Для створення матриці суміжності ми створюємо порожню матрицю 4x4 і заповнюємо її значеннями ваг:
0 0 4 02 0 0 30 1 0 00 0 0 0
Таким чином, ми створили матрицю суміжності для даного графа. Вона допоможе нам в подальшому аналізі та побудові орграфа.
Як створити матрицю суміжності на основі вагової матриці графа
Матриця суміжності являє собою таблицю, в якій рядки і стовпці відповідають вершинам графа, А значення в осередках матриці вказують наявність ребра або його відсутність між відповідними вершинами. Для побудови матриці суміжності на основі вагової матриці графа, дотримуйтесь наступних кроків:
- Створіть порожню квадратну матрицю розміром n x n, де n - кількість вершин у графі.
- Проініціалізуйте всі значення матриці значенням 0, щоб вказати відсутність ребер між вершинами.
- Для кожного ребра (i, j) у ваговій матриці графа, де i і j - номери вершин, зміни значення матриці суміжності на відповідну вагу ребра.
Вагова матриця графа:
| 0 | 2 | 0 || 1 | 0 | 4 || 0 | 0 | 0 |
| 0 | 2 | 0 || 1 | 0 | 4 || 0 | 0 | 0 |
В даному прикладі, ребро (0, 1) має вагу 2, ребро (1, 0) має вагу 1, ребро (1,2) має вагу 4. Інші значення матриці суміжності дорівнюють 0, так як відповідних ребер немає.
Крок 2. Визначення напрямку ребер
Для визначення напрямку ребер потрібно звернутися до ваговій матриці і проаналізувати значення в кожному осередку.
1. Пройдіться по рядках матриці, починаючи з першої і до останньої.
2. Кожне значення комірки матриці має бути перевірено на рівність нулю або нижче. Якщо значення більше нуля, то ребро йде від вершини в стовпці матриці до вершини, що відповідає даному рядку.
3. Якщо значення комірки дорівнює нулю або менше, ребро йде в зворотному напрямку: від вершини, що відповідає даному рядку, до вершини в стовпці матриці. Це може бути корисно, коли потрібно задати вагові ребра.
Після визначення напрямку ребер залишається тільки побудувати орграф, використовуючи отримані значення. Для цього кожній вершині графа необхідно присвоїти відповідні ребра із зазначеним напрямком.
Як визначити напрямок ребер диграфа на основі матриці суміжності
Для визначення напрямку ребер в орграфе на основі матриці суміжності необхідно застосувати наступне правило:
- Проаналізуйте кожну клітинку матриці суміжності.
- Якщо значення комірки дорівнює 1, це означає, що існує спрямоване ребро від вершини, представленої рядком, до вершини, представленої стовпцем.
- Якщо значення комірки дорівнює 0, це означає, що між відповідними вершинами немає ребра.
Наприклад, якщо в матриці суміжності на перетині 1-го рядка і 2-го стовпця знаходиться 1, а на перетині 2-го рядка і 1-го стовпця знаходиться 0, це говорить про те, що в орграфе існує спрямоване ребро з 1-ї вершини в 2-ю вершину, але немає ребра з 2-ї вершини в 1-ю вершину.
Таким чином, аналізуючи значення кожної комірки матриці суміжності, можна визначити напрямок ребер диграфа.
Крок 3. Побудова вершин і ребер орграфа
Після створення вагової матриці ми можемо приступити до побудови диграфа. Орграф являє собою граф, в якому ребра мають напрямок.
Вершини орграфа відповідають елементам вагової матриці. Кожен елемент матриці стає окремою вершиною в диграфі.
Ребра орграфа визначаються за значеннями вагової матриці. Якщо значення елемента матриці більше нуля, то між відповідними вершинами проводиться спрямоване ребро.
Напрямок ребра в орграфе відповідає порядку розташування вершин у ваговій матриці. Наприклад, якщо елемент матриці знаходиться в I-му рядку і j-му стовпці, то ребро буде направлено з i-ї вершини в J-ю вершину.
Таким чином, побудувавши вершини та ребра диграфа, ми можемо візуалізувати взаємозв'язки між елементами вагової матриці та отримати уявлення про структуру даних.