Тема 9. Графи. Основні поняття й операції.
Питання теми
1. Походження графів.
2. Орієнтовані графи.
3. Зважені графи.
4. Типи скінчених графів.
Основні терміни теми : граф, дуга, орграф, мультиграф, псевдограф.
1. Походження графів
Багато задач зводяться до розглядання сукупності об’єктів, існуючи властивості яких описуються зв’язками між ними. Приклад тому: мапа автомобільних доріг, електричні ланцюги, відношення між людьми, подіями і т.ін. В подібних випадках зручно, об’єкти, які розглядаються, відображати крапками, які звуться вершинами, а зв’язки між ними - лініями (будь-якої конфігурації), які звуться ребрами.
Означення. Множина вершин V, зв’язки між якими означені множиною ребер Е, називають графами та позначають G=(V,E).
Перша робота по графам Леонарда Ейлера 1736 р. Задача про кенінсбергські мости: чи можливо здійснити прогулянку таким чином, щоб виходячи з любого місця міста, повернутися в нього, проходячи в точності 1 раз по кожному мосту.
Рис. 1. До задачі про кенінгсберські мости:
а - план міста; б - граф.
2. Орієнтовані графи
Часто зв’язки між об’єктами характеризуються означеною орієнтацією.
Приклад. Однобічний рух на вулицях, рух постійного струму, відношення підлеглості та старшинства серед людей та ін.
Для указування напрямку зв’язку між вершинами графа відповідне ребро відмічається стрілкою. Орієнтоване ребро називається дугою, а граф з орієнтованими ребрами - орієнтованим графом чи орграфом.
Якщо пара вершин з’єднана двома чи більшим числом дуг, то такі дуги називають паралельними. При цьому дві дуги одного напрямку по відношенню до даної вершини називають точно паралельними, а різного напрямку - неточно паралельними. Неточно паралельні дуги можна замінити ребром. Тоді дійдемо до змішаного графа, який має ребра та дуги.
Рис. 2. Орієнтований граф
Змінив напрямок всіх дуг орграфа на протилежний, отримаємо орграф, зворотний даному. Якщо напрямок дуг орграфа не має значення та кожна дуга є неорієнтоване ребро, то він називається співвіднесеним (неорієнтованим) графом.
2. Зважені графи
Подальше узагальнення відображення зв’язків між об’єктами за допомогою графів складається в приписуванні ребрам та дугам деяких кількісних значень, якісних ознак чи характерних властивостей, які називають вагою.
Це може бути порядкова нумерація ребер та дуг, яка показує на чергу при їх розгляданні (пріоритет чи ієрархія). Вага ребра може означати довжину шляху, пропускну здібність, напругу чи струм, кількість набраних очок, колір провідника, характер відношень між людьми та ін. Вагу можливо приписувати не тільки ребрам та дугам, але і вершинам.
Особливе значення для моделювання фізичних систем придбали зважені орієнтовані графи, які називають графами потоків сигналів чи сигнальними графами. Сигнальні графи знаходять широке застосування в теорії ланцюгів та систем, а також в багатьох інших областях науки і техніки.
4. Типи скінчених графів
Якщо множина вершин графа скінчена, то він називається скінченим графом. Скінчений граф G=(V,E), який вміщує p вершин та q ребер називається (p,q) - графом.
Нехай V={v ,v , ... ,v } та E={e ,e , ... ,e } - відповідно множина вершин та ребер (p,q) - графа. Кожне ребро e E об’єднує пару вершин v ,v V, які є його кінцями (граничними вершинами). Для орієнтованого ребра (смуги) розрізнюють початкову вершину, з якої дуга виходить, та кінцеву вершину, в яку дуга заходить. Ребро, кордонними вершинами якого є одна і та ж вершина, називають петлею. Ребра з однаковими кордонними вершинами є паралельними та називають кратними. У загальному випадку граф може вміщувати також ізольовані вершини, які не є кінцями ребер та не зв’язані ні між собою а ні з іншими вершинами. Наприклад, для (5, 6)-графа на рис. 3, а V={v , v , v , v , v }; E={e , e , e , e , e , e }; ребра е і е паралельні, ребро е є петлею, а v - ізольована вершина.
Число ребер, зв’язаних з вершиною ,називають ступенями вершини та позначають через (V ) або deg(V ). Так, для графа на рис. 9,а , i т.д. Ступень ізольованої вершини дорівнює нулю . Вершина ступені одиниця називається кінцевою або висячою вершиною ( ). Легко показати, що у кожному графі сума ступенів усіх вершин дорівнюється подвійному числу ребер, а число вершин непарного ступеню завжди парно. В орграфі розрізняють позитивні та негативні ступені вершин, які дорівнюють відповідно числу виходячих з V та заходячих в V дуг. Наприклад, для вершини d орграфа (див. рис. 2, а) маємо (d)=2 i (d)=3. Очевидно, додаток позитивних та негативних ступенів усіх вершин орграфа рівні між собою і рівні також кількості всіх дуг.
а) б)
Рис. 3. Типи графів:
а - псевдограф; б - повний граф.
Граф без петель та кратних ребер називають простим або звичайним. Граф без петель, але з кратними ребрами називають мультиграфом. Найбільш загальний випадок графа, коли дозволяються петлі та кратні ребра, називають псевдографом . Так, граф на рис. 1, б - це мультиграф, а на рис. 3, а - псевдограф. Якщо граф не має ребер (Е= ), тоді всі його вершини ізольовані (V ), і він називається порожнім або нуль-графом. Звичайний граф, у якого любі дві вершини з’єднані ребром, називається повним (на рис. 9, б доданий приклад повного графа з шістьома вершинами).
Якщо множина вершин V звичайного графа дозволяє розбиття на дві підмножини, що не перетинаються: і , тобто не існує ребер, які об’єднують вершини однієї і тієї ж множини, то він називається двудольним або біграфом. Орієнтований граф рахується простим, якщо він не має точно паралельних дуг та петель.
Граф, ступені всіх вершин якого однакові та дорівнюють r , називається однорідним (регулярним) r-ї ступені. Повний граф з n вершинами завжди однорідний ступені n-1, а пустий граф однорідний ступені 0.