Структурні характеристики графів

З деякими структурними характеристиками графів ми вже зустрічалися при уведенні основних понять (п. 3.1). Ці характеристики випливають з означень 3.3 –3.5, 3.11 –3.12, 3.16 –3.21 видів графів. Однак, застосування графів при проектуванні і дослідженні об'єктів і систем потребує також уявлень і про більш складні структурні характеристики графів, зокрема про різноманітні види маршрутів. Уявлення про види маршрутів необхідні для розв’язання проблеми досяжності, тобто можливості переходу по ребрах графа з однієї визначеної вершини в іншу. Задачі аналізу досяжності на графах є складовими комплексних задач проектування і дослідження таких складних технологічних систем, як транспортні мережі, мережі електро-, газо-, водопостачання та ін.

Означення 3.32.Маршрутом в графі називається скінченна послідовність вершин і ребер v_i, e_i, v_k, e_k, …, v_l, e_l, v_m, що починається і закінчується вершинами, причому кожне ребро в цієї послідовності інцидентне вершинам, які примикають до нього зліва і справа.

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

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

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

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

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

Наприклад, у графі рис. 3.11 маршрут v₅, e₉, v₃, e₃, v₂, e₂, v₆ є шляхом. Очевидно, в неорієнтованому графі будь-який маршрут є шляхом. Оскільки шлях є маршрутом, то означення замкненого і відкритого шляхів будуть такими самими, як замкненого і відкритого маршрутів. Наприклад, у графі рис. 3.11 шлях v₅, e₅, v₄, e₄, v₃, e₃, v₂, e₈, v₅ є замкненим, а шлях v₅, e₅, v₄, e₄, v₃, e₃, v₂ – відкритим.

Означення 3.36.Довжиною (або потужністю) шляху називається число ребер (дуг), що в нього входять (позначається d(v_i,v_j).

Означення 3.37.Довжина найкоротшого шляху між парою вершин v_i і v_j називається від­станню між цими вершинами.

Шлях v₅, e₅, v₄, e₄, v₃, e₃, v₂ у графі рис. 3.11 має довжину d(v₅,v₂)=3, а найкоротшим шляхом між вершинами v₅ і v₂ є v₅, e₉, v₃, e₃, v₂ довжиною d(v₅,v₂)=2, тобто відстань між вершинами дорівнює 2.

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

Означення 3.38.Максимальний за довжиною шлях з вершини v_i графа (орграфа) G до всіх інших вершин називається ексцентриситетом цієї вершини (позначення e(v_i)).

Означення 3.39.Максимальний ексцентриситет вершин графа (орграфа) називається його діаметром.

Означення 3.40.Мінімальний ексцентриситет вершин графа (орграфа) називається його радіусом.

Продовжимо огляд різновидів маршрутів.

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

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

Оскільки ланцюги є шляхами, то означення замкненого і відкритого ланцюгу будуть такими самими, як замкненого і відкритого шляху. Наприклад, у графі рис. 3.11 ланцюг v₅, e₅, v₄, e₄, v₃, e₃, v₂, e₈, v₅ є простим замкненим, а шлях v₅, e₅, v₄, e₄, v₃, e₃, v₂ – простим відкритим.

Означення 3.43.Простий змкнений ланцюг називається циклом.

Наприклад, у графі рис. 3.11 ланцюг v₅, e₅, v₄, e₄, v₃, e₃, v₂, e₈, v₅ є циклом.

Цикли в орграфах (орцикли) часто називають контурами (аналогія – контури в електричних колах).

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

Якщо граф (орграф) є зваженим, то будь-який шлях w, що подається послідовністю ребер (дуг), має вагу , де p(e_i,e_j) та P(w) – відповідно ваги ребра (дуги) та шляху.

Базуючись на поняттях маршрута і шляху, розглянемо ще одну структурну характеристику графів, що має назву “зв’язність”.

Означення 3.44.Вершини v_i і v_j в графі (орграфі) G називаються зв'язаними, якщо існує маршрут з вершини v_i в вершину v_j.

Означення 3.45.Граф (орграф) G називається зв’язним, якщо у ньому будь-які дві вершини є зв’язаними.

З очевидністю справедлива наступна теорема.

Теорема 3.3. Для зв’язності графа (орграфа) необхідно і достатньо, щоб у ньому існував маршрут з якої-небудь фіксованої вершини v_i у кожну іншу вершину v_j.

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

Означення 3.47. Орграф називається сильно зв’язним,якщо для будь-якої пари різних вершин v_i та v_j існує принаймі один шлях із v_i в v_j.

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

Очевидно, сильно зв’язні орграфи (графи) одночасно є зв’язними, а зв’язний орграф не завжди є сильно зв’язним.

Означення 3.48. Вершина v_j графа (орграфа) G називається досяжною з вершини v_i, якщо існує принаймі один шлях, що з’єднує v_i з v_j.

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

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

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

Матриця досяжностей графа (орграфа) G_n являє собою n´n матрицю R= , елементи якої визначаються таким чином: r_ij=1, якщо існує принаймі один шлях з вершини v_i в вершину v_j, і r_ij=0, якщо шляху з вершини v_i в вершину v_j не існує. Всі діагональні елементи r_ii в матриці R дорівнюють 1, оскільки кожна вершина завжди досяжна із себе.

Множина вершин графа G, досяжних з вершины v_i, складається з вершин v_j, для яких r_ij=1 в i-му рядку матриці досяжностей R= , побудованої за описаними правилами.

Матриця досяжностей R= може мати деякі модифікації. Зокрема, елементи r_ij можна визначити як такі, що дорівнюють кількості шляхів заданої довжини d(v_i,v_j) із v_i в v_j. Побудовою матриць досяжностей для заданих значень d(v_i,v_j)=1, 2, … можна знайти найкоротший шлях із вершини v_i в вершину v_j (відстань між вершинами v_i і v_j), що може бути необхідним для розв’язання деякої практичної задачі з використанням графової моделі.

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