Основні поняття та означення

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

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

Сукупність об’єктів і відношень між парами об’єктів може бути зображено на площині у вигляді множини точок, яка є образом множини об’єктів, и множини ліній, що з’єднують пари точок, яка є образом множини відношень. Графічний образ сукупності об’єктів і відношень являє собою діаграму графа, яку зазвичай називають графом (якщо не відступати від строгості означень, то не графічний образ, а сама сукупність об’єктів і відношень є графом). Множину точок, що є образом множини об’єктів, называют вершинами графа, а множину відрізків ліній, що є образом множини відношень, - ребрами (або дугами) графа. Таке неформальне подання графа ми вже використовували для задання відношення між множинами (п. 1.3). Базуючись на неформальному уявленні про гра­фи, введемо необхідні формальні означення.

Нехай V - деяка непорожня множина, а V²=V´V - множина всіх двохелементних підмножин множини V (декартов добуток множини V).

Означення 3.1. Графом G=(V,E) називається пара множин (V,E), де EÍV² - підмножина множини V².

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

Означення 3.2. Елементи множини V називаються вершинами графа G=(V,E).

Вершини графа G=(V,E) будемо позначати символами v₁, v₂,…,v_n. В такому разі елементами множини E будуть пари (v_i,v_k) елементів множини V.

Означення 3.3. Якщо елементами множини E графа G=(V,E) є невпорядковані пари (v_i,v_k) елементів множини V, то вони називаються ребрами графа G, а сам граф G називається неорієнтованим.

Означення 3.4. Якщо елементами множини E графа G=(V,E) є впорядковані пари (v_i,v_k) елементів множини V, то вони називаються дугами графа G, а сам граф G називається орієнтованим (орграфом).

Означення 3.5. Якщо серед елементів множини E графа G=(V,E) є впорядковані та невпорядковані пари (v_i,v_k) елементів множини V, то граф G називається змішаним

Ребра (дуги) графа G=(V,E) будемо позначати символами e_i, i=1, …, m, а в розгорнутому вигляді e_i=(v_i,v_k), чим відображається математична сутність ребра (дуги) як елемента множини V² (пари елементів множини V).

Вершини і ребра (дуги) графа називаються його елемен­та­ми. Кількість n вершин графа G називається його порядком і позначається через |V|. Якщо |V| = n, а кількість ребер (дуг) |E| = m, то G називають n,m-графом. Кількості n і m вершин і ребер (дуг) графа та його порядок відносяться до його числових характеристик.

Означення 3.6. Вершини v_i і v_k називаються кінцевими вершинами ребра (дуги) e_i=(v_i,v_k) графа (орграфа) G=(V,E).

Вершини v_i і v_k, орграфа, що з’єднані дугою e_i=(v_i,v_k), називають також початковою і кінцевою відповідно, а саму дугу називають такою, що виходить із вершини v_i і заходить у вершину v_k.

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

Означення 3.7. Граф G=(V,Æ), що не містить жодного ребра (дуги), називається порожнім (порожній граф з n вершинами позначається O_n).

Означення 3.8. Граф, який складається з однієї вершини, називається тривіальним.

Означення 3.9. Граф, що не містить жодної вершини, називається нуль-графом: G=(Æ,Æ).

Означення 3.10. Якщо вершины v_i і v_k з’єднані ребром (дугою), то вони називаються суміжними, а ребро (дуга) e_i=(v_i,v_k) називається інцидентним (інцидентною)до своїх кінцевих вершин v_i і v_k.

Означення 3.11. Вершина v_i графа (орграфа) G=(V,E) називається ізольованою, якщо вона не має жодного інцидентного до неї ребра (дуги).

Означення 3.12. Вершина v_i графа (орграфа) G=(V,E) називається висячою, якщо вона має лише одну суміжню до неї вершину.

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

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

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

Деякі особливі властивості графів відображаються їхними спеціальними назвами.

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

Для орграфа кількість дуг, що виходять з вершины v_i, называєтся напівстепенєм виходу і позначаєтся deg^-(v_i), а кількість дуг, що заходять у вершину v_i, – напівстепенєм заходу і позначаєтся deg⁺(v_i). Очевидно, deg(v_i)=deg^-(v_i)+deg⁺(v_i). (3.1)

Означення 3.15.Вершина орграфа з напівстепенєм заходу deg⁺(v_i)=0 називається витоком, а вершина з напівстепенєм виходу deg^-(v_i)=0 називається стоком.

Лема 3.1 (про рукостискання). Нехай G_n,m=(V,E)– довільний граф. Тоді =2m. (3.2)

Доведення. При підрахуванні суми степенів довільне ребро (дуга) e_i=(v_i,v_k) вносить свій вклад, що дорівнює 1, одночасно в deg(v_i) і deg(v_k), причому петля буде враховуватись двічі.

Наслідок: довільний граф містить парне число вершин непарного степеню. Дійсно, якщо V₀и V₁ – множини вершин відповідно парного та непарного степеню, то + =2m.

Очевидно, що перший доданок парний. Тому і другий доданок парний, оскільки сума (3.2) парна. Так як у другий сумі всі доданки непарні, їх кількість парна. Отже, множина V₁містить парне число вершин.

Означення 3.16. Граф (орграф), у якого будь-які дві вершини суміжні, називається повным.

Повний граф с n вершинами позначается К_n.Очевидно, степінь кожної вершины в графі К_п дорівнює п–1. Тому з леми 3.1 про рукостискання випливає, що кількість ребер (дуг) в К_п дорівнює n(n-1)/2.

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

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

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

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

Петлі у псевдографі можут бути кратними. Псевдограф може містити паралельні та контрпаралельні ребра (дуги).

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

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

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

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

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

Аналізуючи назви видів графів за означеннями 3.3 –3.5, 3.11 –3.12, 3.16 –3.21, неважко помітити, що один і той же граф може бути віднесений до графів різних видів. Тому вид графа визначають за найбільш суттєвою ознакою, в залежності від мети його застосування у конкретній задачі.

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

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