Ноу Інти, лекція, початкові поняття теорії графів

Графи і матриці

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

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

Інша матриця. асоційована з графом - це матриця інцидентності. Для її побудови Занумеруем вершини графа числами від 1 до, а ребра - числами від 1 до. Матриця інцидентності має рядків і стовпців, а її елемент дорівнює 1, якщо вершина з номером инцидентна ребру з номером, в іншому випадку він дорівнює нулю. На рис. 1.7 показаний граф з занумерованих вершинами і ребрами і його матриці суміжності і інцидентності.

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

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

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

ізоморфізм

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

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

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

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