Главная | Обратная связь | Поможем написать вашу работу!

Відстань, діаметр, радіус і центр графу

Нехай G - зв’язний, неорієнтований граф. Оскільки дві довільні вершини „ a ” і „ b ” – зв’язані, то в загальному випадку існує декілька простих ланцюгів S_i (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 і позначимо через

віддаль від с до найбільш віддаленої вершини графу.

Назвемо c ₀ центром графу G, якщо

Зауважимо, що центр графу не єдиний.

Рис.6

Наприклад, для графу, зображеного на рис. 6, радіус r ₀ = 1; центр графу c ₀ = v ₂ або c ₀ = v ₄.

Алгоритм Дейкстри

Розглянемо наступну задачу: заданий скінченний орієнтований граф G, кожному ребру якого приписана його числова характеристика („довжина”). Необхідно знайти найкоротший шлях від заданої вершини (позначимо її через s) до всіх решта вершин графу.

Для розв’язання цієї задачі найбільшого розповсюдження набув алгоритм Декстри, згідно з яким всі вершини графу G (V) необхідно впорядкувати по зростанню їх відстані від вершини s:

d (s, u ₀) £ d (s, u ₁) £ … £ d (s, u_n) і V = { u ₀, u ₁, …, u_n }.

Ця послідовність будується інтеративно. Перша вершина в ній відома:

u ₀ = s; d (s, u ₀) = 0.

Нехай відомі перші (l + 1) вершини цієї послідовності:

{ u ₀ = s, u ₁, …, u_l },

які ми будемо надалі називати фіксованими. Це означає, що вершина u ₁ ближча від s, ніж всі решта (тобто нефіксовані) вершини.

Для кожної нефіксованої вершини у графу модифікуємо її відстань від s: якщо існує e (u_i, v) і d (s, u_i) + d (u_i, v) £ d (s, v), то d (s, v) = d (s, u_i) + d (u_i, v) і передостанньою вершиною в найкоротшому (на даний час) шляху, який з’єднує s з v, буде вершина u_i. Після цього серед всіх нефіксованих вершин знаходимо ту, відстань до якої від s є найменшою. Ця вершина і буде наступною в послідовності (тобто u_i _{+ 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, знаходимо ту вершину v ₀, для якої

4) FIX(v ₀) = 1, u = v ₀.

5) i = i + 1.

якщо i £ n,

то йти на 2).

6) Кінець.

В результаті масив VID містить найкоротші відстані від s до всіх вершин графу; по масиву PRED можна отримати найкоротший шлях від s до довільної вершини графу.

Приклад.

Рис.7

Робота алгоритму проілюстрована в табл. 5, в якій кожний рядок відповідає одному циклу роботи алгоритму. Фіксовані вершини підкреслені, а біля вершини „ u ” на кожному кроці стоїть зірочка.

Таблиця 5

VID

PRED

∞

16*

∞

Найкоротший шлях від A, наприклад, до E будується, використовуючи масив PRED, таким чином: E D A.

Задача про ланцюги

Теорія графів почалася з розв’язування задачі про кенігсберзькі мости (Ейлер, 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), то будуємо граф G ₁ = G ‑ P (a, a), в якому всі вершини мають теж парний локальний степінь. Оскільки граф G (V) є зв’язним, то серед вершин P (a, a) має знайтись вершина „ b ”, яка зв’язана ребром хоча б з однією вершиною графу G (V) (інакше граф G був би незв’язним);

4) будуємо з ребер графу G ₁ ланцюг P ’, що починається у вершині „ b ” і може закінчуватись тільки у „ b ”; з ланцюгів P і P ’ будуємо новий цикл:

P ₁(a, a) = P (a, b) È P ’(b, b) È P (b, a);

5) якщо P ₁(a, a) не містить всіх ребер графу G (V), то, за аналогією з кроком 3) будуємо граф G ₂ = G – P ₁(a, a) і т.д.

