Спрямовані графи. Теорія графів. Основні поняття і види графів. Приклад використання матриці суміжності

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

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

Формально, орграф 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, Н, Г	ОС

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

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

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

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

Це по суті граф. П'ять комп'ютерів є вершинами, а з'єднання (шляхи передачі сигналів) між ними - ребрами. Замінивши комп'ютери вершинами, ми отримаємо математичний об'єкт - граф, який має 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 .

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

Ребро - впорядкована пара вершин. Граф, для якого вказано напрямок кожного його ребра, називається орієнтованим.

Очевидно додаток до турнірів. Напрмер, стрілка йде від команди, що програла до виграла, тому орієнтований граф показує не тільки хто з ким зіграв, але і хто виграв.

Також можна задавати орієнтованими графами відношення слідування або переваги.

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

Наприклад, при складній оцінці зразків (в геології, наприклад) напрямок ребра вказує перевагу. У нормальній системі переваг не повинно бути циклів

Таня Наташа

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

Односторонній рух.

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

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

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

Ясно, що кожен такий граф повинен бути зв'язковим, однак цього недостатньо.

Ребро Е = (А, В) будемо називати зв'язує ребром, або перешийком, Якщо воно є єдиним шляхом від А до В (або навпаки).

Свюзивающее ребро ділить всі вершини графа на дві множини: ті, в які можна прийти з А, не проходячи по ребру Е, і ті, в які можна прийти з В, не проходячи по Е. Граф в цьому випадку складається з двох частин G 1 і G 2 з'єднаних тільки ребром Е (рис. a і a + 1).

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

Якщо ребро Е i = (А i, У i) не є сполучною, то знайдеться інший шлях, що з'єднує А i і В i і не проходить по Е i. Тому таке ребро будемо називати циклічним ребром.

рис.2 пов'язують рис. 2 + 1 Кінцеве (зв'язує) рис.2 + 2 Циклічне

ребро ребро

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

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

Ми можемо довести цю теорему, вказавши спосмоб відповідного орієнтування графа. виберемо в G довільне ребро Е = (А, В) . якщо Е - зв'язує ребро, воно залишиться двостороннім, і тоді можна буде перейти від А до В і назад (рис.2 + 3).

рис.2 + 3 рис. 2 + 4

якщо Е - циклічне ребро, то воно входить в деякий цикл С, на якому можна встановити циклічну орієнтацію (рис.2 + 4).

Припустимо, що ми вже орієнтували деяку частину Н графа G, так, що з будь-якої вершини графа Н можна пройти в будь-яку іншу його вершину з дотриманням правил одностороннього руху. Так як граф G є зв'язковим, то або Н збігається з усім графом G, або знайдеться ребро Е = (А, В), яке не належить Н , Але одна з його вершин, скажімо А , належить Н .

якщо Е - зв'язує ребро АВ , То воно залишиться двостороннім. Тоді для будь-якої вершини X графа Н можна знайти орієнтовану ланцюг R , що сполучає Х з А , А значить (через ребро Е ), І з В . Назад від вершини В через ребро Е можна перейти до А , А потім - за орієнтовною ланцюга Z - від А до Х (Рис a + 5). приєднуючи Е до H , Ми отримаємо вже більшу частину графа G , Що володіє необхідним властивостям. Якщо ж ребро Е = (А, В) є циклічним, воно належить деякому циклу З . Ми встановили напрямок на З від А до В і далі вздовж З до першої вершини D з З , що належить Н (Рис. A + 6).

Мал. a + 5 рис. a + 6

Всі ці ребра приєднаємо до Н . нехай Х - довільна вершина з Н , а У - будь-яка вершина з З ; можна знайти орієнтовану ланцюг R , що належить Н і що сполучає Х з А , А потім уздовж З пройти до вершини У з З . Назад, від У можна пройти вздовж З до вершини D , А від неї - що належить Н орієнтованої ланцюгом Z - від D до Х . Тому орієнтований граф, отриманий додаванням до Н зазначених ребер циклу З , Також задовольняє необхідним умовам. Продовжуючи цей процес, ми врешті-решт орієнтуємо потрібним чином вихідний граф G .

Ступені вершин.

Для орієнтованих графів ми маємо в кожній вершині число р (А) виходять і число р * (А) входять ребер. Загальна кількість ребер одно:

N = р (А 1) + р (А 2) + ... + р (А n) = p * (A 1) + p * (A 2) + ... + p * (A n)

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

р (А) = р * (А) = r

Вправа

Побудуйте однорідні орієнтовані графи ступеня r = 2 з числом вершин n = 2,6,7,8.

ВІДНОСИНИ.

Відносини і графи.

