Заданий орієнтований граф. Орієнтований графік. Графи з петлями, змішані графи, порожні графи, мультиграфи, звичайні графи, повні графи

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

Основні поняття

Формально, орграф D = (V, E) (\displaystyle D=(V,E))складається з безлічі V (\displaystyle V), елементи якого називаються вершинами, і безлічі E (\displaystyle E)упорядкованих пар вершин u , v ∈ V (\displaystyle u,v\in V).

Дуга (u, v) (\displaystyle (u,v)) інцидентнавершин u (\displaystyle u)і v (\displaystyle v). При цьому кажуть, що u (\displaystyle u) - початкова вершинадуги, а v (\displaystyle v) - кінцева вершина.

Зв'язок

Маршрутомв орграфі називають чергується послідовність вершин і дуг, виду v 0 (v 0, v 1) v 1 (v 1, v 2) v 2 . . . v n (\displaystyle v_(0)\(v_(0),v_(1)\)v_(1)\(v_(1),v_(2)\)v_(2)...v_(n))(Вершини можуть повторюватися). Довжина маршруту- кількість дуг у ньому.

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

Контурє замкнутий шлях.

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

Орграф сильно зв'язковий, або просто сильнийякщо всі його вершини взаємно досяжні; односторонньо зв'язковий, або просто одностороннійякщо для будь-яких двох вершин, принаймні одна досяжна з іншої; слабо зв'язковий, або просто слабкийякщо при ігноруванні напрямку дуг виходить зв'язковий (мульти)граф;

Максимальний сильнийпідграф називається сильною компонентою; одностороння компонентаі слабка компонентавизначаються аналогічно.

Конденсацієюорграфа D (\displaystyle D)називають орграф, вершинами якого служать сильні компоненти D (\displaystyle D), а дуга в D ⋆ (\displaystyle D^(\star ))показує наявність хоча б однієї дуги між вершинами, що входять до відповідних компонентів.

Додаткові визначення

Направлений ациклічний графабо гамакє безконтурний орграф.

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

Зображення та властивості всіх орграфів з трьома вузлами

Легенда: З- слабкий, ОС- односторонній, СС- сильний, Н- є спрямованим графом, Г- є гамаком (ациклічний), Т- є турніром

0 дуг	1 дуга	2 дуги	3 дуги	4 дуги	5 дуг	6 дуг
порожній, Н, Г	Н, Г		ОС	CC	CC	повний, CC
		ОС, Н, Р	CC, Н, Т	CC
		C, Н, Г	ОС, Н, Р, Т	ОС
		C, Н, Г	ОС

У попередніх розділах ми надали деякі основні результати теорії неорієнтованих графів. Однак, для опису деяких ситуацій неорієнтованих графів недостатньо. Наприклад, при поданні схеми вуличного руху графом, ребра якого відповідають вулицям, для вказівки допустимого напрямку руху ребрам необхідно надавати орієнтацію. Іншим прикладом є програма для ЕОМ, що моделюється графом, ребра якого представляють потік управління від одних множин інструкцій до інших. У такому поданні програми для вказівки напряму потоку керування ребрам також необхідно присвоїти орієнтацію. Ще одним прикладом фізичної системи, для представлення якої потрібний орієнтований граф, є електричний ланцюг. Застосування орієнтованих графів та відповідні алгоритми розглядаються в гол. 11-15.

У цьому розділі пропонуються основні результати теорії орієнтованих графів. Обговорюються питання, пов'язані із існуванням орієнтованих ейлерових ланцюгів та гамільтонових циклів. Розглядаються також орієнтовані дерева та їх зв'язок із орієнтованими ейлеровими ланцюгами.

5.1. Основні визначення та поняття

Почнемо із запровадження кількох основних визначень та понять, що належать до орієнтованих граф.

Орієнтований граф складається з двох множин: кінцевої множини V, елементи якої називаються вершинами, і кінцевої множини Е, елементи якої називаються ребрами або дугами. Кожна дуга пов'язана з упорядкованою парою вершин.

Для позначення вершин використовуються символи, а для позначення дуг-символи. Якщо , то називаються кінцевими вершинами у своїй - початкова вершина, - кінцева вершина . Всі дуги, що мають одну пару початкових і кінцевих вершин, називаються паралельними. Дуга називається петлею, якщо інцидентна вершина є одночасно початковою та кінцевою її вершиною.

