1 Теорія графів. Методи задання графів Лекція 8 Теорія графів

фізик і астроном, за походженням швейцарець. В 1726 році був запрошений

до Петербурзької АН і переїхав в 1727 до Росії. В 1731-1741 р.р. і з 1766 - академік Петербурзької АН. Л. Ейлер вчений надзвичайної широти інтересів, він автор понад 800 робіт з математичного аналізу, диференціальної геометрії, теорії чисел, що зробили значний вплив на розвиток науки.

у Пруссії (нині Калінінград у Росії) було на берегах річки

Преголя, рукави якої ділили місто на чотири частини, в тому числі й два острови, що поєднувалися сімома мостами. Здавна серед мешканців Кенігсберга була поширена така задача: як пройти по всіх мостах, не проходячи по жодному з них двічі? Сім мостів Кеніґсберґа — видатна історична задача з математики.

Леонардом Ейлером в 1735 р. призвело до створення теорії графів

і передувало ідеї топології.

На цей день теорія графів – важливий розділ дискретної математики і основоположний математичний апарат комп’ютерних технологій.

Задача про сім мостів Кеніґсберґа (2) 

Бержа), неорієнтовані та мішані графи. Надалі розглядатимемо графи Бержа або

просто графи. Існують три еквівалентних методи задання графів: аналітичний, геометричний і матричний.

Методи задання графів

підмножину F = {(xi, xj)}XX, що задає бінарне відношення на

X. Множина X і бінарне відношення F на цій множині визначають деякий граф G = (X, F). Якщо множина X скінченна, то граф називають скінченним.
При заданні відношення F на X необхідно кожному елементу xiX зіставити певну підмножину X. Для акцентування того, що елементу xi зіставляється саме підмножина, відповідна відношенню F, позначатимемо її через Fxi, тобто FxiX.

x2, x3, x4, x5}. Нехай Fx1 = {x1, x3, x5},

Fx2 = ; Fx3 = {x1, x2, x5}, Fx4 = {x1}, Fx5 = {x1, x2, x3, x4, x5}. Тоді множини X і F = {(x1, x1), (x1, x3), (x1, x5), (x3, x1), (x3, x2), (x3, x5), (x4, x1), (x5, x1), (x5, x2), (x5, x3), (x5, x4), (x5, x5)} задають граф G.

кружками та називають множиною вершин. Кожну вершину xiX з'єднують лініями

з тими вершинами xjX, для яких виконується умова xjFxi. Множина ліній, що відповідає множині впорядкованих пар вершин (xi, xj), де xiX, а xjFxi, називається множиною ребер графа. Якщо xj  xi, то ребро (xi, xj) зображується лінією зі стрілкою – дугою, що спрямована від xi до xj.

зображують лінією без стрілки, яка поєднує вершину xi із собою,

і називається петлею. Нижче показано геометричне задання графа G=(X, F) із прикладу 3.1.

Геометрична інтерпретація прикладу 3.1

– суть 0 та 1, називається матрицею суміжності графа G

= (X, F) тоді й тільки тоді, коли її елемент утворюється за правилом: елемент rij, що стоїть на перерізі xi-го рядка та xj-го стовпчика, дорівнює 1, якщо існує дуга, що йде з вершини xi до вершини xj, а rij = 0 – у протилежному випадку.

,

вигляді предиката

.

Матричний метод задання (2)

Будь-яка квадратна матриця з 0 та 1 є матрицею суміжності деякого графа G = (X, F), і навпаки.

R =



є матрицею суміжності графа G = (X, F) з прикладу 3.1.

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

вершини xi і заходить у вершину xj або xi –

початок, а xj – кінець дуги. Вершина xi та ребро (xj, xl) називаються інцедентними, якщо j = i або l = i. У протилежному випадку вершина xi та ребро (xj, xl) називаються неінцедентними. Дві вершини xi та xj називаються суміжними, якщо існує хоча б одна дуга, інцедентна їм обом. Вершина xi суміжна сама собі, якщо при вершині xi наявна петля. Два ребра (xi, xj) і (xj, xk) називаються суміжними, якщо існує хоча б одна вершина, інцедентна їм обом.

деякий граф і xiX. Відповідно до визначення графа Fxi –

множина xjX, з якими пов'язана вершина xi відношенням F. Напівстепенню виходу s(xi) або si вершини xi називається кількість ребер (xi, xj), що виходять із вершини xi, оскільки відношення F визначається кількістю елементів множини Fxi, то s(xi) =|Fxi|. Якщо F–1 – обернене до F відношення, то F–1xi являє множину тих xjX, що пов'язані відношенням з xi.

xi називається кількість ребер (xj, xi), що заходять у вершину

xi. Очевидно, що p(xi) = |F–1xi|.
У випадку, коли граф G задано матрицею суміжності R, напівстепень виходу (входу) вершини xi визначається відповідно сумою елементів xi-го рядка (xj-го стовпчика). Тому

