ми і q ребрами називається (p; q) - графом. Граф (1,0) - називається тривіальним. [6]
Якщо елементом множини V може бути пара однакових елементів u , то такий елемент множини V називається петлею. [3]
Типи графів:
В· мультіграф, в ньому не допускаються петлі, але пари вершин можуть з'єднуватися більш ніж одним ребром, ці ребра називаються кратними (рис.1).
В· псевдографом, в ньому допускаються петлі і кратні ребра (рис.2).
В
Рис.1 Рис.2
В· Орієнтований граф, або орграф, складається з кінцевого непорожньої множини V вершин і заданого набору Х упорядкованих пар різних вершин. Елементи з Х називаються орієнтованими ребрами, або дугами. Немає петель і кратних дуг (рис. 3). br/>
В В В В В В В
Рис.3
В
Рис.4
br/>
В· Спрямований граф - це орграф, що не має симетричних пар орієнтованих ребер (рис. 4).
В· Помічені графи (або перенумеровані), якщо його вершини відрізняються одна від іншої будь-якими позначками. В якості позначок зазвичай використовуються букви або цілі числа. [6]
Ступенем вершини v i у графі G називається число ребер, інцідентних v i , позначається d i . [6] Для орграфа вводяться поняття ступеня входу і виходу. Ступенем виходу вершини v називається кількість ребер, для яких v є початковою вершиною, позначається outdeg ( v ). Ступенем входу вершини v називається кількість ребер, для яких v є кінцевою вершиною, позначається indeg ( v ). Якщо indeg ( v ) = 0, то вершина v називається джерелом. Якщо outdeg ( v ) = 0, то вершина v називається стоком. [1]
В
Маршрути і зв'язність
Граф G / (U /, V /) називається подграфом графа G (U, V), якщо U / ГЊU і V / ГЊV. Позначення: G / ГЊG. p> Якщо V / = V, то G / називається остовне подграфом G. [3]
Маршрутом у графі G називається чергується послідовність вершин і ребер ця послідовність починається і закінчується вершиною, і кожне ребро послідовності інцидентне двом вершинам, одна з яких безпосередньо передує йому, а інша безпосередньо слід за ним. Зазначений маршрут з'єднує вершини v 0 і v n і його можна позначити v 0 v 1 v 2 ... v n (наявність ребер мається на увазі). Ця послідовність іноді називається ( v 0 - v n
