Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Елементи теорії графів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2003
Тип роботи:
Методичні вказівки
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство Освіти і Науки України
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
Елементи теорії графів
Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія”
Затверджено на засіданні кафедри Електронних Обчислювальних Машин Протокол № 6 від 21 січня 2003 року
Львів – 2003
Елементи теорії графів : Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладачі: І. Мороз, Р. Попович – Львів: Національний університет “Львівська політехніка”, 2003, 19 с.
Укладачі: Р. Попович, к.т.н., доцент
І. Мороз, асистент
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ
Рецензенти: Ємець В. Ф., професор кафедри ЕОМ, д. фіз.-мат. н.
Юрчак І. Ю., доцент кафедри САПР, к. т. н.
Вступ
Зародження теорії графів пов’язують з роботою Ейлера (1736 р.) про Кенігсберзькі мости. Який знайшов критерії існування в графі спеціального маршруту, так званого ейлеревого циклу. Тривалий час цей результат залишався єдиним у теорії графів. Нові результати були отримані лише в XIX ст. в роботах Кіргофа та Келі. Хоча теорія графів виникла більше двох століть тому, її інтенсивний розвиток припадає лише на останні 50-60 років. Цей розвиток завдячує широкому застосуванню графів в теорії автоматів, теорії проектування, економіці, хімії, біології та ін.
Теорія графів, як розділ дискретної математики, з успіхом використовується у задачах керування виробництвом і проектування мереж ЕОМ, при розробці сучасних електронних модулів і при проектуванні фізичних систем, при розв’язуванні задач генетики і вирішенні проблем автоматизованого управління (САПР). Теорія графів є основою математичного забезпечення сучасних систем обробки інформації у прикладній теорії алгоритмів та в інших галузях науки і техніки.
Одним з прикладів ефективного застосування теорії графів в сучасних інформаційних системах є кодування інформації при передачі через канал зв’язку. При цьому ставиться вимога забезпечити виправлення помилок, які виникають внаслідок фізичних завад у каналах зв’язку або пристроях зберігання інформації. Одним з кращих алгоритмів який вирішує дану задачу є алгоритм Вітербі, в основі якого лежить алгоритм пошуку оптимального шляху, що є предметом досліджень в теорії графів.
Далі розглядатимемо деякі елементи теорії графів, які мають загальну форму та можуть бути застосовані при дослідженні об’єктів та систем довільної природи.
1. Основні поняття і операції
1.1. Визначення графу
Предметом перших задач теорії графів були конфігурації, які складаються з точок і ліній, які їх з’єднують. При цьому несуттєво, прямі ці лінії або вони є криволінійними дугами. Важливо лише те, що вони з’єднують дані точки.
Визначення. Розглянемо множину V, яка складається з точок, частина яких з’єднана між собою. Назвемо V множиною вершин, а об’єкт v ( V - вершиною. Граф
G = G(V)
з множиною вершин V - це деяка сукупність пар вигляду
e = (a, b),
де a, b ( V вказують, які пари вершин з’єднані між собою. Відповідно до геометричних уявлень про граф кожна така пара (a, b) називається ребром графу, а „а” і „b” – кінцями ребра. З іншого боку, оскільки
e = (a, b) ( V ( V,
то граф
G(V) ( V ( V.
Визначення. Якщо у визначенні ребра графу не брати до уваги послідовність його кінців, тобто вважати, що
e = (a, b) = (b, a),
то говорять, що e – неорієнтоване ребро. В протилежному випадку e = (a, b) - орієнтоване ребро, в якому „а” – початкова вершина, а „b” – кінцева.
Визначення. Якщо e = (a, b), то говорять, що ребро e інцидентне вершинам „а” і „b”, а вершини „а” і „b” інцидентні ребру e.
1.2. Зображення графів
Визначення. Граф G називається неорієнтованим, якщо кожне його ребро є неорієнтованим. Граф G називається орієнтованим, якщо кожне його ребро є орієнтованим.
Рис. 1.
На рис. 1.а, б, в, е зображені деякі неорієнтовані графи, а на рис. 1.г, д – деякі орієнтовані графи (напрями ребер зображені стрілками). Лінії, які відповідають ребрам графів, можуть перетинатись на рисунку, але точки їх перетину не обов’язково повинні бути вершинами графу (див.рис.1.а).
Якщо два ребра інцидентні одній парі вершин, то такі ребра називаються кратними (див.рис.1.б). Ребро, яке з’єднує вершину саму з собою, називають петлею (див.рис.1.д).
Визначення. Граф називається скінченним, якщо кількість ребер в ньому є скінченною (рис.1.а, б, г); інакше граф називають нескінченним (рис.1.е).
Визначення. Вершина графу, не інцидентна жодному ребру, називається ізольованою. Якщо граф складається тільки з ізольованих вершин, то він називається нульграфом (рис.1.в).
Визначення. Будемо говорити, що два графи G і G’ є ізоморфними, якщо існує така відповідність між множинами їх вершин V і V’, що у графі G вершини з’єднані між собою тоді і тільки тоді, коли з’єднані між собою відповідні їм вершини у графі G’. Якщо ребра орієнтовані, то їх напрямки повинні відповідати один одному.
Наприклад:
Твердження. Ізоморфні графи мають однакові властивості.
Відповідно з даними твердженнями ізоморфні графи надалі будемо ототожнювати.
1.3. Способи задання графів
Графічний опис графів є незручним для їх аналізу на ЕОМ. Тому розглянемо табличні способи задання графів.
Надалі будемо розглядати тільки скінченні графи, у яких множини вершин V = {v1, …, vn} і ребер E = {e1, …, em} є скінченними.
Визначення. Матриця суміжності вершин графу G(V) (позначається M(G) = {Mij}) - це квадратна матриця розміру n(n, в якій Mij - кількість ребер, які з’єднують Vi з Vj в графі G. Якщо граф G неорієнтований, то
Mij = Mji,
тобто матриця М є симетричною.
На рис.2 зображений деякий неорієнтований граф; відповідна матриця суміжності вершин приведена в табл.1.
Рис.2
Таблиця 1
1
2
3
4
5
6
7
1
0
1
1
0
0
0
1
2
1
0
1
0
0
0
0
3
1
1
0
1
0
0
0
4
0
0
1
0
1
0
0
5
0
0
0
1
0
1
1
6
0
0
0
0
1
0
1
7
1
0
0
0
1
1
0
Граф також може бути описаний за допомогою матриці інцидентності (позначається N(G) = {Nij}), яка має n рядків (вершини) і m стовпців (ребра). Для неорієнтованого графу Nij = 1, якщо вершина vi інцидентна ребру ej; в протилежному випадку - Nij = 0.
Для орієнтованого графу Nij = 1, якщо vi - початкова вершина ребра ej; Nij = 1, якщо vi - кінцева вершина ребра ej; Nij = 0, якщо вершина vi не інцидентна ребру ej.
У табл. 2 наведена матриця інцидентності для неорієнтованого графу, зображеного на рис. 2.
Таблиця 2
І
ІІ
ІІІ
IV
V
VI
VII
VIII
IX
1
1
1
1
0
0
0
0
0
0
2
0
1
0
1
0
0
0
0
0
3
0
0
1
1
1
0
0
0
0
4
0
0
0
0
1
1
0
0
0
5
0
0
0
0
0
1
1
0
1
6
0
0
0
0
0
0
1
1
0
7
1
0
0
0
0
0
0
1
1
Рис. 3
Таблиця 3
І
ІІ
ІІІ
IV
V
VI
1
-1
-1
0
0
0
0
2
1
0
-1
0
0
0
3
0
1
0
-1
-1
-1
4
0
0
1
0
0
0
5
0
0
0
1
0
0
6
0
0
0
0
1
0
7
0
0
0
0
0
1
Неорієнтований граф без петель G може бути також описаний квадратною матрицею суміжності ребер (позначається I(G) = {Iij}) розміром m(m, причому Iij = 1, якщо i ( j і у ребер ei і ej є спільна вершина. В протилежному випаду - Iij = 0.
Для графу, зображеного на рис. 2, відповідна матриця суміжності ребер приведена в табл. 4.
Таблиця 4
І
ІІ
ІІІ
IV
V
VI
VII
VIII
IX
І
0
1
1
0
0
0
0
1
1
ІІ
1
0
1
1
0
0
0
0
0
ІІІ
1
1
0
1
1
0
0
0
0
IV
0
1
1
0
1
0
0
0
0
V
0
0
1
1
0
1
0
0
0
VI
0
0
0
0
1
0
1
0
1
VII
0
0
0
0
0
1
0
1
1
VIII
1
0
0
0
0
0
1
0
1
IX
1
0
0
0
0
1
1
1
0
1.4. Локальні степені вершини графу
Нехай G(V) - неорієнтований граф.
Визначення. Локальним степенем ((a) (або просто степенем) деякої вершини a ( V називається кількість ребер графу, інцидентних цій вершині.
Якщо граф заданий матрицею суміжності вершин, то
(1)
Для матриці інцидентності аналогічна формула має вигляд
(2)
Число ребер у графі G позначимо через vE = vE(G). При підрахунку суми кожне ребро e(vi, vj), графу G підраховується двічі: один раз – як таке, що з’єднує вершину vi з vj, а другий раз – як таке, що з’єднує vj з vi. Тому
(3)
(формула (3) залишається правильною і для графу з петлями, якщо їх розглядати як подвійні ребра).
Оскільки в лівій частині формули (3) стоїть парне число, то це означає, що у скінченному графі без петель кількість вершин з непарним степенем – парна.
Визначення. Граф називається однорідним степеня k, якщо ((vi = k), для всіх vi ( V.
В однорідному графі кількість ребер згідно з формулою (3) vE = nk/2.
Визначення. Повний граф U = U(V) - це неорієнтований граф, у якому дві довільні вершини з’єднані рівно одним ребром.
Зрозуміло, що повний граф U(V) з n вершинами – це однорідний граф степеня (n 1). Тому vE = n(n – 1) / 2.
Визначення. Повний граф з петлями U0 = U0(V) - це повний граф, у якому до кожної вершини додана петля.
Кількість ребер у повному графі з петлями vE(U0) = vE(U) + n = n(n + 1) / 2.
Нехай тепер G(V) - орієнтований граф. Тоді через ((vi) і (*(vi) позначають кількість ребер, які виходять з вершини vi і входять в вершину vi відповідно.
Аналогічно попередньому кількість ребер в орієнтованому графі
.
1.5. Частини, суграфи і підграфи графу.
Операції з частинами графу
Визначення. Граф Н називається частиною графу G (позначається H ( G), якщо:
V(H) ( V(G); E(H) ( E(G).
Визначення. Граф Н називається суграфом графу G, якщо він є частиною графу G і
V(H) = V(G).
На Рис. 4 зображені граф G і його три частини. Граф H3 є суграфом.
Рис.4.
Визначення. Суграф H називається покриваючим для графу G, якщо будь-яка вершина H інцидентна хоча б одному ребру з G. Зауважимо, що якщо в графі G є ізольовані вершини, то для нього не існує покриваючого графу H.
Визначення. Підграфом G(U) графу G(V) називається така його частина, яка містить всі ребра графу G(V), що з’єднують дві будь-які вершини з множини U.
На рис. 4 H1 не є підграфом G (не містить ребро e(2, 4)), а H2 – підграф графу G.
Визначення. Зірковим графом, який визначається деякою вершиною a ( V, називається граф, що містить всі ребра даного графу G(V), інцидентні вершині „a”.
За аналогією з операціями поміж множинами можна виконувати і операції між графами.
Визначення. Якщо H – частина графу, то (доповнення графу H) – це граф, в який входять всі ребра графу G, які не належать H:
.
Визначення. Нехай H1 і H2 - дві частини графу G. Тоді H = H1 ( H2 (об’єднання або сума) це також частина графу G, яка складається зі всіх ребер, що належать або H1 або H2.
Визначення. Нехай H1 і H2 - дві частини графу G. Тоді H = H1 ( H2 (перетин) це частина графу G, яка складається зі всіх ребер, що належать H1 та H2 одночасно.
Визначення. Якщо дві частини H1 і H2 графу G не мають спільних вершин, то їх сума H = H1 ( H2 називається прямою. Якщо H1 і H2 не перетинаються по ребрах, то їх сума називається прямою по ребрах.
Наприклад: - пряма сума за ребрами.
2. Маршрути, ланцюги і цикли
2.1. Деякі визначення
Нехай G - орієнтований граф.
Визначення. Маршрутом в G називається скінченна або нескінченна послідовність ребер S = {…, e0, e1, …, en, …} в якій кожні два сусідні ребра ei - 1 і ei мають спільну вершину, тобто
e0 = (v0, v1), e1 = (v1, v2), e2 = (v2, v3), ..., en = (vn, vn + 1).
Визначення. Якщо в S немає ребер, які стоять перед e0, то v0 називається початковою вершиною S; якщо немає ребер після en - 1, то vn - кінцевою вершиною. Якщо вершина vi належить і ei - 1 і ei, то вона називається внутрішньою.
Визначення. Якщо маршрут S має початкову і кінцеву вершини, то він називається скінченним; якщо S має початок і не має кінцевої вершини (або навпаки), то він називається односторонньо-нескінченним; якщо немає ні початкової вершини ні кінцевої – то двосторонньо-нескінченними. Якщо S має початкову вершину v0 і кінцеву vn, то позначається
S = S(v0, vn)
(тобто S - це маршрут довжини n, який з’єднує вершини v0 і vn ).
Визначення. Якщо v0 = vn, то маршрут називається циклічним.
Визначення. Якщо vi і vj - дві вершини маршруту S, то
S(vi, vj) = (ei, …, ei + 1, …, ej - 1)
називається підмаршрутом.
На рис.5 маршрут S = (e1, e2, e3, e4, e5) є скінченним, має довжину 5, початкову вершину v1 і кінцеву v5. Маршрут S = (e2, e3, e4) є підмаршрутом даного маршруту.
Рис.5
Визначення. Ланцюг – це маршрут, кожне ребро якого зустрічається рівно один раз. Циклічний ланцюг називається циклом.
Визначення. Нециклічний ланцюг називається простим, якщо в ньому жодна вершина не повторюється. Цикл з початком (і кінцем) в v0 називається простим, якщо в ньому жодна вершина, крім v0 не повторюється.
Зрозуміло, що частина ланцюга або циклу теж є ланцюгом або циклом.
Для орієнтованих графів вводяться в розгляд як неорієнтовані маршрути (ланцюги) (тобто не приймається до уваги орієнтація ребер), так і орієнтовані маршрути (ланцюги).
2.2. Зв’язність
Нехай G - неорієнтований граф.
Визначення. Дві вершини „a” і „b” графу G називаються зв’язними, якщо існує маршрут S(a, b).
Якщо в S(a, b) деяка вершина vi повторюється більше одного разу, то відкидаючи циклічну ділянку S(vi, vi), отримаємо новий маршрут S’(a, b), в якому вершина vi зустрічається тільки один раз. Повторюючи цю процедуру для всіх таких вершин vi, приходимо до висновку: якщо дві вершини в графі можуть бути зв’язані маршрутом, то існує і простий ланцюг, який зв’язує ті ж вершини.
Визначення. Граф G називається зв’язним, якщо зв’язна будь-яка його пара вершин.
Всі підграфи G(Vi) зв’язного графу G(V) є теж зв’язними і називаються зв’язними компонентами графу.
Зауважимо, що зв’язність – відношення еквівалентності між вершинами графу:
а) довільна вершина v графу зв’язана сама з собою;
б) якщо „a” і „b” – зв’язні (тобто існує маршрут S(a, b)), то в силу неорієнтованості графу „b” і „а” теж зв’язані (маршрутом S(b, a));
в) якщо зв’язані „а” і „b” (маршрутом S1(a, b)) і „b” і „с” (маршрутом S2(b, c)), то існує маршрут з „а” в „с” (S1(a, b) + S2(b, c)), тобто вершини „a” і „c” теж зв’язані.
В силу відомого твердження з алгебри, граф G розбивається на класи еквівалентності – підграфи, в яких всі вершини є зв’язними між собою і які не мають спільних вершин:
, (пряма сума)
таким чином, істинне
Твердження. Довільний неорієнтований граф розбивається на пряму суму своїх зв’язкових компонент.
Це дозволяє більшість задач зводити до випадку зв’язних графів.
2.3. Відстань, діаметр, радіус і центр графу
Нехай G - зв’язний, неорієнтований граф. Оскільки дві довільні вершини „a” і „b” – зв’язані, то в загальному випадку існує декілька простих ланцюгів Si(a, b), які з’єднують „a” і „b”. В цій множині ланцюгів має існувати ланцюг, який має найменшу довжину. Ця найменша довжина і називається відстанню між „a” і „b”: d(a, b). Будемо вважати за визначенням, що d(a, a) = 0.
Введена відстань задовольняє всі аксіоми метрики:
1) d(a, b) ( 0;
2) d(a, b) = 0 тоді і тільки тоді, коли a = b;
3) d(a, b) = d(b, a);
4) d(a, b) + d(b, c) ( d(a, c).
Для скінченного графу можна ввести поняття діаметру.
Визначення. Діаметр графу G(V):
.
Виберемо деяку вершину c ( V і позначимо через
,
віддаль від с до найбільш віддаленої вершини графу.
Назвемо c0 центром графу G, якщо
.
Зауважимо, що центр графу не єдиний.
Рис.6
Наприклад, для графу, зображеного на рис. 6, радіус r0 = 1; центр графу c0 = v2 або c0 = v4.
2.4 Алгоритм Дейкстри
Розглянемо наступну задачу: заданий скінченний орієнтований граф G, кожному ребру якого приписана його числова характеристика („довжина”). Необхідно знайти найкоротший шлях від заданої вершини (позначимо її через s) до всіх решта вершин графу.
Для розв’язання цієї задачі найбільшого розповсюдження набув алгоритм Декстри, згідно з яким всі вершини графу G(V) необхідно впорядкувати по зростанню їх відстані від вершини s:
d(s, u0) ( d(s, u1) ( … ( d(s, un) і V = { u0, u1, …, un}.
Ця послідовність будується інтеративно. Перша вершина в ній відома:
u0 = s; d(s, u0) = 0.
Нехай відомі перші (l + 1) вершини цієї послідовності:
{u0 = s, u1, …, ul},
які ми будемо надалі називати фіксованими. Це означає, що вершина u1 ближча від s, ніж всі решта (тобто нефіксовані) вершини.
Для кожної нефіксованої вершини у графу модифікуємо її відстань від s: якщо існує e(ui, v) і d(s, ui) + d(ui, v) ( d(s, v) , то d(s, v) = d(s, ui) + d(ui, v) і передостанньою вершиною в найкоротшому (на даний час) шляху, який з’єднує s з v, буде вершина ui. Після цього серед всіх нефіксованих вершин знаходимо ту, відстань до якої від s є найменшою. Ця вершина і буде наступною в послідовності (тобто ui + 1).
Алгоритм Дейкстри.
Масиви, що використовуються:
VID: VID(i) – найкоротша на даний момент відстань від s до i -ї вершини графу;
FIX: FIX(i) = 1, якщо i-та вершина графу є фіксованою;
PRED: PRED(i) містить передостанню вершину в найкоротшому з усіх відомих на даний момент шляхів від s до і-ї вершини графу.
1) Початкові установки.
Для початкової вершини: VID(s) = 0, FIX(s) = 0, PRED(s) = s.
Для всіх інших вершин графу: VID(v) = (, FIX(v) = 0, PRED(v) = v.
Біжуча вершина: u = s, i = 1.
2) ЦИКЛ по тих вершинах графу G, для яких FIX(v) = 0
ЯКЩО існує e = (u, v) і VID(u) + d(u, v) ( VID(v)
ТО VID(v) = VID(u) + d(u, v), PRED(v) = u.
3) Серед вершин графу G, для яких FIX(v) = 0, знаходимо ту вершину v0, для якої
.
4) FIX(v0) = 1, u = v0.
5) i = i + 1.
ЯКЩО i ( n,
ТО йти на 2).
6) Кінець.
В результаті масив VID містить найкоротші відстані від s до всіх вершин графу; по масиву PRED можна отримати найкоротший шлях від s до довільної вершини графу.
Приклад.
Рис.7
Робота алгоритму проілюстрована в табл. 5, в якій кожний рядок відповідає одному циклу роботи алгоритму. Фіксовані вершини підкреслені, а біля вершини „u” на кожному кроці стоїть зірочка.
Таблиця 5
i
VID
PRED
A
B
C
D
E
F
A
B
C
D
E
F
1
0*
∞
∞
∞
∞
∞
A
B
C
D
E
F
2
0
7
∞
8
∞
6*
A
A
C
A
E
A
3
0
7*
∞
8
∞
6
A
A
C
A
E
A
4
0
7
∞
8*
∞
6
A
A
C
A
E
A
5
0
7
∞
8
16*
6
A
A
C
A
D
A
6
0
7
∞
8
16
6
A
A
C
A
D
A
Найкоротший шлях від A, наприклад, до E будується, використовуючи масив PRED, таким чином: E ( D ( A.
2.5. Задача про ланцюги
Теорія графів почалася з розв’язування задачі про кенігсберзькі мости (Ейлер, XVIII ст.). Розташування мостів в м. Кенігсберг наведено на рис.8.
Рис. 8.
В місті є 7 мостів {a, b, c, d, e, f, g}, які його розбивають на чотири частини {A, B, C, D}. Необхідно обійти всі мости міста, проходячи по кожному рівно один раз, і повернутись у початкову точку.
Граф для цієї задачі наведений на рис.9.
Рис.9.
Загальна постановка задачі є наступною (Ейлер): в яких випадках у скінченному неорієнтованому графі можна знайти такий цикл, у якому кожне ребро графу зустрічалось би рівно один раз. Якщо такий цикл існує, то він називається ейлеревим циклом, а сам граф називається ейлеревим.
Твердження. Скінченний граф G(V) є ейлеревим тоді і тільки тоді, коли:
1) G(V) - зв’язний граф;
2) локальні степені всіх його вершин парні.
Алгоритм побудови ейлеревого циклу:
1) вибираємо довільну вершину a ( V;
2) будуємо довільний ланцюг P з початком у вершині „a”. Оскільки локальні степені всіх вершин графу є парні, то ланцюг може завершитись тільки в „a” (тобто він є циклом);
3) якщо P(a, a) містить не всі ребра графу G(V), то будуємо граф G1 = G P(a, a), в якому всі вершини мають теж парний локальний степінь. Оскільки граф G(V) є зв’язним, то серед вершин P(a, a) має знайтись вершина „b”, яка зв’язана ребром хоча б з однією вершиною графу G(V) (інакше граф G був би незв’язним);
4) будуємо з ребер графу G1 ланцюг P’, що починається у вершині „b” і може закінчуватись тільки у „b”; з ланцюгів P і P’ будуємо новий цикл:
P1(a, a) = P(a, b) ( P’(b, b) ( P(b, a);
5) якщо P1(a, a) не містить всіх ребер графу G(V), то, за аналогією з кроком 3) будуємо граф G2 = G – P1(a, a) і т.д.
З огляду на скінченність графу, цей процес зупинитися, коли всі ребра графу G(V) будуть вичерпані.
Узагальнюючи задачу Ейлера можна шукати найменшу кількість ланцюгів (не циклів!) P1, які не перетинаються по ребрах і покривають увесь зв’язний граф G(V).
Твердження. Нехай G(V) - скінченний зв’язний граф з „k” вершинами непарного локального степеня. Тоді мінімальна кількість ланцюгів, які не перетинаються по ребрах і покривають граф G, дорівнює k / 2.
Алгоритм побудови ланцюгів Pi.
1) з’єднуємо довільно чином пари вершин з непарним локальним степенем (для цього необхідно k / 2 ребер). При цьому утворюється граф G1, всі вершини якого мають парний степінь;
2) граф G1 є ейлеревим і в ньому існує ейлерів цикл S;
3) після відкидання з циклу S доданих на кроці 1) k / 2 ребер, отримуємо k / 2 ланцюгів, які покривають весь граф G.
Приклад
Рис. 10.
Локальні степені вершин графу:
Вершина
a
b
c
d
e
f
g
h
Степінь
2
4
5
3
2
3
4
3
Таким чином, k = 4. З’єднаємо ребрами вершини (c, d) та (f, h) (на рис.10 ці ребра позначені штриховими лініями).
Поетапно побудуємо для утвореного графу цикл Ейлера:
а) P1 = (І, ІІІ, ІІ);
б) P2 = (І, ІХ, VI, III, II);
в) P3 = (І, IX, XIII, XII, XI, VI, IV, III, II);
г) P4 = (I, IX, XIV, X, VIII, XIII, XIII, XI, VI, IV, III, II);
д) P5 = (I, IX, XIV, X, VIII, XIII, XII, XI, VI, VII, XV, V, IV, III, II).
Віднімаючи додані раніше ребра XIV і XV, отримаємо три ланцюги:
1) (І, Х);
2) (Х, VIII, XIII, XII, XI, VI, VII);
3) (V, IV, III, II).
Зауважимо, що перший і третій ланцюги мають спільний кінець – вершину „а”. „Склеюючи” ці ланцюги, отримаємо остаточно:
1) (V, IV, III, II, I, IX);
2) (X, VIII, XIII, XII, XI, VI, VII).
Для орієнтованих графів має місце
Твердження. Нехай G(V) - орієнтований зв’язний граф. Граф G містить ейлерів цикл тоді і тільки тоді, коли у кожну вершину v входять стільки ж ребер, скільки і виходить:
((v) = (*(v).
Якщо в неороієнтованому графі кожне неорієнтоване ребро замінити двома орієнтованими і протилежно направленими, то мають місце умови попереднього твердження і тому правильне таке
Твердження. У скінченному зв’язному неорієнтованому графі завжди можна побудувати орієнтований цикл, який проходить через кожне ребро по одному разу в кожному з двох напрямків.
2.6. Гамільтонові цикли
Визначення. Гамільтонів цикл – це цикл, який проходить по кожній вершині графу один раз.
До знаходження гамільтонового циклу приводить, наприклад, задача комівояжера: деякий район містить пеану кількість міст, які повинен обійти комівояжер. Відомі відстані між всіма містами. Необхідно знайти найкоротший шлях, який проходить через всі міста і повертається в початковий пункт.
Незважаючи на подібність у формулюванні для ейлеревих і гамільтонових циклів, відповідні теорії мають мало спільного. Критерій існування ейлеревих циклів був встановлений достатньо просто; для гамільтонових циклів ніякого загального правила невідомо. Більше того, для конкретних графів іноді тяжко встановити, чи існує взагалі такий цикл. Тому обмежимось одним критерієм.
Твердження. (Дірак). Якщо в графі G(V) з „n” вершин для довільної вершини v ( V : ((v) ( n / 2, то в графі існує гамільтонів цикл.
3. Деякі класи графів
3.1. Дерева
Визначення. Зв’язний неорієнтований граф називається деревом, якщо він не має циклів.
Визначення. Ліс – це граф, зв’язні компоненти якого є деревами. Зрозуміло, що довільна частина лісу або дерева є теж лісом або деревом.
Твердження. В дереві дві довільні вершини зв’язані єдиним ланцюгом (інакше був би цикл).
Тому довільний ланцюг у дереві є простим.
Визначення. У довільному графі G вершина v називається кінцевою, якщо ((v) = 1, тобто існує одне ребро, інцидентне вершині v, і це ребро називається кінцевим.
Твердження. У дереві є хоча б дві кінцеві вершини.
Розглянемо дерево G і виберемо довільну вершину v0. Кожному ребру e = (a, b) зіставимо той кінець, який більш віддалений від v0 (оскільки в дереві всі ланцюги є простими, то від довільної вершини до v0 веде лише один ланцюг). Тому vV – vE = 1 (vV - кількість вершин, vE - кількість ребер).
Визначення. В довільному неорієнтованому графі G циклічний ранг:
((G) = vE vV + 1.
Твердження. Для довільного зв’язного графу G циклічний ранг
((G) ( 0
і дорівнює кількості ребер, які необхідно вилучити з G для того, щоб отримати дерево (остов графу).
Для дерев ((G) = 0.
Для незв’язних графів циклічний ранг визначається таким чином:
((G) = vE vV + (G,
де (G - кількість зв’язних компонент у графі G.
Дерева використовують для розв’язання такої задачі: необхідно з’єднати „n” міст залізничною колією таким чином, щоб не будувати зайвих ліній. При цьому вважається відомим вартість будівництва колії між двома довільними містами. Таким чином, необхідно побудувати зв’язний граф G, який містить всі задані вершини і для якого повна вартість була б найменшою. Очевидно, що граф G - дерево.
Алгоритм розв’язання.
Вибираємо ребро ei з найменшою вартістю. Отримаємо граф A1 = {e1}. На кожному наступному кроці до Ai 1 додаємо ребро, яке має найменшу вартість серед тих, що залишились, і таке, що граф Ai = Ai 1 ( {ei} не має циклів. Останній граф An 1 = G і є шуканим.
3.2. Дводольні графи
Визначення. Дводольним графом називається граф G = G(V1, V2), в якому вся множина вершин розбивається на дві множини V1, і V2, що не перетинаються (тобто V1 ( V2 = (), і кожне ребро e(v1, v2) з’єднує v1 ( V1 і v2 ( V2.
Твердження. Кожна частина дводольного графу є дводольна.
Твердження. Граф G є дводольним тоді і тільник тоді, коли всі прості цикли в ньому мають парну довжину.
Твердження. Довільний зв’язний граф містить дводольну частину, яка є теж зв’язною і покриває всі вершини графу G.
Визначення. Нехай G(V1, V2) - дводольний граф. Пароз’єднання – це підмножина ребер графу G:{(xi, yj), …}, де xi ( V1 а yj ( V2, причому жодні два ребра не мають спільних вершин.
Визначення. Максимальне пароз’єднання (П) – це пароз’єднання дводольного графу G, яке має найбільшу кількість ребер.
Розглянемо таку задачу: знайти максимальне пароз’єднання, яке містить всі вершини множини V1.
Твердження (теорема Холла). Максимальне пароз’єднання П дводольного графу покриває всі вершини множин V1 тоді і тільки тоді, якщо для довільної множини U1 ( V1 кількість елементів у множині U2 ( V2, яка містить всі вершини, з’єднані ребром хоча б однією вершиною з U1, не менша від кількості вершин множини U1.
Алгоритм побудови максимального пароз’єднання П.
Будемо вважати, що умови теореми Холла виконані. Задамося довільним пароз’єднанням П0. Якщо воно не охоплює всіх вершин множини V1, то існує x0 : x0 ( V1 і x0 ( П0.
Побудуємо
W0 = {x0};
W1 = {y | (x0, y) ( G};
W2 = {x | (x, y) ( П0, y ( W1, x ( W0};
W3 = {y | (x, y) ( G, x ( W2, y ( W1};
W4 = {x | (x, y) ( П0, y ( W3, x ( W0 ( W2};
W5 = {y | (x, y) ( G, x ( W4, y ( W1 ( W3};
. . .
Зауважимо, що, згідно з побудовою, в множинах W1 і W2, W3 і W4, W5 і W6 і т.д. попарно однакова кількість елементів. Крім того, послідовність вершин Wi не може закінчитись на множині з парним індексом W2k, оскільки для множини
U1 = W0 ( W2( … ( W2k ( V1
кількість вершин у відповідній множині
U2 = W1 ( W3( … ( W2k - 1 ( V2
(U2 містить всі вершини графу, які з’єднані ребром хоча б з однією з вершин множини U1) на одиницю більше, що суперечить умові теореми Холла. Тому існує вершина y*:
y* ( W2k - 1 і y* ( П0.
Тоді існує шлях S, який починається з x0, проходить через вершини множин W1 і закінчується в y* і містить непарну (2k 1) кількість ребер:
S = {e1, e2, …, e2k - 1},
причому всі парні ребра e2k ( П0.
Нове пароз’єднання П1 будуємо наступним чином:
П1 = П0 \ {e2 ( e4 (…( e2k - 2} ( {e1 ( e2 (…( e2k - 1}.
Пароз’єднання П1 містить на одне ребро і на одну вершину з множини V1 більше ніж П0. Якщо П1 охоплює всі вершини множини V1, то беремо деяку вершину x0 : x0 ( V1 і x0 ( П1 і т.д.
Приклад
П0 = {(x1, y1), (x3, y2)}.
1) W0 = (x2); W1 = (y2); W2 = (x3); W3 = (y1); W4 = (x1); W5 = (y4).
e1 = (x2, y2); e2 = (x3, y2); e3 = (x3, y1); e4 = (x1, y1); e5 = (x1, y4).
П1 = {(x2, y2), (x3, y1), (x1, y4)}.
2) W0 = (x4); W1 = (y3, y4).
e1 = (x4, y3).
П = П2 = {(x1, y4), (x2, y2), (x3, y1), (x4, y3)}.
Список літератури
1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.
2. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. – 455 с.
3. Зыков А.А. Основы теории графов. – М.: Наука, 1987. – 384 с.
4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. – 480 с.
5. Оре О. Теория графов. – М.: Наука, 1980. – 336 с.
6. Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1986. – 383 с.
7. Сешу С., Рид М.Б. Линейные графы и электрические цепи. – М.: Высшая школа, 1971. – 448 с.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора