3. Елементи теорії графів

При викладі попереднього матеріалу вже були використані моделі у вигляді графів. Поряд з теоретико-множинним описом моделей систем подання у вигляді графів є одним з найпоширеніших.

Граф Г – геометрична фігура, побудована на множині вершин V = {v₁, v₂, … v_m} і ребер R = {r₁, r₂, … r_n}:

Г = (V, R). (3.1)

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

а) б)

Рис. 3.1

Приклади використання графів для моделювання:

1. Неорієнтовані графи описують (моделюють) дороги між населеними пунктами А, B, C і D (див. мал. 3.1, а).

2. Орграф описує односпрямовані канали передачі інформації (див. мал. 3.1, б).

Дуга r_i, пов'язана зі злом v_j, називається інцидентною цьому вузлу, причому, якщо заходить – позитивно інцидентна, якщо виходить – негативно інцидентна.

Два вузли v_k і v_i суміжні, якщо їм інцидентна одна дуга. Аналогічно, дві дуги суміжні, якщо вони інцидентні одному вузлу, причому, якщо одна виходить, а інша заходить - послідовно суміжні, у противному випадку - паралельно суміжні.

Дуга, що виходить із вузла й у неї ж заходить, називається петлею.

Вузол, з якого дуги тільки виходять, називається джерелом, а в який тільки заходять – стоком. Вузли стік і джерело - висячі вузли.

Дві системи S₁ і S₂ із заданими на них відносинами R₁ і R₂ ізоморфні, якщо:

1) їхні структурні елементи попарно взаємно однозначно відповідають один одному;

2) підмножина елементів А₁ системи S₁ зв'язано відношенням R₁, тоді відповідна підмножина (див. п. 1) А₂ системи S₂ зв'язано відношенням R₂.

Існує гомоморфізм – спрощена модель вихідної системи, тобто не виконуються які-небудь із вищевказаних умов.

Зв'язку в системі можна зображувати подвійно:

1) елементи – це вершини, а зв'язку – дуги (верховий граф),

2) елементи – дуги, а зв'язку – вузли (реберний або сигнальний граф).

Структури графів можна представити як графічно, так і структурними матрицями. Відомі три види структурних матриць, ізоморфних графічної моделі графа: матриці суміжності, інцидентності (інциденції) і структури зв'язків.

Матриця суміжності – квадратна матриця А = {a_ij}, , де m – число вузлів, тобто А_mxm, для якої

Число одиниць у матриці А дорівнює числу дуг n.

Ця матриця має цікаву властивість: якщо звести матрицю А в k-ю ступінь, то кожний елемент матриці А^k буде дорівнює числу шляхів з вузла v_i у вузол v_j довжиною в k дуг.

Шлях у графі - це послідовність послідовно суміжних дуг, орієнтованих в одному напрямку.

Приклад 3.1.

Як видно (див. мал. 3.2), через дві (k = 2) суміжні дуги можна потрапити: з вершини 1 у вершину 4, з 2 в 1, з 2 в 3, з 3 в 4, з 4 в 1 і з 4 в 2.

Таким чином, можна алгоритмічно визначити, чи існує шлях з v_i в v_j довжиною в k дуг. Очевидно, що якщо число вузлів m, максимальний ступінь k, у яку потрібно звести А для визначення самого довгого шляху, дорівнює (m - 1).

Матриця інцидентності – у загальному випадку прямокутна матриця В = {b_ij}, , , де m – число вершин, n – число ребер. Для орграфов:

Для неорієнтованих:

Д

№№ вершин

ля приклада 3.1 матриця інцидентності має вигляд:



Матриця структури зв'язків С = {c_ij} встановлює стосунки між дугами:

С = В^ТВ,

С – симетрична матриця розміром n x n, тобто С_nxn, для якої

Рис. 3.3

Таким чином, матриця структури зв'язків містить інформацію про взаємну орієнтацію пар дуг графа.

Крім цього, можуть використовуватися структурні матриці, що кодують окремі властивості графів:

- наявність контурів (контур = замкнутий шлях),

- наявність шляхів,

- відносини торкання.

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

Сильнозв’язаним називається граф, у якому будь-який вузол досяжний з будь-якого іншого вузла.

Досяжність – це існування шляхи з вузла v_i у вузол v_j. Наприклад, на мал. 3.3 шлях з вузла 1 у вузол 4 має вигляд:

вузол 1  W₁  вузол 2  W₂  вузол 3  W₄  вузол 4.

Може виявитися, що не всі вузли досяжні з інших вузлів. У цьому випадку може бути виділений підграф Г₁, тобто сукупність, підмножина вузлів, для якого умова сильної зв’язності виконується. Наприклад, граф Г (див. мал. 3.4) не сильнозв’язний, тому що у вузол 1 з вузлів 2, 3 і 4 немає шляхів. Сильнозв’язний компонент Г₁ для графа Г складається з вузлів 2, 3 і 4 з відповідними дугами W₂ – W₅.

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

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

Структура найпростішої системи керування описується графом (див. мал. 3.5), де W₁ можна інтерпретувати як модель об'єкта керування, а W₂ – модель керуючого пристрою. Вузли 1 - керування U, 2 і 4 можна інтерпретувати як вихідну величину об'єкта у; 3 (ε) - помилка регулювання, вузол 5 - завдання х (бажане значення величини у).

Рис. 3.5