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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Орієнтований граф з трьома дугами і трьома вершинами.

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

Основні поняття[ред.ред. код]

Формально, орграф D = (V, E) є множина E впорядкованих пар вершин v\in V.

Дуга {u, v} інцидентна до вершин u і v. При цьому говорять, що u — початкова вершина дуги, а v — кінцева вершина.

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

Орієнтований повний граф називається турніром.

Зв'язність[ред.ред. код]

Маршрутом орграфа називають послідовність вершин і дуг, виду v_0 \{v_0, v_1\} v_1 \{v_1, v_2\} v_2 ... v_n (вершини можуть повторюватися). Довжина маршруту — кількість дуг у ньому.

Шлях — маршрут орграфа без повторюваних дуг, простий шлях — без повторюваних вершин. Якщо існує шлях з однієї вершини в іншу, то друга вершина досяжна з першої.

Контур — замкнений шлях.

Для напівмаршруту знімається обмеження на напрямок дуг, аналогічно визначаються напівшлях і напівконтур.

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

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

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

Додаткові визначення[ред.ред. код]

Орієнтований ациклічний граф або «гамак» є безконтурним орграфом.

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

Зображення і властивості всіх орграфів з трьома вузлами[ред.ред. код]

Легенда:С — слабкий, ОС — односторонній, СС — сильний,Н — орієнтований граф,Г — гамак, Т — турніром.

0 дуг 1 дуга 2 дуги 3 дуги 4 дуги 5 дуг 6 дуг
3node digraph0.svg
порожній, Н, Г
3node digraph1.svg
Н, Г
3node digraph21.svg
3node digraph31.svg
ОС
3node digraph41.svg
CC
3node digraph5.svg
CC
3node digraph6.svg
повний, CC
3node digraph22.svg
ОС, Н, Г
3node digraph32.svg
CC, Н, Т
3node digraph42.svg
CC
3node digraph23.svg
C, Н, Г
3node digraph33.svg
ОС, Н, Г, Т
3node digraph43.svg
ОС
3node digraph24.svg
C, Н, Г
3node digraph34.svg
ОС
3node digraph44.svg
ОС

Застосування орграфів[ред.ред. код]

Орграф широко застосовуються в програмуванні як спосіб опису систем зі складними зв'язками. Наприклад, одна з основних структур, що використовуються при розробці компіляторів і взагалі для подання комп'ютерних програм — граф потоків даних.

Бінарні відношення[ред.ред. код]

орграф відносини подільності

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

Примітки[ред.ред. код]

Література[ред.ред. код]

  • Харари Ф. Теория графов — М.: УРСС, 2003. — 300 с. — ISBN 5-354-00301-6.
  • Оре, Ойстин Теория графов — М.: УРСС, 2008. — 352 с. — ISBN 978-5-397-00044-4.
  • Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман Компиляторы: принципы, технологии и инструменты, 2 издание = Compilers: Principles, Techniques, and Tools — 2 изд. — М.: «Вильямс», 2008. — ISBN 978-5-8459-1349-4.

Дивіться також[ред.ред. код]