зний, або просто сильний якщо всі його вершини взаємно досяжні; односторонньо зв'язний, або просто односторонній якщо для будь-яких двох вершин, принаймні одна досяжна з іншої; слабо зв'язний, або просто слабкий, якщо при ігноруванні напрямки дуг виходить зв'язний (мульти) граф;
Максимальний місцями подграф (Підграф вихідного графа - граф, що містить якесь підмножина вершин даного графа і всі ребра, інцідентние даному підмножині. (Пор. суграфом-частковий граф вихідного графа - граф, що містить всі вершини вихідного графа і підмножина його ребер)) називається сильною компонентою; (Орграф називається сильно зв'язковим (Strongly connected), якщо будь-які дві його вершини сильно пов'язані. Дві вершини s і t будь-якого графа сильно пов'язані, якщо існує орієнтований шлях з s в t і орієнтований шлях з t в s. Сильно зв'язковими компонентами орграфа називаються його максимально сильно зв'язкові підграфи). Одностороння компонента і слабка компонента визначаються аналогічно.
Конденсацією орграфа D називають орграф D *, вершинами якого служать сильні компоненти D, а дуга в D * показує наявність хоча б однієї дуги між вершинами, що входять до відповідні компоненти.
Додаткові визначення
Спрямований ациклічний граф або гамак є бесконтурний орграф. (Направлений ациклічний граф - випадок спрямованого графа, в якому відсутні спрямовані цикли, тобто шляху, що починаються і кінчаються в одній і тій же вершині. Спрямований ациклічний граф є узагальненням дерева (точніше, їх об'єднання - ліси)). p> Орієнтований граф, отриманий з заданого зміною напрямку ребер на протилежне, називається зворотним.
Зображення і властивості всіх орграфов з трьома вузлами. Легенда: З - слабкий, ОС - односторонній, СС - місцями, Н - є спрямованим графом, Г - є гамаком, Т - є турніром.
0 дуг
1 дуга
2 дуги
3 дуги
4 дуги
5 дуг
6 дуг
порожній, Н, Г
Н, Г
ОС
CC
CC
повний, CC
ОС, Н, Г
CC, Н, Т
CC
C, Н, Г
ОС, Н, Г, Т
ОС
C, Н, Г
ОС
ОС
Застосування орграфов
орграфов широко застосовуються в програмуванні як спосіб опису систем зі складними зв'язками. Наприклад, одна з основних структур, які використовуються при розробці компіляторів і взагалі для подання комп'ютерних програм - граф потоків даних.
Бінарні відносини
Бінарне відношення над кінцевим носієм може бути представлено у вигляді орграфа. Простим орграфом представіми антирефлексивне відносини, в загальному випадку потрібно орграф з петлями. Якщо відношення симетрично, то його можна представити неорієнтованим графом, а орграф відносини подільності. Якщо антисиметричного, то спрямованим графом. (У математиці бінарним відношенням називається будь безліч впорядкованих пар).
В
Глава 2. ТЕОРІЯ ГРАФІВ
Граф G - сукупність двох мн...