Будь-яка математична система має справу з безліччю якихось об'єктів, або елементів. (Прикмети: алгебра, геометрія)

Для того щоб побудувати математичну теорію, нам потрібні не тільки самі ці елементи, але також і відносиниміж ними. (Приклади: для чисел а> в; в геометрії -рівність трикутників, // прямих; в теорії множин - рівність і включення множин.)

Всі ці відносини стосуються двох об'єктів, тому вони називаються бінарними відносинами, або просто відносинами, Є й інші типи відносин, наприклад тернарние відносини, Що стосуються трьох об'єктів. (Наприклад, точка А лежить між точками В і С).

Введемо загальне визначення бінарного відношення R: аRв - в знаходиться у відношенні R до а.

Наприклад, ставлення а> в означає, що в належить множині всіх чисел, менших а

Фактично, кожен орієнтований граф G визначає певне відношення в безлічі його вершин. Це відношення можна записати у вигляді: аGв. Воно означає, що на графі є орієнтоване ребро, що йде від а до в.

Спеціальні умови.

Нехай дано деяке відношення R. Якщо елемент а перебуває у відношенні R сам з собою, то йому відповідає петля в графі

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

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

Для кожного відносини R можна визначити зворотне відношення R *, Вважаючи, що аr * в тоді і тільки тоді, коли аRв.

З визначення зворотного відносини видно, що якщо на графі G, відповідному R, є ребро (а, в), то на графі G *, відповідному R *, має бути ребро (в, а). Іншими словами, граф G * зворотним для G, тобто графом з тими ж ребрами, що і G, але протилежно орієнтованими.

відношення називається симметрическим, Якщо з аRв слід вRа.

Симетричної відношенню відповідає граф з неорієнтованими ребрами; назад, граф з неорієнтованими ребрами визначає деякий симетрична відношення.

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

відношення R транзитивно, Якщо з двох умов аRв і вRс слід, що аRc.

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

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

Відносини еквівалентності.

Ставлення еквівалентності, зазвичай позначається символом ~, характеризується наступними трьома властивостями:

1). Рефлексивностью: а ~ а;

2). Симметричностью: з а ~ в Þ в ~ а;

3). Транзитивності: з а ~ в і в ~ з Þ а ~ с.

Фактично відношення еквівалентності - узагальнення властивості рівності.

Ставлення еквівалентності вводить в безлічі вершин розбиття на непересічні класи еквівалентності.

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

Часткова впорядкованість.

ставлення часткової впорядкованості- це (на прикладі множин):

1). Рефлексивність: А Ê А

2). Транзитивність: якщо А Ê В і В Ê З Þ А Ê З

3). Тотожність: якщо А Ê В і В Ê АÞ А = В

Відносини суворого включення -

1). Антирефлексивне: А ÉА ніколи не має місця;

2). Транзитивність: якщо А É У і В É З, то А É З

ставлення впорядкованості(В прямому сенсі) називається сувора впорядкованість, а> в, для якої на додаток до попередніх умов виконано також наступне:

Умова повноти.Для будь-яких двох незбіжних елементів в і а завжди виконана одна з двох співвідношень а> в або в> а.

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

ПЛОСКІ ГРАФИ.

Умови для плоских графів.

Граф Куратовского До 3,3

Граф завдання про трьох будинках і трьох колодязях

Граф Куратовского До 5

Ці два графа - НЕ ПЛОСКІ!

розширення графа- на деякі ребра поставили нові вершини, так що ці ребра

стали елементарними ланцюгами, що складаються з декількох ребер.

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

теорема Куратовсого

Для того щоб граф був плоским, необхідно і достатньо, щоб він не містив в собі ніякого графа, який можна було стиснути до графа До 3,3 або графа До 5.

формули Ейлера

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

З визначення багатокутних графів слід, що вони зв'язні. Вимагатимемо також, щоб жоден багатокутник не лежала всередині іншого. Граничні ребра кожного такого багатокутника утворюють цикл, іноді званий мінімальним циклом. Частина площини, укладена всередині багатокутника, називається гранню графа. На графі є і максимальний цикл З 1, Навколишній весь граф з усіма його гранями. Будемо вважати частину площині, що лежить поза З 1, теж як грань графа з кордоном З 1 - нескінченнагрань F ¥.

позначимо через

число вершин, ребер і граней просторового багатокутника..

теорема Ейлера

в - р + р = 2

Доведення:Формула очевидна для багатокутника, що має n ребер. Дійсно, n вершин і n ребер, а також дві грані F 1 F ¥

