Главная | Обратная связь

Поняття орієнтованого графу

Орієнтованим графом (орграфом) називається упорядкована пара множин виду (V,E), де V – деяка непорожня множина, EÍV². Множина V називається множиною вершин орграфу, а її елементи – вершинами; множина E називається множиною дуг орграфу, а її елементи – дугами. Кожна дуга орграфу – це упорядкована пара вершин, перший компонент якої називається початком дуги, а другий – кінцем дуги. Дугу орграфу, початком якої є вершина u, а кінцем – вершина v, будемо позначати (u,v). Дуга (u,v) та вершина u (v) називаються інцидентними, а вершини u та v – суміжними. Оскільки, за визначенням, дуга орграфу є упорядкованою парою вершин, то за умови u¹v пари (u,v) та (v,u) є різними дугами. Дуга виду (v,v) називається петлею. Дуги е₁ та е₂ орграфу G називаються суміжними, якщо кінець дуги е₁ збігається з початком дуги е₂.

Наприклад, упорядкована пара множин виду ({1,2,3},{(1,2),(3,2),(3,1), (2,3)}) є орграфом, тому що перша множина пари (тобто {1,2,3}) є не порожньою, а друга – це множина упорядкованих пар, побудованих з елементів першої множини. Дуга (1,2) та вершина 1 інцидентні; також інцидентними є дуга (1,2) та вершина 2, дуга (3,2) та вершина 3, дуга (3,2) та вершина, 2, дуга (3,1) та вершина 3, дуга (3,1) та вершина 1, дуга (2,3) та вершина 2, дуга (2,3) та вершина 3. Суміжними є вершини: 1 та 2, 3 та 2, 3 та 1. Дуги (3,1) та (1,2) суміжні. Також суміжними є дуги (1,2) та (2,3), дуги (3,2) та (2,3), дуги (2,3) та (3,2) й дуги (2,3) та (3,1). Пара множин виду ({1,2,3},{(1,2),(3,2),(3,4)}) не є орграфом, оскільки друга множина (тобто {(1,2),(3,2),(3,4)}) містить пару (3,4), другий компонент якої не є елементом множини {1,2,3}.

Так само, як й неорієнтованим графам, орграфам можна надавати імена.

Напівстепенем виходу вершини v орграфу G (позначається on(v)) називається потужність множини дуг орграфу G, для яких вершина v є початком. Напівстепенем заходу вершини v орграфу G (позначається in(v)) називається потужність множини дуг орграфу G, для яких вершина v є кінцем. Степінь вершини v орграфу G позначається n(v) й визначається таким чином: n(v)=on(v)+in(v).

Розглянемо приклад. Нехай задано орграф G=({1,2,3,4},{(1,2),(1,3), (2,3),(3,1),(3,4)}). Обчислимо степені вершин G. Вершина 1 є початком двох дуг ((1,2) та (1,3)) й кінцем однієї дуги (а саме, дуги (3,1)), отже, on(1)=2, in(1)=1, n(1)=on(1)+in(1)=2+1=3. Аналогічно обчислюємо степені інших вершин: on(2)=1, in(2)=1, n(2)=1+1=2; on(3)=2, in(3)=2, n(3)=2+2=4; on(4)=0 (у орграфі G немає жодної дуги, початком якої є вершина 4), in(4)=1, n(4)=0+1=1.

Означення поняття порожнього (повного, скінченного) орграфу, підграфу орграфу, порядку орграфу аналогічне означенню поняття порожнього (повного, скінченного) графу, підграфу графу, порядку графу. Означення ізоморфних орграфів аналогічне означенню поняття ізоморфних графів.

Твердження 10. Для будь-якого скінченного орграфу G=(V,E) порядку n виконується on(v)= in(v).

Доведення. При обчисленні on(v) кожна дуга враховується рівно один раз, отже, on(v)=|E|. Аналогічно in(v)=|E|. Отже, on(v)= in(v). Твердження доведено.

Наслідок. Сума степенів усіх вершин орграфу порядку n є числом парним.

Доведення. n(v)= (on(v)+in(v))= on(v)+ in(v)=|E|+|E|=2×|E|. Наслідок доведено.