Page 78 - 2589

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

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

ізоморфними, доведеться виконати всі n! перестановок рядків і
стовпців, а це – досить трудомістка операція.
Матриця інцидентності графа та список його ребер залежать
від нумерації ребер і вершин. Перехід від однієї пари нумерації

до іншої визначається перестановками (α , α ,…, α ) вершин та
2
n
1
( ,  ,…, ) ребер графа, який розглядається. Матриця
1 2 n
інцидентності утворюється з початкової внаслідок перестановки
рядків ( i-й на  -те місце) і стовпців ( j-й на α -те). Рядки списку
j i
ребер переставляються так само, як і рядки матриці
інцидентності, причому кожний номер j в рядках списку
замінюється номером α .
j

Приклад 4.3: Чи ізоморфні графи, зображені відповідно на
рис.4.5,а та 4.6,б.

а)

б)

Рисунок 4.5 – Дослідження ізоморфності графів

78