Маршрути у графах. Ланцюги і цикли

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

Ø напрямок кожної дуги повинне збігатися з напрямком шляху;

Ø жодне ребро шляху не повинне зустрічатися двічі.
Інакше кажучи, шлях— упорядкована послідовність ребер орієнтованого графа, у якій кінець попереднього ребра збігається з початком наступне й все ребра єдині.Циклв орграфі — шлях, у якого збігаються початок і кінець. Для циклів орграфа також справедлива теорема про циклічні підстановки. Ланцюг, шлях і цикл у графі називаються простими,якщо вони проходять через кожну з вершин не більше одного разу. Неорієнтований граф називається зв'язковим,якщо між будь-якими двома його вершинами є маршрут.Для зв'язного графа орієнтація дуг не обов'язкова. Так, граф (рис. 2.1, б) є зв'язковим, а граф (рис. 2.1, г) — незв'язним.Також можна ввести поняття зв’язності для вершин графа: дві вершини називаються зв'язковими,якщо існує маршрут між ними. Зрозуміло, що зв’язність між вершинами є бінарним відношенням. Це відношення буде відношенням еквівалентності. Дійсно, відношення зв’язністі має відомі властивості, тобто воно:

Ø рефлексивне — кожна вершина (включаючи ізольовані) зв'язна сама із собою;

Ø симетричне — будь-який маршрут можна представити у зворотному порядку:

Ø транзитивне — якщо вершина V з'єднана з вершиною маршрутом а вершина з'єднана з вершиною маршрутом то вершина V з'єднана з вершиною маршрутом у якому спочатку йдуть всі ребра маршруту а потім всі ребра маршруту

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

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

Теорема 2.3.Для того щоб зв'язний граф G був простим циклом, необхідно й досить, щоб кожна його вершина мала ступінь, рівну 2.

Рис.2.4. Граф з мостом CE

 

Ребро зв'язного графа G називається мостом,якщо після його видалення G стане незв'язним і розпадеться на два зв'язкових графа й На рис. 2.4 міст (CЕ)розділив зв'язний граф на два різних зв'язкових графа: з вершинами й з вершинами

 

Теорема 2.4.Ребро графа є мостом тоді й тільки тоді, коли не належить жодному циклу.

Які графи можна вважати різними, а які не розрізняються?

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

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

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

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

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

Рис. 2.5. Ізоморфні графи

Рис. 2.6. Графи:

а — (з областями

б — (з областями

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

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