Page 44 - 2577

k вершин. Граф називають повним, якщо будь – які дві його вершини з’єднані ребром.
Повний граф з n вершинами позначається через K . На рис. 3.8 показані графи К 2, К 3, К 4 і К 4.
n

K4
K2 K3 K5

Рисунок 3.8 – Повні графи
Граф G називають дводольним, якщо V можна подати як об’єднання множин А і В, що
A
B
не перетинаються: V  A  B , так що кожне ребро має вид (a, b), де a і b . Таким
чином, кожне ребро зв’язує вершину із А з вершиною із В, але ніякі дві вершини із А або із В
не є зв’язаними. Дводольний граф називається повним дводольним графом K , якщо А
m,n
вміщує m, а В – n вершин і для кожного a і b маємо  ba,  E . Таким чином, для
B
A
кожного a і b є ребро, яке зв’язує a і b. На рис 3.9 наведені графи, що мають К 1,2,
A
B
К 2,3, К 2,2 і К 3,2.

A A A A

B B B B

К 1,2 К 2,3 К 2,2 К 3,3

Рисунок 3.9 – Дводольні графи

Граф, який складається із множини вершин V і множини Е упорядкованих пар
елементів із V називається орієнтованим графом або орграфом. Ребра такого графа
називають дугами. Якщо  ba,  E , то а – початкова, а b – кінцева вершини. Відмітимо,
що поняття орграфа допускає наявність петель, чого не було у випадку простих графів. Це
пояснюються тим, що орграф допускає відношення між елементами, а простий граф
визначений як множина вершин і ребер, а в множині два однакових елементи вважаються
одним елементом.
Якщо а – початкова, а b – кінцева вершини орграфа G(V,E), то вершини a і b
інцидентні ребру (a,b); вершина а суміжна до вершини b, і, навпаки, вершина b також
суміжна до вершини а.
Степеню виходу вершини v називається кількість ребер, для яких v є початковою
вершиною, позначається outdeg( v ). Степеню входу вершини v називається кількість ребер,
 
 
для яких v є кінцевою вершиною і позначається indeg v . Якщо indeg v =0, то v
називається джерелом. Якщо outdeg(v )=0, то вершина v називається стоком.
Орграф, який має більше ніж одне ребро із
однієї вершини в іншу, називають орієнтованим
мультиграфом.
Орграф G V, E  називається орієнтованим
підграфом орграфа G(V,E), він позначається як


G V ,  E  G V, E , якщо V  V і E  E .

Рисунок 3.10 – Орграф, в якому
є джерело і стік

41