Что такое орграф когда представления данных используются орграфы приведите примеры
Ориентированный граф
Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках (Оре) и просто рёбрами.
Содержание
Основные понятия
Формально, орграф D=(V, E) есть множество E упорядоченных пар вершин 
.
Дуга
Орграф, полученный из простого графа ориентацией ребер, называется направленным. В отличие от последнего, в произвольном простом орграфе две вершины могут соединяться двумя разнонаправленными дугами.
Направленный полный граф называется турниром.
Связность
Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг, вида 
(вершины могут повторяться). Длина маршрута — количество дуг в нем.
Путь есть маршрут в орграфе без повторяющихся дуг, простой путь — без повторяющихся вершин. Если существует путь из одной вершины в другую, то вторая вершина достижима из первой.
Контур есть замкнутый путь.
Для полумаршрута снимается ограничение на направление дуг, аналогично определяются полупуть и полуконтур.
Орграф сильно связный, или просто сильный если все его вершины взаимно достижимы; односторонне связный, или просто односторонний если для любых двух вершин, по крайней мере одна достижима из другой; слабо связный, или просто слабый, если при игнорировании направления дуг получается связный (мульти)граф;
Максимальный сильный подграф называется сильной компонентой; односторонняя компонента и слабая компонента определяются аналогично.
Конденсацией орграфа D называют орграф D*, вершинами которого служат сильные компоненты D, а дуга в D* показывает наличие хотя бы одной дуги между вершинами, входящими в соответствующие компоненты.
Дополнительные определения
Ориентированный граф, полученный из заданного сменой направления ребер на противоположное, называется обратным.
Изображение и свойства всех орграфов с тремя узлами
Легенда: С — слабый, ОС — односторонний, СС — сильный, Н — является направленным графом, Г — является гамаком (ациклический), Т — является турниром
| 0 дуг | 1 дуга | 2 дуги | 3 дуги | 4 дуги | 5 дуг | 6 дуг |
 пустой, Н, Г |  Н, Г |  |  ОС |  CC |  CC |  полный, CC |
|---|---|---|---|---|---|---|
 ОС, Н, Г |  CC, Н, Т |  CC | ||||
 C, Н, Г |  ОС, Н, Г, Т |  ОС | ||||
 C, Н, Г |  ОС |  ОС |
