Топ питань
Часова шкала
Чат
Перспективи

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

З Вікіпедії, вільної енциклопедії

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

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

Thumb
Орієнтований граф з трьома дугами і трьома вершинами.

Основні поняття

Узагальнити
Перспектива

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

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

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

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

Зв'язність

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

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

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

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

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

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

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

Додаткові визначення

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

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

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

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

Більше інформації порожній, Н, Г, Н, Г ...
Remove ads

Застосування орграфів

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

Бінарні відношення

Thumb
Орграф відношення подільності

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

Remove ads

Див. також

Примітки

Література

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads