2. Ізоморфні графи
Той самий граф можна зображувати по-різному. По-перше, ребра звичайно, але не обов'язково, зображуються відрізками прямих. По-друге, вершини можна по-різному розташовувати на площині. Тому треба вмовитися, які графи однакові і які різні. Це робиться за допомогою поняття ізоморфізму.
Визначення.
Графи
й
називаються ізоморфними,
якщо існує взаємно однозначна відповідність
між множинами вершин
(і, аналогічно, між множинами ребер
– обидві відповідності позначимо
значком ~), що зберігає відношення
інцидентности: якщо
,
,
,
і
,
,
то вершина
інцидентна ребру
в графі
,
тоді й тільки тоді, коли вершина
інцидентна ребру
в графі
.
Інакше
кажучи, графи
й
ізоморфні,
якщо їх вершини й ребра можна пронумерувати
таким чином, що ребро
тоді й тільки тоді з'єднує вершини
й
у графі
,
коли ребро
з'єднує вершини
й
у графі
.
Зокрема,
графи
й
без кратних ребер ізоморфні, якщо
будь-які дві вершини
в графі
суміжні тоді й тільки тоді, коли суміжні
вершини
в графі
.
Графи, що містять різне число вершин (або ребер), не можуть бути ізоморфними. Питання про те, чи ізоморфні дві даних графи, може виявитися досить складним.
Приклад.
Рис. 4.7 Рис. 4.8
Рис. 4.9 Рис. 4.10
Рис. 4.11 Рис. 4.12
Наприклад,
графи мал. 4.7 і мал. 4.8, ізоморфні
(це видно з нумерації їх вершин). Графи
на мал. 4.9 і мал. 4.10, не ізоморфні,
хоча кожен з них має 5 вершин й 7 ребер.
В одного з них є вершина, інцидентна 4
ребрам, в іншого немає. Графи на мал. 4.11
й 4.12 не ізоморфні, тому що в першого з
них є тільки дві послідовності з п'яти
суміжних ребер, що починаються й
кінчаються в одній вершині:
і
,
а в другого таких послідовностей більше
двох:
;
;
і т.д.
Ізоморфні графи в теорії графів звичайно не розрізняються.
3.Матриці суміжності та інциденцій
Нехай
– граф з
вершинами
й
ребрами
.
Його матрицею
суміжності
називається квадратна матриця
,
де
– число ребер, що з'єднують вершини
й
.
Зокрема,
,
якщо вершини
й
не суміжні. Така матриця, мабуть,
симетрична.
Для
графа
без кратних ребер
,
якщо вершини
й
суміжні, і
,
якщо
й
не суміжні. Для графа без петель всі
діагональні елементи матриці суміжності
рівні 0.
Визначення. Матрицею
інциденцій
графа
називається
-матриця
,
де
,
якщо вершина
інцидентна ребру
,
і
,
якщо
й
не інцидентні.
Для графа без петель у кожному стовпці матриці інциденцій точно два елементи рівні 1. Якщо граф має петлі, то в стовпцях, що відповідають петлям, міститься по одній одиниці, в інших – по дві. Наприклад, матриці суміжності графів мал. 4.1 – 4.3 мають вигляд
, 
, 
,
а їх матриці інциденцій -
, 
,
.
Якщо графи й ізоморфні, то їх вершини (і, відповідно, ребра) можна пронумерувати так, що матриці суміжності цих графів (і їх матриці інциденцій) виявляться однаковими. Обернено, будь-які дві графи, що мають ту саму матрицю суміжності (відповідно, інциденцій) ізоморфні. По матриці суміжності (інциденцій) можна відновити граф з точністю до ізоморфізму.