Зважені графи

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

Ізоморфізм

На рис. 1.8 зображено два графи з однією і тою ж множиною вершин . При уважному розгляді можна виявити, що це різні графи – в лівому є ребро ,у правом такого немає. В той же час, якщо не звертати уваги на найменування вершин, то ці графи явно однаково влаштовані: кожен з них – цикл з чотирьох вершин. У багатьох випадках при дослідженні будови графів імена або номери вершин не грають ролі, і такі графи, один з яких виходить з іншого перейменуванням вершин, зручніше було б вважати однаковими. Для того, щоб це можна було робити "на законній підставі", вводиться поняття ізоморфізму графів.

Рис. 1.8.

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

Той факт, що графи і ізоморфні, записується так: .

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

(вершина графа )
(вершина графа )

Відмітимо, що в даному прикладі є і інші ізоморфізми першого графа на другий.

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

Ізоморфізм – бінарне відношення на множині графів. Очевидно, що це відношення рефлексивне, симетричне і транзитивне, тобто є відношенням еквівалентності. Класи еквівалентності називаються абстрактними графами. Коли говорять, що розглядаються абстрактні графи, це означає, що ізоморфні графи вважаються однаковими. Абстрактний граф можна уявляти собі як граф, у якого стерті імена (позначки) вершин, тому абстрактні графи іноді називають також непоміченими графами.

Інваріанти

У загальному випадку дізнатися, чи ізоморфні два графи, достатньо складно. Якщо буквально слідувати визначенню, то потрібно перебрати всі бієкції множини вершин одного з них на множину вершин іншого і для кожної з цих бієкцій перевірити, чи є вона ізоморфізмом. Для вершин є ! бієкцій і ця робота стає практично нездійсненною вже для не дуже великих (наприклад ). Проте у багатьох випадках буває досить легко встановити, що два даних графи неізоморфні. Розглянемо, наприклад, графи, зображені на рис. 1.9.

Оскільки при ізоморфізмі пари суміжних вершин переходить в пару суміжних, а пара несуміжних – в пару несуміжних, то ясно, що число ребер у двох ізоморфних графів повинне бути однаковим. Тому відразу можна сказати, що графи і ,у яких різна кількість ребер, неізоморфні. У графів і однакове число ребер, але вони теж неізоморфні. Це можна встановити, порівнюючи ступені вершин. Очевидно, при ізоморфізмі кожна вершина переходить у вершину того ж ступеня. Отже, ізоморфні графи повинні мати однакові набори ступенів, а у графів і ці набори різні. З графами і справа трохи складніша – у них і набори ступенів однакові. Все ж таки і ці графи неізоморфні: можна відмітити, що в графі є цикл довжини 3, а в графі таких циклів немає. Ясно, що при ізоморфізмі кожен цикл довжини 3 переходить в цикл довжини 3.

Рис. 1.9.

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