Тема „Графи”

Нехай V – довільна множина, E – деяка сукупність пар вигляду (v_i, v_j) , де v_i, v_j  V. Термін сукупність означає можливість наявності однакових пар.

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

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

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

• вершини v та u суміжні;

• вершини v і u є кінцями ребра e;

• вершини v і u інцидентні ребру e;

• ребро e – інцидентне вершинам v і u.

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

Множина ребер E може бути порожньою. Такий граф називається нуль-графом і позначається . Якщо ж множина вершин V – порожня, то порожньою є також множини E. Такий граф називається порожнім. Різні ребра можуть бути інцидентними одній і тій самій парі вершин (рис. 1), такі ребра називаються кратними.

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

Якщо пари (v, u)  E вважаються впорядкованими, то граф є орієнтованим. Інакше граф називається неорієнтованим. Ребра орієнтованого графа прийнято називати дугами та зображати напрямними відрізками (рис. 2). При зображені орієнтованих графів напрямки ребер позначаються стрілками.

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

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

Скінченний неорієнтований граф без петель і кратних ребер називається звичайним.

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

Задання графа за допомогою матриці інцидентності та списку ребер

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

Нехай v₁, …, v_n – вершини графа G; e₁, …, e_m – його ребра. Відношення інцидентності можна означити матрицею E = ||a_ij||, що має m рядків й n стовпців. Стовпці відповідають вершинам графа, а рядки – його ребрам.

Якщо ребро e_i є інцидентним вершині v_j, то a_ij = 1, в іншому випадку a_ij = 0.

У матриці інцидентності E = ||_ij|| орієнтованого графа G, якщо вершина v_j – початок ребра e_i, то _ij = –1, якщо v_j – кінець e_i, то _ij = 1; якщо e_i – петля, а v_j – інцидентна їй вершина, то _ij = , де  – будь-яке число, відмінне від 1, 0 та –1, в інших випадках _ij = 0.

v₇

v₄

e₁₀

e₉

e₃

v₅

v₆

e₁₁

v₂

v₅

e₁

e₈

e₇

e₄

e₄

e₈

v₄

e₅

v₁

v₆

e₂

e₅

v₃

e₃

e₂

e₆

v₃

e₇

v₂

v₁

e₁

v₇

e₆

Рис. 3 б)

Рис. 3 а)

Наприклад, для графа, зображеного на рис. 3б) таблиця має вигляд

	v1	v2	v3	v4	v5	v6	v7		Ребро	Вершина
e1	–1	1	0	0	0	0	0		e1	v1, v2
e2	–1	0	1	0	0	0	0		e2	v1, v3
e3	0	–1	0	1	0	0	0		e3	v2, v4
e4	0	0	–1	0	1	0	0		e4	v3, v5
e5	0	0	–1	0	0	1	0		e5	v3, v6
e6	0	0	–1	0	0	0	1		e6	v3, v7
e7	0	0	0	0	0	0	2		e7	v7, v7
e8	0	–1	1	0	0	0	0		e8	v2, v3