З огляду на скінченність графу, цей процес зупинитися, коли всі ребра графу G (V) будуть вичерпані.

Узагальнюючи задачу Ейлера можна шукати найменшу кількість ланцюгів (не циклів!) P ₁, які не перетинаються по ребрах і покривають увесь зв’язний граф G (V).

Твердження. Нехай G (V) - скінченний зв’язний граф з k вершинами непарного локального степеня. Тоді мінімальна кількість ланцюгів, які не перетинаються по ребрах і покривають граф G, дорівнює k / 2.

Алгоритм побудови ланцюгів P_i.

1) з’єднуємо довільно чином пари вершин з непарним локальним степенем (для цього необхідно k / 2 ребер). При цьому утворюється граф G ₁, всі вершини якого мають парний степінь;

2) граф G ₁ є ейлеровим і в ньому існує ейлерів цикл S;

3) після відкидання з циклу S доданих на кроці 1) k / 2 ребер, отримуємо k / 2 ланцюгів, які покривають весь граф G.

Приклад

Рис. 10.

Степені вершин графу:

Вершина	a	b	c	d	e	f	g	h
Степінь

Таким чином, k = 4. З’єднаємо ребрами вершини (c, d) та (f, h) (на рис.10 ці ребра позначені штриховими лініями).

Поетапно побудуємо для утвореного графу цикл Ейлера:

а) P ₁ = (І, ІІІ, ІІ);

б) P ₂ = (І, ІХ, VI, IV, III, II);

в) P ₃ = (І, IX, XIII, XII, XI, VI, IV, III, II);

г) P ₄ = (I, IX, XIV, X, VIII, XIII, XII, XI, VI, IV, III, II);

