Основні поняття теорії графів. Орієнтовані графи Основи дискретної математики. В.Ковтунець

Задача Ейлера про Кенігсберзькі мости Обійти всі мости по одному разу і повернутись в початкову точку

Еквівалентне формулювання в термінах теорії графів Обійти граф так, щоб кожне ребро проходилось один раз, і повернутись в початкову точку B1 B2 I1 I2

Означення графа Нехай V = {v 1, v 2, …, v n }– скінченна множина елементів, які ми назовемо вершинами, a A множина впорядкованих пар вершин, A={(v,w), v, w V }, які ми назовемо дугами. Пара G=(V, A) називається графом. При цьому для дуги (v,w) вершина v називається початком, а верщина w – кінцем дуги. Говорять також, що дуга a= (v,w) інцидентна вершинам v та w. При цьому пишуть v=beg(a), w=end(a).

Приклад V={1,2,3,4,5}, A={(1,3),(2,4),(4,2), (4,3), (4,4), (5,4)}

Поняття теорії графів Означення 2. Дугу (v,w), в якої початок і кінець співпадають, тобто v=w, називається петлею. Означення 3. Шляхом з k ланками в графі G=(V,A) називається множина, що включає послідовність дуг цього графа (a1, a2, …, ak) та інцидентних ним вершин така, що початок кожної наступної дуги співпадає з кінцем попередньої в цій послідовності, тобто, beg(a i+1 )=end(a i ), l= 1,2,…, k-1. При цьому початок першої дуги називається початком шляху, а кінець останньої дуги – кінцем шляху. Означення 4. Шлях називається контуром, якщо вершина, яка є його початком, співпадає з вершиною- кінцем шляху.

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

Приклади Шляхи: (2, 4), (2,4,4), (5,4,3), (5,4,4,2) та ін. Контури: (4,4), (4,2,4), (4,2,4,4,2,4), (2,4,4,2) Приклади простих шляхів: (2,4,2), (5.4,3). Приклад простого контура: (2,4,2).

Підграфи Означення 7. Нехай задано граф G=(V,A). Граф G=(V,A), множина вершин якого співпадає із множиною вершин графа G, а множина ребер є підмножиною множини ребер графа G, тобто, A A, називається частковим графом графа G. Означення 8. Нехай задано граф G=(V,A). Граф G=(V,A), множина вершин якого є підмножиною вершин графа G, тобто V V а множина ребер є підмножиною множини ребер графа G, тобто, A A, називається підграфом графа G.

Матриці, повязані з графами Означення 9. Нехай задано граф G з вершинами {1,2,…,n}. Його матрицею суміжності називається квадратна матриця X розміру n x n, кожен елемент x ij якої дорівнює числу дуг з початком у вершині i та кінцем у вершині j.

Приклад матриці суміжності

Приклад матриці інцидентності дуги графа пронумеровано в порядку: 1: (1,3); 2: (4,3); 3: (4,2); 4: (2,4)

Приклад