Спеціальні види графів

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

3.7.1. Двочасткові графи. Вирізною ознакою графів цього виду є те, що вершини графа поділені на дві підмножини таким чином, що кожне ребро (дуга) з’єднує вершини різних підмножин. З такими графами ми зустрічалися при вивченні відношень на множинах (п. 1.3).

Означення 3.49. Граф (орграф) G = (V,E) називається двочастковим, якщо V=V₁ÈV₂, V₁ÇV₂=Æ, і кожне ребро (дуга) із E з’єднує одну вершину з підмножині V₁ з одною або декількома вершинами в підмножині V₂.

Пара підмножин (V₁,V₂) являє собою двочасткове розбиття множини V.

Означення 3.50. Двочастковий граф (орграф) G = (V,E) з розбиттям (V₁,V₂) множини V називається повним двочастковим графом (орграфом), якщо кожна вершина v_i ÎV₁ з’єднана з кожною вершиною v_jÎV₂ одним ребром (дугою).

Повний двочастковий граф (орграф) з r і s вершинами позначається K_rs. При r = s повний двочастковий граф (орграф) називається збалансованим.

На рис. 3.13 наведені приклади діаграм двочасткових графів: а) неповного, б) повного K_2,5, в) збалансованого K_2,2.

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

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

Наслідком вилучення із графа G ребер розрізаючої множини є створення нового графа H=G₁ÈG₂, який складається з графів G₁ = (V₁,E₁), V₁ÌV, E₁ÌE і G₂ = (V₂,E₂), V₂ÌV, E₂ÌE, які є підграфами графа G з різними множинами вершин і ребер: V₁ÇV₂=Æ, E₁ÇE₂=Æ.

Очевидно, в багатореберному графі G = (V,E) буває можливим виділити декілька розрізаючих множин.

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

Означення 3.52. Граф, одно з ребер (дуг) якого є мостом, називається роздільним.

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

Означення 3.53. Граф (орграф), який не містить жодної точки зчленування, називається нероздільним.

На рис. 3.14 показані приклади: а) графа з виділеним розрізом, б) графа з мостом, що з’єднує вершини v і w, в) графа рис.3.14,б без вилученого моста.

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

3.7.3. Мережі. Важливе значення в практичному застосуванні теорії графів має поняття мережі.

Означення 3.54. Реберно зважений орграф G_n,m=(V,E) називається мережею, якщо він:

а) містить дві і тільки дві вершини v₁ і v_n, перша з яких (початкова) є витоком (deg⁺(v₁)=0), а лруга (кінцева) — стоком (deg^-(v_n)=0);

б) вага кожній з дуг зазначається невід’ємним числом, яке називається пропускною здатністю дуги (позначення с(е_і), e_iÎЕ, i= ).

На рис. 3.15 наведений приклад діаграми мережі.

Засадним поняттям теорії мереж є поток. Множину дуг, що входять у проміжну вершину v_k, k=2, …, n–1, позначимо , а множину дуг, що виходять з цієї вершини, позначимо . На множині дуг Е, що складають мережу, визначимо функцію f(e_i), яка відображує множину Е в множину цілих невід’ємних чисел, що відповідають таким умовам:

а) f(е_i)≤с(е_i), тобто ці числа не перевищують пропускну здатність дуг мережі;

б) для кожної вершини, за виключенням витоку та стоку, виконується рівність:

.

Означення 3.55. Функція f(e_i), що визначається умовами а) і б), називається потоком в дузі.

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

Означення 3.56. Функція F_k= , k=2, …, n-1, що визначається умовами а) і б), називається потоком в вершині.

Потоки у вершинах v₁ і v_n, що є витоком та стоком, відповідно дорівнюють: F₁= ; F_n= .

Мережа завжди має принаймі один розріз. Множину дуг, що входать у розріз та виходять із нього, позначимо E_t.

Означення 3.57. Функція F_t= називається потоком в мережі.

Очевидно, має місце рівність F_t=F₁=F_n.

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

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

3.7.4. Дерева. Дерева є найбільш простим і розповсюдженим класом графів. Структурною особливістю дерев є відсутність циклів. Вихідним поняттям цього класу графів є ліс.

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

Компонентами зв’язності (підграфами) ліса є дерева.

Означення 3.59. Деревом називається скінченний зв’язний граф без циклів, який містить не менше двох вершин.

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

Для будь-якого дерева має місце рівність m=n–1. Дійсно, ця рівність справедлива для однореберного дерева (рис. 3.16,а). Додавання ребра до вершини збільшуе m і n на одиницю зі збереженням рівності m=n–1. Нарощуваючи число ребер приєднанням їх до будь-яких вершин з появою нових вісячих вершин, ми будемо одержувати нові дерева зі збереженням рівності m=n–1.

Крім властивостей зв'язності, ациклічності та співвідношення m=n–1, деревам привласні ще такі очевидні властивості: кожне ребро є ребром розрізу (мостом); будь-які дві вершини з’єднані одним і тільки одним простим відкритим ланцюгом; при додаванні ребра між двома несуміжними вершинами граф перестає бути деревом у зв’язку з появою в ньому одного циклу; після вилучення будь-якого ребра граф перестає бути деревом у зв’язку з втратою зв’язності; дерево є планарним графом, оскільки його діаграму можна зобразити на площині без перетину ребер.

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

Означення 3.60. Вершина ордерева називається коренем, якщо існує орієнтований шлях з цієї вершини у кожну з інших вершин.

Означення 3.61. Вершини ордерева, напівстепені виходу яких дорівнюють нулю (вісячі вершини), називаються його листями.

Ордерева відрізняються від неорієнтваних дерев тим, що не всі впорядковані пари вершин пов’язані оршляхами.

Оскільки дерева (ордерева) є графами (орграфами), то до них в рівній мірі відносяться всі теоретичні положення за пп. 3.1 – 3.6. Зокрема, компонентами зв’язності (підграфами) дерева є піддерева.

На рис.3.17 показано діаграму орграфа, який є ордеревом. Коренем цього дерева є вершина v₀, а листями є вершини v₂, v₃, v₆, v₇, v₈.

Для більшої наочності структуру діаграми ордерева зображають як ранжовану по рівнях вершин (рис.3.17).

Означення 3.62. Якщо в ордереві існує шлях з вершини v_i у вершину v_k, то вершина v_i називається предком вершини v_k, а вершина v_k – нащадком вершини v_i.

В ордереві рис. 3.17 v₀ – предок вершин v₁, v₂, …, v₈, а отанні є нащадками вершини v₀.

Означення 3.63. Якщо в ордереві вершини v_i та v_k суміжні, причому дуга вихо­дить з вершини v_i, то вершина v_i називаеться прямим предком вершини v_k, а вершина v_k – прямим нащадком вершини v_i.

В ордереві рис. 3.17 v₀ - прямий предок вершин v₁ і v₄, а вершини v₁ і v₄ - прямі нащадки вершини v₀.

Наприклад, якщо дерево рис. 3.17 є генеалогічним деревом роду, то вершина v₀ – це засновник роду, вершини v₁ і v₄ – його діти, v₂, v₃, v₅, v₆ – онуки, v₇, v₈ – правнуки.

Вершина ордерева, яка не має прямих нащадків, є листком. В ордереві рис. 3.17 вершини v₂,v₃,v₆,v₇,v₈ є листями.

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

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

Означення 3.64. Турніром називається орграф, у якому будь-які дві вершини з'єднані рівно одною дугою.

Приклад турніру показаний на рис. 3.18. Його можна інтерпретувати, припустимо, так: ко­манда z завдала поразки команді w, але програла команді v, і т.д.