Page 76 - 2589

Матриця суміжності графа – це квадратна матриця ∆||δ ||,
ij
стовпцям і рядкам якої відповідають вершини графа. Для
неорієнтованого графа δ дорівнює кількості ребер, інцидентних
ij
і- та j -й вершинам, для орієнтованого графа цей елемент матриці
суміжності відповідає кількості ребер з початком в і -й вершині й
кінцем у j -й. Таким чином, матриця суміжності неорієнтованого

графа є симетричною (δ =δ ) а орієнтованого – необов'язково.
ij ji
Якщо вона все ж симетрична, то для кожного ребра

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

неорієнтованому графу, що має ту саму матрицю суміжності.
Матриці суміжності розглянутих вище графів (див. рис. 4.3,а
та рис. 4.3,б.) наведено в табл.4.2. Матриця суміжності повністю

визначає відповідний неорієнтований або орієнтований граф.
Число його вершин дорівнює вимірності матриці n, і- та j-й
вершинам графа інцидентними є δ ребер. Для неорієнтованого
ij
графа δ =δ і всі його ребра визначаються верхнім правим
ij ji
трикутником матриці, розташованим над діагоналлю, включаючи
останню. Кількість їх дорівнює сумі δ у цьому трикутнику,
ij
тобто
n m
  .
ij
 i 1  j 1
Приклад 4.2: Матриці суміжності для графів зображених на
рис.4.3,а і рис.4.3,б відповідно наведені у табл. 4.2,а і табл.4.1,б.

Таблиця 4.2 – Опис графів матрицями суміжності

Ребра орієнтованого графа визначаються всіма елементами
δ матриці суміжності В обох випадках за допомогою матриці
ij
суміжності легко будується, наприклад, список ребер, що
визначає граф. Елементу матриці суміжності, розташованому в і-

му рядку та j -му стовпці, відповідають δ рядків списку ребер
ij

76