Для графа із попереднього прикладу напівстепені виходу та входу відповідних вершин дорівнюють s1 = 3, p1 = 4, s2 = 0, p2 = 2, s3 = 3, p3 = 2, s4 = 1, p4 = 1, s5 = 5, p5 = 3.

F2) називаються рівними, якщо X1=X2, і для кожного xiX1 та

xjX2 таких, що xi= xj, виконується F1xi= F2xj.

називаються ізоморфними, якщо існує бієктивне відображення f множини X на

Y, f:XY, і для кожного xX та yY таких, що f(x) = y, є справедливим співвідношення f(Fx) = Py.
Зрозуміло, що відношення ізоморфізму графів є рефлексивним, симетричним і транзитивним, тобто є відношенням еквівалентності. Тому, якщо відомо, що граф G=(X, F) ізоморфний до графа H = (Y, P) (позначається GH), то графи G=(X, F) і H=(Y, P) вважатимемо еквівалентними або рівними з точністю до ізоморфізму.

граф H = (Y, P), у якого Y

= {y1, y2, y3, y4, y5}, Py1 = , Py2 = {y1, y2, y3, y4, y5}, Py3 = {y4}, Py4 = {y2, y4, y5}, Py5 = {y1, y2, y4}. Встановити, чи є цей граф ізоморфним до графа G(X, F) (слайд 7).

X та Y графів G (попередній приклад) і H у

такий спосіб:



то одержимо f(Fx1) = f({x1, x3, x5}) = {y2, y4, y5} = Py4, f(Fx2) = Py1, f(Fx3) = Py5, f(Fx4) = Py3, f(Fx5) = Py2. Тому графи G(X, F) і H = (Y, P) є ізоморфними.

Розглянемо деякі спеціальні види графів.

Приклад 3.2 (2)

транспонованим щодо графа G = (X, F).

Матриця суміжності R* графа

G* утворюється з матриці R транспонуванням елементів.

F), відношення якого задовольняє умові (xiX)(xjX)[(xjFxi)(xiFxj)],
називається симетричним графом.

Граф G

= (X, F), в якого (xiX)(xjX)[(xjFxi)(xiFxj)], називається антисиметричним графом.

F), де X = {xi}, iI = {1, 2, ...,

n} такий, що ((xiX)[Fxi = ]), називається графом n-го порядку із порожнім відношенням і позначається G. Матриця суміжності R графа G містить тільки нульові елементи, тобто (iI)(jI)[rij=0]. Зокрема, граф G = (X, Y), в якого X = {x1}, а Fx1 = , називатимемо одиничним графом із порожнім відношенням і позначатимемо G0.

F), де X = {xi}, iI = {1, 2, ...,

n} такий, що ((xiX)[Fxi = X]), називається графом n-го порядку з насиченим відношенням і позначається GX. Матриця суміжності RX графа GX містить тільки одиничні елементи, тобто (iI)(jI)[rij = 1]. Зокрема, граф G=(X, F), в якого X={x1}, а Fx1={x1}, називатимемо одиничним графом з насиченим відношенням і позначатимемо G1.

Ахіхj = {(хі, хі1), (хі1, хі2), …, (хіs, хj)} називається

шляхом, що поєднує вершини xі, xjX. Для будь-якого ребра, що належить шляху Ахіхj, вважатимемо, що Ахіхj проходить через це ребро. Аналогічно, якщо вершина xk належить деякому ребру Ахіхj, то вважатимемо, що Ахіхj проходить через вершину xk.
Шлях Ахіхj називається циклом, якщо xi = xj. Цикл (xi, xi) називатимемо петлею.

F) називається зв'язним, якщо для будь-яких двох різних вершин xi

та xj графа G існує шлях, що з'єднує ці вершини.

Граф G = (X, F) називається ациклічним, якщо в ньому відсутні цикли.

властивостями:

існує єдина вершина, що називається коренем дерева, напівстепень входу якої

дорівнює 0;
напівстепені входу всіх інших вершин дорівнюють 1;
кожна вершина є досяжною з кореня дерева.


У випадку неорієнтованих графів деревом називається звязний ациклічний граф.

Дерево

– довільний граф. Граф G' = (X', F') називається підграфом

графа G = (X, F), якщо множина X'X або для всіх xiX' має місце співвідношення F'xiFxX'. У такому випадку граф G = (X, F) називається надграфом графа G' = (X', F').
Граф G = (X, F) називається порожнім і позначається  за умови, що X = . Очевидно, що F = .
Зрозуміло, що для довільного графа G = (X, F) має місце G і GG. Підграфи  та G називаються невласними підграфами графа G = (X, Y). Усі останні підграфи графа G = (X, Y) називаються власними підграфами.

в якого всі графи, розглянуті у певному колі задач, є

підграфами графа L. Існує один порожній граф і скільки завгодно різних універсальних графів.