Применение орграфов
Орграфы широко применяются в программировании как способ описания систем со сложными связями. К примеру, одна из основных структур, используемых при разработке компиляторов и вообще для представления компьютерных программ — граф потоков данных.
Бинарные отношения
Бинарное отношение над конечным носителем может быть представлено в виде орграфа. Простым орграфом представимы антирефлексивные отношения, в общем случае требуется орграф с петлями. Если отношение симметрично, то его можно представить неориентированным графом, а если антисимметрично, то направленным графом.
Примечания
Литература
Полезное
Смотреть что такое «Ориентированный граф» в других словарях:
ориентированный граф — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN directed graph … Справочник технического переводчика
ориентированный граф — orientuotasis grafas statusas T sritis automatika atitikmenys: angl. directed graph; oriented graph vok. gerichteter Graph, m; orientierter Graph, m rus. орграф, m; ориентированный граф, m pranc. graphe de fluence, m; graphe directe, m; graphe… … Automatikos terminų žodynas
Двудольный ориентированный граф — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
взвешенный ориентированный граф — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN weighted directed graph … Справочник технического переводчика
ориентированный ациклический граф — Ориентированный граф без циклов, петель, кратных дуг. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом EN DAGdirected acyclic graph … Справочник технического переводчика
Граф алгоритма — Граф алгоритма ориентированный граф, состоящий из вершин, соответствующих операциям алгоритма, и направленных дуг, соответствующих передаче данных (результаты одних операций передаются в качестве аргументов другим операциям) между ними. Не… … Википедия
Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность непустого множества вершин и множества пар… … Википедия
Граф (теория графов) — Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Для… … Википедия
Граф зависимостей — В математике, информатике и цифровой электронике, граф зависимостей представляет собой ориентированный граф, отражающий зависимости нескольких объектов друг к другу. По графу зависимостей можно определить порядок вычислений или его недостатки,… … Википедия
Орграф
В математической теории графов и информатике граф — это совокупность объектов со связями между ними.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа (орграф), в котором вершины — это статьи, а дуги (ориентированные рёбра) — это связи, созданные гиперссылками (см. Тематическая карта).
Содержание
Определения
Теория графов не обладает устоявшейся терминологией. В различных статьях под одними и теми же терминами понимаются разные вещи. Приводимые ниже определения — наиболее часто встречаемые.
V (а значит и E ) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.
Два ребра называются смежными, если они имеют общую концевую вершину.
Два ребра называются кратными, если множества их концевых вершин совпадают.
Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.
Ориентированный граф
Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v 
w ведёт от вершины v к вершине w.
Смешанный граф
Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.
Прочие связанные определения
Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Ориентированным путём в орграфе называют конечную последовательность вершин vi 
, для которой все пары (vi,vi + 1) 
являются (ориентированными) рёбрами.
Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.
Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:
Бинарное отношение на множестве вершин графа, заданное как «существует путь из u в v », является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.
Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа G. Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов
Ребро графа называется мостом, если его удаление увеличивает число компонент.
Дополнительные характеристики графов
Способы представления графа в информатике
Матрица смежности
Матрица смежности — таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).
Недостатком являются требования к памяти — очевидно, квадрат количества вершин.
Матрица инцидентности
Данный способ является самым ёмким (размер пропорционален | E | | V | ) и неудобным для хранения, но облегчает нахождение циклов в графе.
Список рёбер
Список рёбер — это тип представления графа в памяти, подразумевающий, что каждое ребро представляется двумя числами — номерами вершин этого ребра. Список рёбер более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности.
Обобщение понятия графа
Простой граф является одномерным симплициальным комплексом.
Более абстрактно, граф можно задать как тройку 
, где V и E — некоторые множества (вершин и рёбер, соотв.), а 
— функция инцидентности (или инцидентор), сопоставляющая каждому ребру 
(упорядоченную или неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого понятия являются:
Под данное выше определение не подходят некоторые другие обобщения:
Литература
См. также
Ссылки
Популярные программы для визуализации графов
Применение орграфов
Орграфы широко применяются в программировании как способ описания систем со сложными связями. К примеру, одна из основных структур, используемых при разработке компиляторов и вообще для представления компьютерных программ — граф потоков данных.
Бинарное отношение над конечным носителем может быть представлено в виде орграфа. Простым орграфом представимы антирефлексивные отношения, в общем случае требуется орграф с петлями. Если отношение симметрично, то его можно представить неориентированным графом, а орграф отношения делимости. Если антисимметрично, то направленным графом. (В математике бинарным отношением называется любое множество упорядоченных пар).
Сетевые графики
В самих кружках (разделенных на секторы) также содержится информация.
Они указывают на то, что «событие», на которое направлена пунктирная стрелка, может происходить только после свершения события, из которого исходит эта стрелка.
В сетевом графике не должно быть тупиковых участков, каждое событие должно соединяться сплошной или пунктирной стрелкой (или стрелками) с каким-либо предшествующим (одним или несколькими) и последующим (одним или несколькими) событиями.
Нумерация событий производится примерно в той последовательности, в какой они будут происходить. Начальное событие располагается обычно с левой стороны графика, конечное — с правой.
Последовательность стрелок, в которой начало каждой последующей стрелки совпадает с концом предыдущей, называется путем. Путь обозначается в виде последовательности номеров событий.
В сетевом графике между начальным и конечным событиями может быть несколько путей. Путь, имеющий наибольшую продолжительность, называется критическим. Критический путь определяет общую продолжительность работ. Все остальные пути имеют меньшую продолжительность, и поэтому в них выполняемое работы имеют резервы времени.
Критический путь обозначается на сетевом графике утолщенными или двойными линиями (стрелками).
Особое значение при составлении сетевого графика имеют два понятия:
Сети Петри
Сети Петри – инструмент исследования систем. В настоящее время сети Петри применяются в основном в моделировании. Во многих областях исследований явление изучается не непосредственно, а косвенно, через модель. Модель – это представление, как правило, в математических терминах того, что считается наиболее характерным в изучаемом объекте или системе. Манипулируя моделью системы, можно получить новые знания о ней, избегая опасности, дороговизну или неудобства анализа самой реальной системы. Обычно модели имеют математическую основу.
Развитие теории сетей Петри проводилось по двум направлениям. Формальная теория сетей Петри занимается разработкой основных средств, методов и понятий, необходимых для применения сетей Петри. Прикладная теория сетей Петри связана главным образом с применением сетей Петри к моделированию систем, их анализу и получающимся в результате этого глубоким проникновением в моделируемые системы.
Моделирование в сетях Петри осуществляется на событийном уровне. Определяются, какие действия происходят в системе, какие состояние предшествовали этим действиям и какие состояния примет система после выполнения действия. Выполнения событийной модели в сетях Петри описывает поведение системы. Анализ результатов выполнения может сказать о том, в каких состояниях пребывала или не пребывала система, какие состояния в принципе не достижимы. Однако, такой анализ не дает числовых характеристик, определяющих состояние системы. Развитие теории сетей Петри привело к появлению, так называемых, “цветных” сетей Петри. Понятие цветности в них тесно связано с понятиями переменных, типов данных, условий и других конструкций, более приближенных к языкам программирования. Несмотря на некоторые сходства между цветными сетями Петри и программами, они еще не применялись в качестве языка программирования.
Не смотря на описанные выше достоинства сетей Петри, неудобства применения сетей Петри в качестве языка программирования заключены в процессе их выполнения в вычислительной системе. В сетях Петри нет строго понятия процесса, который можно было бы выполнять на указанном процессоре. Нет также однозначной последовательности исполнения сети Петри, так как исходная теория представляет нам язык для описания параллельных процессов.
Наилучшими возможностями описания параллельных систем обладают сети Петри. Они не менее мощные, чем PVM, MPI, SDL и другие, но чтобы их выполнять на процессорах необходимо сделать из описания параллельного распределенное.
Марковский процесс
Ма́рковский проце́сс — случайный процесс, эволюция которого после любого заданного значения временно́го параметра 
не зависит от эволюции, предшествовавшей , при условии, что значение процесса в этот момент фиксировано («будущее» процесса не зависит от «прошлого» при известном «настоящем»; другая трактовка (Вентцель): «будущее» процесса зависит от «прошлого» лишь через «настоящее»).
История
Определяющее марковский процесс свойство принято называть марковским; впервые оно было сформулировано А. А. Марковым который в работах 1907 г. положил начало изучению последовательностей зависимых испытаний и связанных с ними сумм случайных величин. Это направление исследований известно под названием теории цепей Маркова.
Однако уже в работе Л. Башелье можно усмотреть попытку трактовать броуновское движение как марковский процесс, попытку, получившую обоснование после исследований Винера в 1923.
Основы общей теории марковских процессов с непрерывным временем были заложены Колмогоровым.
Орграфы и DAG-графы
Ориентированный граф ( орграф )
Орграф определяется списком узлов и ребер (внизу), где каждое ребро направлено из первой вершины во вторую. На чертежах орграфа для изображения ориенти-рованныхребер используются стрелки (вверху).
Направления ребер в графе можно интерпретировать различными способами. Например, в графе телефонных вызовов ребро может быть направлено от вызывающего абонента к вызываемому. В бухгалтерских транзакциях ребро может представлять собой денежные суммы, товары или информацию, передаваемые из одного места в другое.
Число возможных орграфов поистине огромно. Каждое из возможных V 2 ориентированных ребер (считая и петли) может присутствовать или отсутствовать — таким образом, общее количество разных орграфов равно 
. С увеличением количества вершин это число стремительно возрастает (см. рис. 19.2) уже при небольших значениях V, даже по сравнению с количеством различных неориентированных графов. Как и в случае неориентированных графов, количество изоморфных друг другу графов (вершины одного из изоморфных графов можно переименовать таким образом, чтобы получить другой) намного меньше, однако воспользоваться этим сокращением невозможно, т.к. нам неизвестен эффективный алгоритм выявления изоморфизма графов.
Это небольшое отступление про подсчет графов выделяет несколько моментов, которым мы уделяем особое внимание, когда проводим анализ алгоритмов, и показывает их непосредственное отношение к изучению орграфов. Стоит ли разрабатывать алгоритмы так, чтобы они хорошо работали в худшем случае, если встретить такой орграф практически невозможно? Есть ли смысл выбирать алгоритмы на основе анализа работы в среднем, или все это чисто математические выкрутасы? Если нам нужно получить программную реализацию, которая эффективно работает на реально встречающихся орграфах, то тогда возникает проблема описания таких орграфов. Разработка математических моделей, достаточно точно описывающих реальные орграфы, является еще более трудным делом, чем для неориентированных графов.
19.1. Найдите в интернете пример крупного орграфа — возможно, графа транзакций в какой-то онлайновой системе или орграфа, определяемого ссылками веб-страниц.
19.2. Найдите в интернете пример крупного DAG-графа — возможно, графа определения функций в крупной программной системе или ссылок в каталоге крупной файловой системы.
19.3. Постройте таблицу, аналогичную представленной на рис. 19.2, но без учета графов и орграфов с петлями.
19.4. Каково количество орграфов, содержащих V вершин и E ребер?
19.5. Сколько орграфов соответствует каждому неориентированному графу, содержащему V вершин и E ребер?
19.6. Сколько цифр содержит десятичное число, равное количеству орграфов с V вершинами и E ребрами?
19.7. Начертите неизоморфные орграфы, содержащие три вершины.
19.8. Каково количество различных орграфов, содержащих V вершин и E ребер, если считать орграфы различными только если они не изоморфны.
19.9. Вычислите верхнюю границу процентного отношения орграфов, содержащих 10 вершин, которые могут быть просмотрены каким-либо компьютером в условиях, описанных в тексте, и с учетом того, что во вселенной имеется менее 10 80 электронов, а возраст Вселенной не превышает 10 20 лет.
Глоссарий и правила игры
Определение 19.1. Ориентированный граф (или орграф) — это множество вершин плюс множество ориентированных ребер, которые соединяют упорядоченные пары вершин (при отсутствии одинаковых ребер). Мы говорим, что ребро направлено из первой вершины во вторую вершину.
Как и в случае неориентированных графов, в этом определении исключается наличие одинаковых ребер, но мы будем допускать их в различных приложениях и реализациях, если так будет удобнее. Мы явно разрешаем присутствие петель в орграфах (и обычно допускаем, что такая петля имеется у каждой вершины), поскольку они играют важную роль в фундаментальных алгоритмах.
Определение 19.2. Ориентированный путь (directedpath) в орграфе — это список вершин, в котором имеется (ориентированное) ребро орграфа, соединяющее каждую вершину списка со следующим элементом этого списка. Мы говорим, что вершина t достижима (reachable) из вершины s, если существует ориентированный путь из s в t.
Мы считаем, что каждая вершина достижима сама из себя, и обычно реализуем это свойство, включая в представление орграфов петли.
Для понимания многих алгоритмов, описываемых в данной главе, требуется понимание свойств связности орграфов и влияния этих свойств на базовый процесс перемещения от одной вершины к другой по ребрам графа. Достичь такого понимания для орграфов сложнее, чем для неориентированных графов. Например, иногда с первого взгляда видно, является ли небольшой неориентированный граф связным или содержит ли он циклы, однако в орграфах эти свойства не так очевидны, что демонстрирует типичный пример на рис. 19.3.
Конечно, подобные примеры подчеркивают различия, однако важно помнить, что задача, трудная для человека, может быть, а может и не быть трудной для программы — к примеру, написание класса DFS, предназначенного для поиска циклов в орграфе, не труднее задачи поиска циклов в неориентированном графе. И все же орграфы и неориентированные графы во многом существенно различаются. Например, то, что в каком-то орграфе вершина t достижима из вершины s, ничего не говорит о том, достижима ли s из t. Это различие очевидно, но, как мы увидим, весьма существенно.
Этот небольшой орграф похож на крупную решетчатую сеть, которая была рассмотрена в «Введение» — только теперь на каждой линии сетки имеется ориентированное ребро случайно выбранного направления. Даже для такого графа с небольшим количеством вершин его свойства связности совсем не очевидны. Существует ли ориентированный путь из верхнего левого угла в нижний правый?
В этих представлениях нет различий между неориентированными графами и ориентированными графами с петлей в каждой вершине и двумя ориентированными ребрами для каждого ребра, соединяющего разные вершины неориентированного графа (по одному в каждом направлении). Поэтому алгоритмы, которые мы разработаем в этой главе для орграфов, можно использовать и для обработки неориентированных графов — естественно, при соответствующей интерпретации результатов. Кроме того, в качестве основы для программ обработки орграфов мы будем использовать некоторые программы из «Виды графов и их свойства» : программы 17.7—17.10, реализующие классы DenseGRAPH и SparseMultiGRAPH, строят орграфы, если конструктору передается во втором аргументе значение true.
В представлениях орграфа матрицей смежности и списками смежности каждое ребро фигурирует только один раз, как видно из представления орграфа, показанного на рис. 19.1, в виде матрицы смежности (сверху) и в виде списков смежности (внизу). Оба эти представления содержат в каждой вершине петли, которые обычно используются при обработке орграфов.
Степень захода (indegree) вершины орграфа есть количество ориентированных ребер, которые ведут в эту вершину. Степень выхода (outdegree) вершины орграфа есть количество ориентированных ребер, которые ведут из этой вершины. Никакая вершина орграфа не достижима из вершины со степенью выхода 0 — такая вершина называется сток (sink); вершина со степенью захода 0 называется исток (source), она не достижима ни из какой вершины орграфа. Орграф, в котором разрешены петли, и степень выхода каждой вершины равна 1, называется отображением (map) (функция из множества целых чисел от 0 до V— 1 на это же множество). Используя векторы, индексированные именами вершин, можно подсчитать степени захода и выхода для каждой вершины и найти истоки и стоки, потратив на это линейное время и объем памяти, пропорциональный V (см. упражнение 19.19).
Обращение (reverse) орграфа — это орграф, который получается при изменении направлений всех ребер орграфа на обратные. На рис. 19.5 показано обращение орграфа с рис. 19.1 и его представления. Обращения орграфов используются в алгоритмах тогда, когда нужно знать, откуда исходят ребра, поскольку стандартные представления показывают нам только куда они идут. При обращении орграфа степени выхода и захода меняются местами.
В случае представления матрицей смежности обращение можно вычислить, создав копию матрицы и транспонировав ее (поменяв местами строки и столбцы).
Изменение направлений ребер орграфа на обратные соответствует транспонированию матрицы смежности, но требует перестроения списков смежности (см. рис. 19.1 и рис. 19.4).