У графічному поданні орієнтованого графа вершини зображуються точками чи кружками, а ребра (дуги) – відрізками

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

Наприклад, якщо такі, що їх), орієнтований граф можна подати рис. 5.1. У цьому графі – паралельні дуги, а – петля.

Мал. 5.1. Орієнтований графік.

Кажуть, що дуга інцидентна своїм кінцевим вершинам. Вершини називаються суміжними, якщо вони є кінцевими однією дуги. Якщо дуги мають загальну кінцеву вершину, вони називаються суміжними.

Дуга називається що виходить зі своєї початкової вершини і заходить у свою кінцеву вершину. Верщина називається ізольованою, якщо вона не має інцидентних дуг.

Ступенем вершини називається число інцидентних їй дуг. Напівступенем заходу вершини є число тих, що заходять в V] дуг, а півступенем результату - число тих, що виходять з дуг. Символами і б" позначають мінімальне півступеня результату та заходу орієнтованого графа. Аналогічно символами позначають максимальні півступеня результату та заходу відповідно.

Безліч будь-якої вершини визначаються так: . Наприклад, у графі на рис. 5.1.

Зауважимо, що петля збільшує півступеня як заходу, і результату цієї вершини. Наступне твердження є наслідком того, що кожна дуга збільшує на 1 суму півступеня як заходу, так і результату орієнтованого графа.

Теорема 5.1. В орієнтованому графі з дугами

Сума напівступеня заходу = Сума напівступеня результату = m.

Підграфи та породжені підграфи орієнтованого графа визначаються так само, як і у разі неорієнтованих графів (розд. 1.2).

Неорієнтований граф, що виходить в результаті зняття орієнтації з дуг орієнтованого графа G, називається основою неорієнтованого графа G і позначається через .

Орієнтованим маршрутом орієнтованого графа називається така кінцева послідовність вершин

Що є дугою графа G. Такий маршрут зазвичай називається орієнтованим маршрутом, причому початкова вершина, - кінцева вершина маршруту, а всі інші вершини - внутрішні. Початкова та кінцева вершини орієнтованого маршруту називаються його кінцевими вершинами. Зазначимо, що дуги, а отже, і вершини можуть з'являтися в орієнтованому маршруті більше одного разу.

Орієнтований маршрут називається відкритим, якщо його кінцеві вершини різні, інакше - замкнутим.

Орієнтований маршрут називається орієнтованим ланцюгом, якщо його дуги різні. Орієнтований ланцюг є відкритим, якщо його кінцеві вершини різні, інакше - замкненим.

Відкритий орієнтований ланцюг називається орієнтованим шляхом, якщо різні всі його вершини.

Замкнений орієнтований ланцюг називається орієнтованим циклом або контуром, якщо його вершини, за винятком кінцевих, різні.

Говорять, що орієнтований граф ациклічний чи безконтурний, якщо він не має контурів. Наприклад, ациклічним є орієнтований граф на рис. 5.2.

Мал. 5.2. Ациклічний орієнтований граф.

Мал. 5.3. Сильно зв'язковий орієнтований граф.

Послідовність вершин орієнтованого графа G називається маршрутом у G, якщо вона є маршрутом орієнтованого графа, що лежить в основі неорієнтованого Наприклад, послідовність у графі на рис. 5.2 є маршрутом, але з орієнтованим.

Аналогічним чином визначаються ланцюг, шлях та цикл орієнтованого графа.

Орієнтований граф називається зв'язковим, якщо зв'язковим є неорієнтований граф, що лежить в його основі.

Підграф орієнтованого графа G називається компонентом графа G, якщо він є компонентом графа

Вершини орієнтованого графа G називаються сильно зв'язковими, якщо G існують орієнтовані шляхи з і назад. Якщо сильно зв'язна з тим, очевидно, , сильно зв'язна з . Будь-яка вершина дуже зв'язана сама з собою.

Якщо вершина сильно зв'язна з вершиною, то, як легко бачити, вершина сильно зв'язна з вершиною Отже, в цьому випадку просто кажуть, що вершини сильно зв'язні.

