У цій статті ми збираємося обговорити матрицю суміжності та її представлення.

Визначення матриці суміжності

У теорії графів матриця суміжності — це щільний спосіб опису скінченної структури графа. Саме двовимірна матриця використовується для відображення асоціації між вузлами графа.

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

Матриця суміжності також називається as матриця підключення . Іноді його також називають a Матриця вершин .

Представлення матриці суміжності

Якщо неорієнтований граф G складається з n вершин, то матриця суміжності графа має вигляд n x n матриці A = [aij] і визначається як -

a _ij = 1 {якщо існує шлях з V _i до В _j }

a _ij = 0 {Інакше}

Давайте розглянемо деякі важливі моменти щодо матриці суміжності.

• Якщо між вершиною V існує ребро _i і В _j , де i — рядок, а j — стовпець, тоді значення a _ij = 1.
• Якщо між вершиною V немає ребра _i і В _j , то значення a _ij = 0.
• Якщо в простому графі немає самоциклів, то матриця вершин (або матриця суміжності) повинна мати 0 на діагоналі.
• Матриця суміжності є симетричною для неорієнтованого графа. Він визначає, що значення в i ^тис рядок і j ^тис дорівнює значенню в j ^тис ряд i ^тис
• Якщо матриця суміжності помножена сама на себе, і якщо в i є ненульове значення ^тис рядок і j ^тис колони, далі йде траса від с _i до В _{j ­ ­} з довжиною, еквівалентною 2. Ненульове значення в матриці суміжності означає наявність певної кількості окремих шляхів.

Примітка. У матриці суміжності 0 означає, що між двома вузлами немає зв’язку, тоді як 1 означає, що зв’язок існує між двома вузлами.

Як створити матрицю суміжності?

Припустимо, є граф g з п кількість вершин, то матриця вершин (або матриця суміжності) задається як -

А = а _{одинадцять} a ₁₂ . . . . . a _1н a _{двадцять один} a ₂₂ . . . . . a _2н . . . . . . . . . a _n1 a _n2 . . . . . a _пп

Де a _ij дорівнює кількості ребер від вершини i до j. Як згадувалося вище, матриця суміжності є симетричною для неорієнтованого графа, тому для неорієнтованого графа _ij = а _хі .

Якщо графи прості і немає ваг на ребрах або множинних ребрах, тоді елементи матриці суміжності будуть 0 і 1. Якщо немає самоциклів, тоді діагональні записи матриці суміжності будуть 0.

Тепер давайте подивимося на матрицю суміжності для неорієнтованого графа та орієнтованого графа.

Матриця суміжності для неорієнтованого графа

У неорієнтованому графі ребра не пов’язані з напрямками з ними. У неорієнтованому графі, якщо існує ребро між вершиною A і вершиною B, тоді вершини можуть бути перенесені з A в B, а також з B в A.

Розглянемо наведений нижче неорієнтований граф і спробуємо побудувати для нього матрицю суміжності.

Ми бачимо, що на графіку немає самоциклу, тому діагональні елементи суміжної матриці дорівнюватимуть 0. Матриця суміжності наведеного вище графіка буде -

Матриця суміжності для орієнтованого графа

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

Розглянемо наведений нижче орієнтований граф і спробуємо побудувати для нього матрицю суміжності.

На наведеному вище графіку ми бачимо, що немає самоциклу, тому діагональні елементи суміжної матриці дорівнюватимуть 0. Матриця суміжності наведеного вище графа буде -

Властивості матриці суміжності

Нижче наведено деякі властивості матриці суміжності:

• Матриця суміжності — це матриця, яка містить рядки та стовпці, які використовуються для представлення простого позначеного графа з числами 0 і 1 у позиції (V _я , ІН _j ), відповідно до умови, чи є два V _{i ­} і В _j є суміжними.
• Для орієнтованого графа, якщо існує ребро між вершиною i або V _i до вершини j або V _j , то значення A[V _i ][IN _j ] = 1, інакше значення буде 0.
• Для неорієнтованого графа, якщо між вершиною i або V існує ребро _i до вершини j або V _j , то значення A[V _i ][IN _j ] = 1 і A[V _j ][IN _i ] = 1, інакше значення буде 0.

Давайте розглянемо деякі питання матриці суміжності. Нижче наведено питання щодо зважених неорієнтованих і орієнтованих графів.

ПРИМІТКА. Граф називається зваженим графом, якщо кожному ребру присвоєно додатне число, яке називається вагою ребра.

Питання 1 - Якою буде матриця суміжності для наведеного нижче неорієнтованого зваженого графа?

Рішення - У наведеному запитанні немає самоциклу, тому зрозуміло, що діагональні елементи суміжної матриці для наведеного вище графа дорівнюватимуть 0. Наведений вище граф є зваженим неорієнтованим графом. Ваги на ребрах графа будуть представлені як елементи матриці суміжності.

Матриця суміжності наведеного вище графа буде -

Питання 2 - Якою буде матриця суміжності для орієнтованого нижче зваженого графа?

Рішення - У наведеному запитанні немає самоциклу, тому зрозуміло, що діагональні елементи суміжної матриці для наведеного вище графа будуть 0. Наведений вище граф є зваженим орієнтованим графом. Ваги на ребрах графа будуть представлені як елементи матриці суміжності.

Матриця суміжності наведеного вище графа буде -

Сподіваюся, ця стаття стане в нагоді для вас, щоб зрозуміти, що стосується матриці суміжності. Тут ми обговорили матрицю суміжності, а також її створення та властивості. Ми також обговорили формування матриці суміжності на орієнтованих чи неорієнтованих графах, незалежно від того, зважені вони чи ні.