Главная | Обратная связь

Шляхи у орієнтованому графі

Шляхом (або орієнтованим маршрутом) у орграфі G=(V,E) між вершинами u та v орграфу G називається послідовність вершин даного орграфу виду u₁,…,u_n, де u₁=u, u_n=v, (u_i,u_i+1)ÎE, 1£i£n-1, nÎN⁺. Шляхом (або орієнтованим маршрутом) у орграфі G=(V,E) називається послідовність вершин даного орграфу виду u₁,…,u_n, де (u_i,u_i+1)ÎE, 1£i£n-1, nÎN⁺. Вершину шляху, що не є першою чи останньою, назвемо внутрішньою вершиною. Якщо між вершинами u та v орграфу G існує шлях u₁,…,u_n, будемо говорити, що вершини u та v з’єднані (сполучені) шляхом, або шлях u₁,…,u_n з’єднує вершини u та v, або вершина v досяжна з вершини u.

Шлях u₁,…,u_n у орграфі G називається циклічним (або замкнутим), якщо u₁=u_n.

Довжиною шляху u₁,…,u_n у орграфі G будемо називати число n-1, тобто число, що на одиницю менше кількості елементів у послідовності u₁,…,u_n. Шлях, що складається з однієї вершини, називається тривіальним. Довжина тривіального шляху дорівнює нулю.

Нехай, наприклад, задано орграф G=({1,2,3,4,5},{(1,2),(2,3),(3,4), (4,5),(5,2),(5,3)}). Розглянемо послідовність 3,4,5,3,4 вершин G. Перевіри-мо, чи утворюють дугу кожні дві сусідні вершини цієї послідовності. Маємо: (3,4) – дуга орграфу G, (4,5), (5,3), (3,4) – також дуги G. Таким чином, послідовність вершин 3,4,5,3,4 є шляхом між вершинами 3 та 4 у орграфі G. Довжина цього шляху дорівнює чотирьом. Послідовність вершин орграфу G виду 3,4 також є шляхом між вершинами 3 та 4 у G. Розглянемо іншу послідовність вершин даного орграфу: 1,2,5,3,2. Вона не є шляхом у G, оскільки не кожні дві сусідні вершини цієї послідовності утворюють дугу. Дійсно, вершини 2 та 5 – сусідні у даній послідовності, але (2,5) не є дугою у орграфі G. Прикладом тривіального шляху у орграфі G є послідовність 4. Приклади циклічних шляхів у орграфі G: 3,4,5,3, а також 2,3,4,5,2.

Як видно з наведених прикладів, дві вершини орграфу можуть сполучатися кількома різними шляхами. Зокрема, вершини 3 та 4 з’єднані шляхом 3,4,5,3,4 та шляхом 3,4.

Нехай G=(V,E) – орграф. За кожним нетривіальним шляхом виду u₁,u₂,u₃…,u_n-2,u_n-1,u_n у орграфі G визначається послідовність дуг виду (u₁,u₂),(u₂,u₃),…,(u_n-2,u_n-1),(u_n-1,u_n), у якій кожні дві сусідні дуги суміжні. Наприклад, за шляхом a,b,c,d у орграфі ({a,b,c,d},{(a,b),(a,d),(b,b),(b,c), (c,d)}) визначається послідовність суміжних дуг виду (a,b),(b,c),(c,d).

Шлях u₁,…,u_n між вершинами u та v орграфу G називається орієнтованим ланцюгом (орланцюгом) між u та v, якщо у послідовності дуг, що визначається даним шляхом, усі дуги попарно різні. Шлях u₁,…,u_n у орграфі G називається орієнтованим ланцюгом (орланцюгом), якщо у послідовності дуг, що визначається даним шляхом, усі дуги попарно різні. Орланцюг u₁,…,u_n називається орієнтованим циклом, якщо u₁=u_n й n>1. Орланцюг u₁,…,u_n між вершинами u та v орграфу G називається простим, якщо усі його вершини, крім, можливо, першої та останньої, попарно різні. Орланцюг u₁,…,u_n у орграфі G називається простим, якщо усі його вершини, крім, можливо, першої та останньої, попарно різні. Простий орланцюг u₁,…,u_n називається простим орієнтованим циклом (контуром), якщо u₁=u_n й n>1. Орграф без циклів назвемо ациклічним.

