Використання теорії графів для структурного аналізу складних систем

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

Види графів. Якщо визначена множина елементів V, то граф G=G(V) вважається визначеним, коли деяке сімейство сполучень елементів пбо пар виду Е=(a,b), де a,b належить V, вказує, які елементи є зв’язні. У відповідності з геометричною інтерпретацією пара Е=(a,b) – ребро, а елементи a i b - кінцеві точки ребра, або вершини. Якщо початок розташування вершини не має значення, то Е – неорієнтовне ребро, а якщо це важливо, то Е – орієнтовне ребро, дуга, причому a – початкова вершина, b – кінцева.

В теорії графів використовують також таку термінологію: ребро Е інцидентно вершинам a,b; вершини a,b інцидентні ребру Е.

Граф, складений виключно з орієнтованих ребер – орієнтований. Відповідно: неорієнтовані та змішані графи. Неорієнтований граф можна перетворити в орієнтований заміною кожного ребра Е парою ребер з тими ж кінцями, але протилежної орієнтації (процес подвоєння).

Граф кінцевий, коли число ребер кінцеве, та нескінченний - у протилежному випадку.

Граф, який складається лише з ізольованої вершини – нуль-граф, а граф, ребрами якого є різні пари двох різних вершин a, b і з V – повний граф.

В орієнованому повному графі є пари ребер по одному в кожному напрямку, які з’єднують будь-які дві різні вершини (a,b).

Способи формалізованого задання графів.

Графічне представлення – найбільш наочне, але не достатнє, його не можна використовувати при роботі на ЕОМ.

Матричне представлення. Можуть бути різні форми. Для неорієнтованого графа матриця суміжності є симетричною. В матриці суміжності вершин для орієнованого графа:

А=||a_ij||

Елементи визначаються так:

          1, якщо з вершини і можна перейти в вершину j

a_ij =

          0 - в протилежному випадку.

Вид матриці суміжності орієнованих графів суттєво залежить від принципу нумерації вершин.

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

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

Частинний граф та підграф. Граф Н називається частинним графом графа G, якщо його множина вершин V(H) є в множині вершин V графа G і всі ребра графа Н є ребрами графа G.

Ланцюг – послідовність ребер Е₀, Е₁... Е_n коли кожне ребро Е_n-1 дотикається одним з кінців з ребром Е_n.

Шлях – послідовність дуг, коли кінець кожної попередньої співпадає з початком наступної, наприклад (1,3)(3,5)(5,1). Це поняття також використовується для орієнованих графів.

Цикл - кінцевий ланцюг, який розпочинається і закінчується в одній вершині, наприклад (1,2,4,1).

Контур – кінцевий шлях, для якого початкова вершина першої дуги співпадає з кінцевою вершиною останньої дуги шляху: послідовність дуг (1,3), (3,5),(5,1) – контур.

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