Орієнтований граф називається сильно зв'язковим, якщо сильно зв'язні всі його вершини. Наприклад, дуже зв'язковим є граф на рис. 5.3.

Максимальний зв'язний підграф орієнтованого графа G називається сильно зв'язною компонентою графа G. Якщо орієнтований граф сильно зв'язаний, то він має єдину зв'язну компоненту, а саме самого себе.

Розглянемо орієнтований граф. Легко бачити, що будь-яка його вершина належить точно одному сильно зв'язному компоненту графа G. Отже, безліч вершин сильно зв'язкових компонент утворюють розбиття безлічі вершин У графа

Мал. 5.4. Граф та його конденсація.

Наприклад, орієнтований граф на рис. 5.4 а має три сильно зв'язні компоненти з множинами вершин і утворюють розбиття безлічі вершин орієнтованого графа.

Цікаво, що в орієнтованому графі можуть бути дуги, які не входять ні в які зв'язні компоненти графа. Наприклад, ні в які зв'язні компоненти не входять дуги в графі на рис. 5.4 а.

Таким чином, хоча властивість «сильної зв'язності» тягне за собою розбиття безлічі вершин графа, воно може не породжувати розбиття безлічі дуг.

Об'єднання, перетин, сума по mod 2 та інші операції над орієнтованими графами визначаються так само, як і у разі неорієнтованих графів (розд. 1.5).

Граф, що у результаті стягування всіх дуг сильно зв'язувальних компонент орієнтованого графа G, називається конденсованим графом графа G. Конденсація графа, наведеного на рис. 5.4 а, представлена ​​на рис. 5.4 б.

Вершини графа відповідають дуже зв'язним компонентам графа G і називаються конденсованими образами компонентів.

Ранг і цикломатичне число орієнтованого графа самі, що й у відповідного неорієнтованого графа. Це означає, що якщо орієнтований граф G має дуг, вершин і компонент, то ранг та цикломатичне число графа G визначаються виразами

Тепер визначимо мінімально зв'язні орієнтовані графи та вивчимо деякі їх властивості.

Орієнтований граф G називається мінімально зв'язковим, якщо він дуже зв'язковий, а видалення будь-якої дуги позбавляє його властивості сильної зв'язності.

Мал. 5.5. Мінімально зв'язковий орієнтований граф.

Мінімально зв'язковим є, наприклад, граф, поданий на рис. 5.5.

Очевидно, що мінімально зв'язкові графи не можуть мати паралельних дуг та петель.

Ми знаємо, що неорієнтований граф мінімально зв'язаний тоді і лише тоді, коли він є деревом (упр. 2.13). По теоремі 2.5 дерево має щонайменше двох вершин ступеня 1. Отже, мінімально зв'язні неорієнтовані графи мають принаймні дві вершини ступеня 1.

Встановимо аналогічний результат для орієнтованих графів. Ступінь будь-якої вершини сильно зв'язкового орієнтованого графа має бути не менше 2, оскільки кожна вершина повинна мати вихідну та західну дуги. У наступній теоремі ми доводимо, що у мінімально зв'язковому орієнтованому графі є принаймні дві вершини ступеня 2.

На першому занятті, вводячи поняття графа, ми розглядали як приклад змагання спортивних команд. Ми. з'єднували дві команди, скажімо А і С, ребром АС у тому випадку, коли ці команди вже грали одна з одною. Однак такий граф не дає відповіді на одне дуже важливе питання: хто саме виграв гру?
Цей недолік легко можна усунути. Якщо команда А виграла С, умовимося ставити на ребрі АС стрілку, спрямовану від А до С. Припустимо, що нам відомі результати всіх вже зіграних ігор, і додамо до графа рис. 1 відповідні стрілки; нехай при цьому вийде граф, зображений на рис. 58.

Рис. 58.

На цьому графі показано, що команда А виграла С, команда F програла А, а В виграла всі ігри - з С, Е, F і т. д.