д) P ₅ = (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 входять стільки ж ребер, скільки і виходить:

r (v) = r *(v).

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

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

Гамільтонові цикли

Визначення. Гамільтонів цикл – це цикл, який проходить по кожній вершині графа і рівно один раз.

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

Незважаючи на подібність у формулюванні для ейлерових і гамільтонових циклів, відповідні теорії мають мало спільного. Критерій існування ейлеревих циклів був встановлений достатньо просто; для гамільтонових циклів ніякого загального правила невідомо. Більше того, для конкретних графів іноді тяжко встановити, чи існує взагалі такий цикл. Тому обмежимось одним критерієм.

Твердження. (Дірак). Якщо в графі G (V) з n вершинами для довільної вершини v Î V: r (v) ³ n / 2, то в графі існує гамільтонів цикл.

На закінчення зауважимо, що є різні задачі пошуку маршрутів у графі:

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

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

- з’ясування чи граф є гамільтоновим

- знаходження маршрут, що зв’язує дві довільні задані вершини

- знайти найкоротший шлях з однієї заданої вершини в іншу задану вершину (зокрема для зважених графів)

Деякі класи графів

Дерева

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

Твердження 1. В дереві дві довільні вершини зв’язані єдиним ланцюгом (інакше був би цикл).

Твердження 2. Довільний ланцюг у дереві є простим.

Визначення. У довільному графі G вершина v називається кінцевою, якщо r (v) = 1, тобто існує одне ребро, інцидентне вершині v, і це ребро називається кінцевим.

Твердження 3. У дереві є хоча б дві кінцеві вершини.

Розглянемо дерево G і виберемо довільну вершину v ₀. Кожному ребру e = (a, b) зіставимо той кінець, який більш віддалений від v ₀ (оскільки в дереві всі ланцюги є простими, то від довільної вершини до v ₀ веде лише один ланцюг).

Твердження 4. Для дерева виконується рівність v_V – v_E = 1 (v_V - кількість вершин, v_E - кількість ребер).

Твердження 5. У дереві кожне ребро суттєве (його вилучення веде до порушення зв’язаності графа).

Визначення. В довільному скінченному зв’язаному графі G циклічний ранг:

g(G) = v_E ‑ v_V + 1.

Твердження. Для довільного скінченного зв’язаного графа G циклічний ранг

g(G) ³ 0

і дорівнює кількості ребер, які необхідно вилучити з G для того, щоб отримати дерево (скелет графа).

Для дерев g(G) = 0.

Дерева використовують для розв’язання такої задачі: необхідно з’єднати „ n ” міст залізничною колією таким чином, щоб не будувати зайвих ліній. При цьому вважається відомим вартість будівництва колії між двома довільними містами. Таким чином, необхідно побудувати зв’язний граф G, який містить всі задані вершини і для якого повна вартість була б найменшою. Очевидно, що граф G - дерево.

Алгоритм розв’язання.

Вибираємо ребро e_i з найменшою вартістю. Отримаємо граф A ₁ = { e ₁}. На кожному наступному кроці до A_i _‑₁ додаємо ребро, яке має найменшу вартість серед тих, що залишились, і таке, що граф A_i = A_i _‑₁ È { e_i } не має циклів. Останній граф A_n _‑ ₁ = G і є шуканим.

Двочасткові графи

Граф G =(V, E) називається двочастковим, якщо існує розбиття { V ₁, V ₂} множини вершин V на дві підмножини (частки) таке, що для довільного ребра (v, w)Î E виконується або v Î V ₁ i w Î V ₂, або v Î V ₂ i w Î V ₁.

Двочастковий граф G =(V, E) називається повним двочастковим графом, якщо для будь-якої пари вершин його часток v Î V ₁ i w Î V ₂ маємо (v, w)Î E. Якщо | V ₁|= m i | V ₂|= n, то повний двочастковий граф G позначається K_m _, _n.

Теорема (теорема Кеніга). Граф є двочастковим тоді і тільки тоді, коли всі його цикли мають парну довжину.

Визначення. Нехай G (V ₁, V ₂) - дводольний граф. Пароз’єднання – це підмножина ребер графу G:{(x_i, y_j), …}, де x_i Î V ₁ а y_j Î V ₂, причому жодні два ребра не мають спільних вершин.

Визначення. Максимальне пароз’єднання (П) – це пароз’єднання дводольного графу G, яке має найбільшу кількість ребер.

Розглянемо таку задачу: знайти максимальне пароз’єднання, яке містить всі вершини множини V ₁.

Твердження (теорема Холла). Максимальне пароз’єднання П дводольного графу покриває всі вершини множин V ₁ тоді і тільки тоді, якщо для довільної множини U ₁ Í V ₁ кількість елементів у множині U ₂ Í V ₂, яка містить всі вершини, з’єднані ребром хоча б однією вершиною з U ₁, не менша від кількості вершин множини U ₁.

Алгоритм побудови максимального пароз’єднання П.

Будемо вважати, що умови теореми Холла виконані. Задамося довільним пароз’єднанням П ₀. Якщо воно не охоплює всіх вершин множини V ₁, то існує x ₀: x ₀Î V ₁ і x ₀Ï П ₀.

Побудуємо

W ₀ = { x ₀};

W ₁ = { y | (x ₀, y) Î G };

W ₂ = { x | (x, y) Î П ₀, y Î W ₁, x Ï W ₀};

W ₃ = { y | (x, y) Î G, x Î W ₂, y Ï W ₁};

W ₄ = { x | (x, y) Î П ₀, y Î W ₃, x Ï W ₀ È W ₂};

W ₅ = { y | (x, y) Î G, x Î W ₄, y Ï W ₁ È W ₃};

...

Зауважимо, що, згідно з побудовою, в множинах W ₁ і W ₂, W ₃ і W ₄, W ₅ і W ₆ і т.д. попарно однакова кількість елементів. Крім того, послідовність вершин W_i не може закінчитись на множині з парним індексом W ₂ _k, оскільки для множини

U ₁ = W ₀ È W ₂È … È W ₂ _k Í V ₁

кількість вершин у відповідній множині

U ₂ = W ₁ È W ₃È … È W ₂ _k _-₁ Í V ₂

(U ₂ містить всі вершини графу, які з’єднані ребром хоча б з однією з вершин множини U ₁) на одиницю більше, що суперечить умові теореми Холла. Тому існує вершина y *:

y * Î W ₂ _k _-₁ і y * Ï П ₀.

Тоді існує шлях S, який починається з x ₀, проходить через вершини множин W ₁ і закінчується в y * і містить непарну (2 k ‑ 1) кількість ребер:

S = { e ₁, e ₂, …, e ₂ _k _-₁},

причому всі парні ребра e₂ _k Î П ₀.

Нове пароз’єднання П ₁ будуємо наступним чином:

П ₁ = П ₀ \ { e ₂ È e ₄ È…È e ₂ _k _- ₂} È { e ₁ È e ₂ È…È e ₂ _k _- ₁}.

Пароз’єднання П ₁ містить на одне ребро і на одну вершину з множини V ₁ більше ніж П ₀. Якщо П ₁ охоплює всі вершини множини V ₁, то беремо деяку вершину x ₀: x ₀Î V ₁ і x ₀Î П ₁ і т.д.

Приклад

П ₀ = {(x ₁, y ₁), (x ₃, y ₂)}.

1) W ₀ = (x ₂); W ₁ = (y ₂); W ₂ = (x ₃); W ₃ = (y ₁); W ₄ = (x ₁); W ₅ = (y ₄).

