Глава x орієнтовані графи

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

В цьому розділі вивчаються орієнтовані графи.

§ 63. Основні визначення

Нехай V - кінцеве непорожня множина, V2 - його де-картов квадрат. Орієнтований граф (орграф) -це па-ра (V. А), де AV 2. Елементи множини V називають-ся вершинами орграфа G- (V, А), а елементи множини А - його дугами. Таким чином, дуга - це впорядкований-ва пара вершин. Безлічі вершин і дуг орграфа G позначаються через VG і AG відповідно. Число | VG | називається порядком орграфа G і позначається через | G |.

Якщо х - (і, v) - дуга, то вершини і та v називаються її кінцевими вершинами, причому і називається початком дуги x, a v - кінцем. Кажуть, що дуга инцидентна каж-дой зі своїх кінцевих вершин. Кажуть також, що дуга виходить зі свого початку і заходить в свій кінець. Дуга з співпадаючими початком і кінцем, тобто дуга виду (v, v), називається петлею. Можна визначити орієнтовані графи з декількома дугами, що мають спільний початок і загальний кінець (мультиграфом). Такі дуги називаються паралельними.

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

Нехай G - деякий орграф. Орієнтованим маршрутом (або просто маршрутом) в графі G називається:

Маршрут називається циклічним, якщо його перша і остання вершини збігаються. Циклічний шлях називається контуром. Очевидно, що будь-який (і, v) -Маршрут при і ≠ v містить (і, v)-шлях, а при і = v- контур.

Якщо в орграфе існує (і, v) -Маршрут. то кажуть, що вершина vдостіжіма з вершини і. Будь-яка вершина вважається досяжною з себе самої.

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

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

Очевидно, що кожен сильний граф є одне-стороннім, а кожен односторонній - слабким.

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

На рис. 63.2, а зображений сильний орграф, на рис. 63.2, б - односторонній, а на рис. 63.2, в - слабкий.

Маршрут, що містить всі вершини орграфа G, на-ни опиняються остовне.

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

> Необхідність. Нехай G - сильний орграф і Т = (v0, х0, v1, х2,. Хп, v0) -його циклічний маршрут, що проходить через максимально можливе число вершин. Якщо цей маршрут не є остовне, то візьмемо поза ним вершину і. Так як G - сильний орграф, то сущест-вують маршрути

Але тоді циклічний маршрут

містить більше, ніж Т, число вершин, що суперечать-чит вибору маршруту Т. Отже, Т - остовно маршрут.

Достатність. Нехай і і v - дві довільні вершини орграфа G, а

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

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

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

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

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

На рис. 63.3 представлені орграф G і його конденсація G *.

Затвердження 63.3.КонденсаціяG * будь-якого Оргрім-фаGне має контурів.

> Проведемо доказ від протилежного. Нехай Т = (so, xi, si,. So) - контур в G *. Тоді кожна вер-шина, що входить в компоненту Si, досяжна з будь-якої вершини, що входить в компоненту Sj. Але це суперечать-чит максимальності сильних компонент. <

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

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

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

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