WikiSort.ru - Кино и мультфильмы

ПОИСК ПО САЙТУ | о проекте

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

Основные понятия

Формально, орграф состоит из множества , элементы которого называются вершинами, и множества упорядоченных пар вершин .

Дуга инцидентна вершинам и . При этом говорят, что  — начальная вершина дуги, а  — конечная вершина.

Орграф, полученный из простого графа ориентацией рёбер, называется направленным. В отличие от последнего, в произвольном простом орграфе две вершины могут соединяться двумя разнонаправленными дугами.

Направленный полный граф называется турниром.

Связность

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

Путь есть маршрут в орграфе без повторяющихся дуг, простой путь — без повторяющихся вершин. Если существует путь из одной вершины в другую, то вторая вершина достижима из первой.

Контур есть замкнутый путь.

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

Орграф сильно связный, или просто сильный, если все его вершины взаимно достижимы; односторонне связный, или просто односторонний, если для любых двух вершин, по крайней мере, одна достижима из другой; слабо связный, или просто слабый, если при игнорировании направления дуг получается связный (мульти)граф;

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

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

Дополнительные определения

Направленный ациклический граф или гамак есть бесконтурный орграф.

Ориентированный граф, полученный из заданного сменой направления рёбер на противоположное, называется обратным.

Изображение и свойства всех орграфов с тремя узлами

Легенда: С — слабый, ОС — односторонний, СС — сильный, Н — является направленным графом, Г — является гамаком (ациклический), Т — является турниром

0 дуг1 дуга2 дуги3 дуги4 дуги5 дуг6 дуг
пустой, Н, Г
Н, Г
ОС
CC
CC
полный, CC
ОС, Н, Г
CC, Н, Т
CC
C, Н, Г
ОС, Н, Г, Т
ОС
C, Н, Г
ОС
ОС

Применение орграфов

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

Бинарные отношения

орграф отношения делимости

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

Примечания

    Литература

    Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

    Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

    Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




    Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

    Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

    2019-2024
    WikiSort.ru - проект по пересортировке и дополнению контента Википедии