Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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


Directed.svg

План:


Введення

Directed.svg

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


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

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

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

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

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


1.1. Зв'язність

Маршрутом в Орграф називають чергуються послідовність вершин і дуг, виду v 0 {v 0, v 1} v 1 {v 1, v 2} v 2... v n (Вершини можуть повторюватися). Довжина маршруту - кількість дуг в ньому.

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

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

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

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

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

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


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

Спрямований ациклічний граф або гамак є бесконтурний орграф.

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

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

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

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
ОС

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

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

2.1. Бінарні відносини

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

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


Примітки

Література

Структури даних
Типи Колекція Контейнер
Масиви Асоціативний масив Multimap Безліч Мультімножество Хеш-таблиця
Списки Зв'язний список Черга (Кільцевій буфер, Двусвязний) Стек Список з пропусками
Дерева B-дерево Двійкове дерево пошуку Купа
Графи Орієнтований граф Спрямований ациклічний граф Binary decision diagram Гіперграфа
Список структур даних

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Агентно-орієнтований підхід
Граф
Граф Нулін
Граф Петерсена
Граф, Девід
Граф, Штеффі
Граф Монтенегро
Граф алгоритму
Граф Ессекс
© Усі права захищені
написати до нас
Рейтинг@Mail.ru