Наприклад, у орграфі G=({1,2,3,4,5,6},{(1,2),(2,3),(3,4),(4,5),(5,3), (3,6)}) шлях 1,2,3,4,5,3,6 є орланцюгом між вершинами 1 та 6. Для перевірки побудуємо послідовність дуг, що визначається цим шляхом. Маємо: (1,2),(2,3),(3,4),(4,5),(5,3),(3,6). Бачимо, що у цій послідовності усі дуги попарно різні. Даний орланцюг не є орієнтованим циклом, оскільки перша та остання вершини у ньому різні. Не є він також й простим орланцюгом (отже, не є контуром), адже вершина 3 входить у нього двічі, хоча не є одночасно першою та останньою. Розглянемо інший шлях між вершинами 1 та 6 у орграфі G, а саме 1,2,3,6. Він є простим орланцюгом, оскільки, по-перше, у послідовності дуг (1,2),(2,3),(3,6), що визначається цим шляхом, усі дуги попарно різні (тобто даний шлях є орланцюгом), а, по-друге, вершини не повторюються. Шлях 3,4,5,3 у орграфі G є орієнтованим циклом, а також контуром. Перевіримо це. Спочатку покажемо, що даний шлях є орієнтованим циклом. Побудуємо послідовність дуг, що визначається цим шляхом: (3,4),(4,5),(5,3). Бачимо, що усі дуги у послідовності попарно різні. Отже, даний шлях є орланцюгом. Оскільки перша та остання вершини цього орланцюга однакові, він є орієнтованим циклом. Усі його вершини, крім першої та останньої, як бачимо, попарно різні. Таким чином, даний орієнтований цикл є простим. Оскільки орграф G має контур, то він не є ациклічним. Прикладом ациклічного орграфу є орграф ({1,2,3},{(3,1),(2,1)}).

Орграф G=(V,E) називається сильно зв’язним, якщо між будь-якими його вершинами u та v існує шлях. Наприклад, орграф G=({1,2,3,4},{(1,2), (2,3),(3,4),(4,1)}) є сильно зв’язним; це випливає з того, що G має контур 1,2,3,4,1, який містить усі вершини орграфу G. Орграф G₁=({1,2,3},{(1,2),(2,3)}) не є сильно зв’язним, адже у ньому не існує шляху між вершинами 3 та 1.

Напівшляхом у орграфі G=(V,E) між вершинами u та v орграфу G називається послідовність вершин даного орграфу виду u₁,…,u_n, де u₁=u, u_n=v, (u_i,u_i+1)ÎE або (u_i+1,u_i)ÎE, 1£i£n-1, nÎN⁺.

Наприклад, у орграфі G=({1,2,3,4,5},{(1,2),(2,3),(3,4),(4,5),(5,2),(5,3)}) напівшляхом між вершинами 3 та 1 є послідовність вершин 3,4,5,2,1. Дійсно, (3,4),(4,5),(5,2) – дуги орграфу G; остання пара сусідніх вершин у даній послідовності, тобто (2,1), не є дугою орграфу G, але (1,2) являється дугою G. Цей напівшлях не є шляхом у орграфі G між вершинами 3 та 1, оскільки 2 та 1 – сусідні вершини у цій послідовності, але (2,1) не є дугою орграфу G.

Зауважимо, що коли у орграфі G існує напівшлях u₁,…,u_k між вершинами u та v, то у G існує напівшлях між вершинами v та u. Таким напівшляхом, зокрема, є послідовність u_k,…,u₁.

Напівланцюгом між вершинами u та v орграфу G називається такий напівшлях між u та v, що у послідовності дуг, що визначається даним напівшляхом, усі дуги попарно різні. Напівконтуром у орграфі G називається напівланцюг із щонайменше двома вершинами, у якому усі вершини, крім першої та останньої, попарно різні. Наприклад, у орграфі G=({1,2,3,4},{(1,2),(2,3),(3,4),(4,2)}) існує напівланцюг 1,2,3,4 між вершинами 1 та 4, а також існує напівконтур 2,3,4,2.

Орграф G називається слабо зв’язним, якщо між будь-якими його вершинами u та v існує напівшлях. Наприклад, орграф G=({1,2,3,4},{(1,2),(1,3),(1,4)}) слабо зв’язний, адже між вершиною 1 та будь-якою іншою вершиною G існує шлях (отже, й напівшлях), між вершинами 2 та 3 є напівшлях 2,1,3, між вершинами 2 та 4 – напівшлях 2,1,4, між вершинами 3 та 4 – напівшлях 3,1,4. Орграф G₁=({1,2,3,4},{(1,2),(3,4)}) не є слабо зв’язним, адже у ньому не існує напівшляху між вершинами 2 та 3.

Зауважимо, що будь-який сильно зв’язний орграф є слабо зв’язним, але не навпаки, тобто існують слабо зв’язні орграфи, що не є сильно зв’язними. Наприклад, орграф ({1,2},{(1,2)}) слабо зв’язний, але не є сильно зв’язним, оскільки у ньому не існує шляху між вершинами 2 та 1.

Орграф, що не є слабо зв’язним, називається незв’язним.