Орієнтовані графи

Часто зв'язки між об'єктами характеризуються цілком визначеною орієнтацією. Наприклад, на деяких вулицях допускається тільки односторонній автомобільний рух, у сполучних проводах електричного ланцюга задаються позитивні напрямки струмів, відношення між людьми можуть визначатися підпорядкованістю або старшинством. Орієнтовані зв'язки характеризують перехід системи з одного стана в інше, результати зустрічей між командами в спортивних змаганнях, різні відношення між числами (нерівність, подільність).

Для вказівки напрямку зв'язку між вершинами графа відповідне ребро відзначається стрілкою. Орієнтоване в такий спосіб ребро називають дугою, а граф з орієнтованими ребрами - орієнтованим графом або коротше орграфом (мал 3.1, а).

Якщо пара вершин з'єднується двома або більшим числом дуг, то такі дуги називають рівнобіжними. При цьому дві дуги, однаково спрямовані стосовно даної вершини, називають строго рівнобіжними, а по-різному спрямовані - нестрого рівнобіжними. Ясно, що нестрого рівнобіжні дуги, що відображають орієнтацію зв'язку в обох напрямках, власне кажучи равноцінні неориентированному зв'язку і можуть бути замінені ребром. Після таку заміни в орграфі, прийдемо до змішаного графа, що містить ребра і дуги (мал. 8,б). Навпаки, будь-який неориентирований або змішаний граф можна перетворити в орієнтований заміною кожного ребра парою нестрого рівнобіжних дуг.

Мал. 3.2.Орієнтований (а) і змішаний (б) графи.

Змінивши напрямки всіх дуг орграфа на протилежні, одержуємо орграф, зворотний вихідному. Якщо напрямки дуг орграфа не враховуються і кожна дуга розглядається як неориєнтоване ребро, то він називається співвіднесеним (неориентированным) графом.