Ребрографа називається орієнтованимякщо одну вершину вважають початком ребра, а іншу - кінцем.
Граф, всі ребра якого орієнтовані, називається орієнтиним графом.
Одна й та вершина орієнтованого графа може бути початком одних ребер і кінцем іншим. Відповідно розрізняють два ступені вершини: ступінь виходу та ступінь входу.
ступенем виходувершини А орієнтованого графа називається число ребер, що виходять з А (позначення: d+(A)).
Ступенем входу вершини А орієнтованого графа називається число входять до Аребер (позначення: d-(A)).
А якщо якась гра закінчилася внічию? Ми можемо відобразити нічийні результати на графі, залишаючи відповідні ребра неорієнтованими. При цьому ми отримаємо так званий смішанований граф, На якому є як орієнтовані, так і неорієнтовані ребра.
Шляхом в орієнтованому графі G від А1 до Аn називається послідовність орієнтованих ребер<А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, Така, що кінець кожного попереднього ребра збігається з початком наступного і жодне ребро не зустрічається більше одного разу.

Мал. 59
Якщо в орієнтованому графі G знайшовся шлях від Адо, то зворотного шляху від Удо Аможе не бути (рис. 59).
Якщо існує орієнтований шлях від А до В, то кажуть, що В досягнимаз А,
У графі G малюнку 38 Досяжна
з А, А не досяжна з Ст.
Простим шляхомв орієнтованому графі називається шлях, у якому жодна вершина не міститься більше одного разу. Замкнений шляхв орієнтованому графі називається орієнтованим циклом.
Довжиною шляхуназивається число ребер у цьому шляху.
Відстаньвід А до В в орієнтованому графі називається довжина найкоротшого шляху від А до В. Якщо шляху від А до В не існує, то відстань від А до В називають нескінченним і позначають? Відстань від А до будемо позначати S (АВ). Для графа малюнку 38
S(АВ) = 1, S(СВ) - 2, S(ВС) = ?.
Завдання 9.1.
У приморському курортному місті після встановлення одностороннього руху виявилося, що кількість вулиць, якими можна в'їхати на кожне перехрестя, дорівнює кількості вулиць, якими можна з нього виїхати. Доведіть, що можна запропонувати такий маршрут патрулювання, який починається і закінчується в одному місці і проходить через кожну ділянку вулиць рівно один раз.
Рішення.
Побудуємо орграф G, який задає рух у місті.
Орграф називається зв'язковим,якщо від будь-якої його вершини до будь-якої іншої можна перейти дугами без урахування їх орієнтації. Зв'язковий орграф називається ейлеровим,якщо в ньому є цикл ейлерів.
Теорема 12. Зв'язковий орграф є ейлеровим тоді і лише тоді, коли для кожної його вершиниvвиконується рівністьd- (v) = d+ (v) .
Теорема доводиться так само, як і теорема в задачі 4.2.
З умови завдання слід, що з вершин побудованого графа G виконується рівність d-(v) = d+(v). Отже, граф G ейлерів, та ейлерів цикл визначить потрібний маршрут патрулювання.
Завдання 9.2.
На площині відзначено кінцеве число точок. Деякі пари точок є початками і кінцями векторів, причому число векторів, що входять до будь-якої точки, дорівнює числу векторів, що виходять з неї. Знайдіть суму векторів.
Рішення.
Точки площини разом із векторами утворюють орграф G. Цикл орграфа, всі вершини якого різні, називається контуром.
Теорема 13. Зв'язковий орграфGейлерів тоді і лише тоді, колиGє об'єднанням контурів, які попарно не мають спільних ребер.
Доведення. Необхідність. Нехай G – ейлерів орграф. Розглянемо будь-яку вершину u1. Вийдемо з вершини u1по деякій дузі (u1, u2). Це можливо зробити, так як орграф Gзв'язковий. Оскільки d-(u2) = d+(u2), то з вершини u2можна вийти дугою (u2, u3) . Орграф G має кінцеве число вершин, тому, зрештою, ми потрапимо в деяку вершину w, в якій були раніше. Частина ланцюга, що починається і закінчується у вершині w, є контуром С1. Вилучимо дуги контуру С1 з орграфа G . У орграфі G1 (можливо незв'язному) ступеня входу і виходу вершин, що належали С, зменшилися на одиницю, ступеня входу і виходу інших вершин не змінилися. Отже, для будь-якої вершини v орграфа С1 виконуватиметься рівність d-(v) = d+(v). Тому в орграфі G1 можна виділити контур C 2 і т.д.
Достатність доводиться шляхом поєднання контурів у ейлерів цикл (див. доказ теореми в задачі 4.2).
Теорему доведено. Можливо, орграф G, який задає вектори в нашому завданні, не є зв'язковим. Застосувавши доведену теорему кожної зв'язкової частини орграфа, отримаємо розбиття векторів на контури. Сума векторів, що належать одному контуру, дорівнює нулю. Отже, сума всіх векторів дорівнює нулю.

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

