Page 77 - 2589

(при δ =0 немає жодного рядка), в кожному з яких записуються
ij
номери і, j Для неорієнтованого графа ці рядки відповідають
тільки елементам названого вище верхнього правого трикутника
матриці суміжності, тобто елементам δ з j≥ і а для орієнтованого
ij
графа треба розглядати всі елементи δ .
ij
Отже, граф може бути поданий різними способами. Він може
бути зображений на кресленні (рисунку), заданий матрицею
інцидентності, списком ребер або матрицею суміжності. Вигляд

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

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

Нехай існує бієкція φ, яка діє з множини вершин графа G на

множину вершин графа Н так, що для будь-яких вершин ν та ν
1 2
графа G їхні образи φ(ν ) і φ(ν ) є суміжними в Н тоді й тільки
1 2

тоді, коли ν та ν – суміжні в G Така бієкція називається
1 2
ізоморфізмом графа G на граф Н, а графи G і Н є ізоморфними.

Приклад 4.3: Графи, зображені на рис.4.4, – ізоморфні.

Іншими словами, графи є ізоморфними, якщо вони різняться
тільки нумерацією вершин.

а) б) в)
Рисунок 4.4 – Приклади ізоморфних графів

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

77