Page 72 - 2589

5 ГРАФИ В ТЕОРІЇ СИСТЕМ

5.1 Основні поняття теорії графів

Нехай V – довільна множина, Е – деяка сукупність пар
вигляду (v ,v ). Де ( v , v ) V . Термін сукупність означає
i j i j
можливість наявності однакових пар.
Упорядкована пара D=(V, Е), що складається з множини V та
сукупності Е, називається графом із множиною вершин V і

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

на площині, а ребра (v ,v ) – відрізками (прямолінійними або
i j
криволінійними), які з'єднують крапки v та v . Граф називається

j
i
скінченним, якщо множини його вершин і ребер є скінченними.
Множину вершин графа G позначають V(G), а множину ребер –
Е(G). Кількість вершин графа n(G)=|V(G)|, а кількість ребер
m(G)=|E(G)|

Кількість вершин n(G) графа називають його порядком.
Кількість ребер графа, інцидентних деякій вершині ν,
називається локальним степенем, або просто степенем, вершини ν
і позначається ρ(ν). Якщо е=(ν, w)E(G), то кажуть:

 вершини ν та w суміжні;
 вершини ν та w є кінцями ребра е;

 вершини ν та w – інцидентні ребру е;
 ребро е – інцидентне вершинам ν та w .
Два ребра називаються суміжними, якщо обидва вони є

інцидентними одній вершині.

а) б) в) г) д)

Рисунок 4.1 – Типові приклади неорієнтованих графів

Множина ребер Е може бути порожньою (рис.4.1,а). Такий

граф називається нуль-графом і позначається 0. Якщо ж множина
вершин V – порожня, то порожньою є також множина Е. Такий

72