Декілька прикладів дадуть трохи поверхового уявлення про граф. Так типовим графом є ​​схема метро чи будь-який інший маршрут. Зокрема, програмісту знайома комп'ютерна мережа, яка також є графом. Загальне тут це наявність точок, з'єднаних лініями. Так, у комп'ютерної мережі точки – це окремі сервери, а лінії – різні види електричних сигналів. У метрополітені перше – станції, друге – тунелі, прокладені з-поміж них. Теоретично графів точки називається вершинами (вузлами), а лінії – ребрами (дугами). Таким чином, граф- Це сукупність вершин, з'єднаних ребрами.

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

Повернімося до комп'ютерної мережі. Вона має певну топологію, і може бути умовно зображена у вигляді деякого числа комп'ютерів і шляхів, що їх з'єднують. На малюнку нижче як приклад показано повнозв'язкову топологію.

Це насправді граф. П'ять комп'ютерів є вершинами, а з'єднання (шляхи передачі сигналів) з-поміж них – ребрами. Замінивши комп'ютери вершинами, ми отримаємо математичний об'єкт – граф, який має 10 ребер та 5 вершин. Пронумерувати вершини можна довільним чином, а чи не обов'язково оскільки це зроблено малюнку. Варто зазначити, що в даному прикладі не використовується жодної петлі, тобто такого ребра, яке виходить з вершини і відразу входить до неї, але петлі можуть зустрічатися в завданнях.

Ось деякі важливі позначення, які використовуються в теорії графів:

• G = (V, E), тут G - граф, V - його вершини, а E - ребра;
• |V| - Порядок (число вершин);
• |E| - Розмір графа (число ребер).

У разі (рис. 1) |V|=5, |E|=10;

Коли з будь-якої вершини доступна будь-яка інша вершина, такий граф називається неорієнтованимзв'язковим графом (рис. 1). Якщо ж граф зв'язковий, але це умова не виконується, тоді такий граф називається орієнтованимчи орграфом (рис. 2).

У орієнтованих та неорієнтованих графах є поняття ступеня вершини. Ступінь вершини- Це кількість ребер, що з'єднують її з іншими вершинами. Сума всіх ступенів графа дорівнює подвійній кількості всіх його ребер. Для малюнка 2 сума всіх ступенів дорівнює 20.

В орграфі, на відміну від неорієнтованого графа, є можливість рухатися з вершини h до вершини s без проміжних вершин, лише коли ребро виходить з h і входить у s, але не навпаки.

Орієнтовані графи мають таку форму запису:

G=(V, A), де V – вершини, A – спрямовані ребра.

Третій тип графів змішаніграфи (рис. 3). Вони мають як спрямовані ребра, і ненаправленные. Формально змішаний граф записується так: G=(V, E, A), де кожна з літер у дужках означає також, що їй приписувалося раніше.

У графі малюнку 3 одні дуги спрямовані [(e, a), (e, c), (a, b), (c, a), (d, b)], інші – неспрямовані [(e, d), (e, b), (d, c) ...].

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

Вони еквівалентні один одному, адже не змінюючи структуру одного графа, можна побудувати інший. Такі графи називаються ізоморфними, Т. е. володіють тим властивістю, що будь-яка вершина з певним числом ребер в одному графі має тотожну вершину в іншому. На малюнку 4 зображено два ізоморфні графи.

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

У кожному з розглянутих нами графів є можливість виділити шлях і, причому не один. Шлях- Це послідовність вершин, кожна з яких з'єднана з наступною за допомогою ребра. Якщо перша та остання вершини збігаються, то такий шлях називається циклом. Довжина шляху визначається кількістю складових його ребер. Наприклад, малюнку 4.а шляхом служить послідовність [(e), (a), (b), (c)]. Цей шлях є підграфом, оскільки до нього застосовується визначення останнього, а саме: граф G'=(V', E') є підграфом графа G=(V, E), тільки тоді, коли V' і E' належать V, E .