e ₁ = (x ₂, y ₂); e ₂ = (x ₃, y ₂); e ₃ = (x ₃, y ₁); e ₄ = (x ₁, y ₁); e ₅ = (x ₁, y ₄).

П ₁ = {(x ₂, y ₂), (x ₃, y ₁), (x ₁, y ₄)}.

2) W ₀ = (x ₄); W ₁ = (y ₃, y ₄).

e ₁ = (x ₄, y ₃).

П = П ₂ = {(x ₁, y ₄), (x ₂, y ₂), (x ₃, y ₁), (x ₄, y ₃)}.

5. Плоскі та планарні графи

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

Таким чином виникає поняття плоского графа.

Граф називається плоским, якщо його діаграму можна зобразити на площині так, що лінії, які відповідають ребрам графа, не перетинаються (тобто мають спільні точки тільки у вершинах графа). Таке зображення називається плоскою картою графа.

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

Наприклад, граф, зображений на рис., планарний, оскільки він ізоморфний графу, зображеному поруч. Простий цикл, дерево і ліс - це також планарні графи.

Про планарні графи кажуть, що вони укладаються на площині або мають плоске укладання.

а) б)

Рис.

При дослідженні плоских графів особливе місце займають графи K ₅ i K _3,3, зображені на рис.

K ₅ K _3,3

Рис.

Граф K _3,3 виникає із задачі про три хати і три криниці.

Теорема. Графи K ₅ i K _3,3 не є планарними.

Значення графів K ₅ i K _3,3 полягає в тому, що вони є "єдиними" суттєво непланарними графами. Всі інші непланарні графи містять у собі підграфи "подібні" до K ₅ або K _3,3. Характер цієї подібності розкривається за допомогою таких понять.

Елементарним стягуванням графа G =(V, E) називається вилучення в графі G деякого ребра (v_i, v_j)Î E і злиття вершин v_i i v_j в одну вершину v, причому v інцидентна всім тим відмінним від (v_i, v_j) ребрам графа G, які були інцидентні або v_i, або v_j.

Кажуть, що граф G стягується до графа G ¢, якщо G ¢ можна отримати з G за допомогою послідовності елементарних стягувань.

Приклад. На рис. зображено графи G i G ¢, при цьому G стягується до G ¢.

G G ¢

Рис.

Наведемо без доведення важливу теорему теорії графів.

Теорема (теорема Куратовського). Граф G є планарним тоді і тільки тоді, коли він не містить підграфів, що стягуються до K ₅ або K _3,3.

⇐ Предыдущая 9 10 11 12 13 14 15 161718 Следующая ⇒