Додамо нову грань до графу з г гранями, проводячи по межі F ¥ деяку елементарну ланцюг, що з'єднує дві вершини максімальног графа G. Якщо ця дуга має г ребер, то нам доведеться бобавіть г - 1 нову вершину і одну нову грань. Але тоді

в '- р' + г '= (в + г - 1) - (р + р) + (г + 1) = в - р + р (= 2!)

за припущенням індукції.

Матричні уявлення.

1. Матриця інціденцій А.

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

б). Для орієнтованого графа елемент матриці інціденцій дорівнює +1, коли вершина, инцидентная дузі, є початковою вершиною дуги (тобто дуга виходить з цієї вершини). Елемент дорівнює -1, коли дуга входить в вершину. Якщо вершини не инцидентна дузі, то елемент матриці дорівнює 0.

2. Матриця циклів С.

а). Для неорієнтованого графа рядка матриці циклів відповідають простим циклам графа, а стовпці - його ребрах. Елемент матриці a ij = 1, якщо цикл З i містить ребро e j. В іншому випадку a ij = 0.

б). Для орієнтованого графа a ij = 1, -1 або 0 в залежності від того, однакова або протилежна орієнтація циклу З i і дуги e j або ж даний цикл взагалі не містить дуги e j.

3. Матриця суміжності вершин (або просто матриця суміжності) V являє собою матрицю, рядки і стовпці якої відповідають вершинам, а елемент матриці a ij в разі неорієнтованого графа дорівнює числу ребер, що з'єднують вершини i і j. Для орієнтованого графа елемент a ij дорівнює числу ребер, спрямованих від вершини i до вершини j.

Оновние теореми, пов'язані з матричними уявленнями графів.

1) .Ранг (максимальне число лінійно-незалежних стовпців) матриці інціденцій А зв'язкового графа (орієнтованого і неорієнтованого) з n вершинами дорівнює (n-1).

2). Ранг матриці циклів З зв'язкового графа з m ребрами і n вершинами дорівнює (m-n + 1).

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

Наступне відображення показує, що графи G 1 і G 2 ізоморфні

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

A 2 = PA 1 P ", де

Р = , Або p ij = d p (i), j (символ Кронекера)

і Р "- транспонована матриця.

Знаходження матриці Р може бути нелегкою справою.

Изоморфность G 1 і G 2 означає, що А 1 і А 2 мають однакові власні значення. Однак ця умова не є достатнім (приклад внизу).

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

Орієнтовані і неорієнтовані графи

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

Графи, в яких всі ребра є дугами(Порядок двох кінців ребра графа істотний), називаються орієнтованими графами або орграф .

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

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

Якщо граф містить петлі, То ця обставина спеціально обумовлюють, додаючи до основної Харатеристики графа слова "з петлями", наприклад, "орграф з петлями". Якщо граф не містить петель, то додають слова "без петель".

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

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

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

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

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

двочастковий граф

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

Приклад 1.побудувати повнийдвочастковий граф.

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

Ейлеров граф

Ми вже торкалися завдання про Кенігсбергськая мостах. Негативне рішення Ейлером цього завдання привело до першої опублікованій роботі з теорії графів. Завдання про обхід мостів можна узагальнити і отримати наступне завдання теорії графів: чи можна знайти в цій графі цикл, що містить всі вершини і всі ребра? Граф, в якому це можливо, називається ейлеровим графом.

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

Приклад 2.Чи є повний граф з однаковим числом nребер, яким инцидентна кожна вершина, ейлеровим графом? Пояснити відповідь. Привести приклади.

Відповідь. якщо n- непарне число, то кожна вершина инцидентна n-1 ребрах. В такому випадку даний граф є ейлеровим графом. Приклади таких графів на малюнку нижче.

Регулярний граф

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

Число вершин регулярного графа k-го ступеня не може бути меншою k+1. У регулярного графа непарної ступеня може бути лише парне число вершин.

Приклад 3.Побудувати регулярний граф, в якому найкоротший цикл має довжину 4.

Рішення. Міркуємо так: для того, щоб довжина циклу задовольняла заданій умові, потрібно, щоб число вершин графа було кратно чотирьом. Якщо число вершин дорівнює чотирьом, то вийде граф, зображений на малюнку нижче. Він є регулярним, але в ньому найкоротший цикл має довжину 3.

Збільшуємо число вершин до восьми (наступне число, кратне чотирьом). З'єднуємо вершини ребрами так, щоб ступеня вершин були рівні трьом. Отримуємо наступний граф, що задовольняє умовам завдання.

Гамильтонов граф

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

Приклад 4.Заданий двочастковий граф, в якому n- число вершин з безлічі A, а m- число вершин з безлічі B. В якому випадку граф буде ейлеровим графом, а в якому випадку - гамільтоновим графом?