что такое орграф в информатике

Ориентированный граф

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

Содержание

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

Формально, орграф D=(V, E) есть множество E упорядоченных пар вершин .

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

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

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

Связность

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

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

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

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

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

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

Конденсацией орграфа 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 … Справочник технического переводчика

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

Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность непустого множества вершин и множества пар… … Википедия

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

Граф зависимостей — В математике, информатике и цифровой электронике, граф зависимостей представляет собой ориентированный граф, отражающий зависимости нескольких объектов друг к другу. По графу зависимостей можно определить порядок вычислений или его недостатки,… … Википедия

Источник

Теория Графов. Часть 1 Введение и классификация графов

«Графы являются одним из объединяющих понятий информатики – абстрактное представление, которое описывает организацию транспортных систем, взаимодействие между людьми и телекоммуникационные сети. То, что с помощью одного формального представления можно смоделировать так много различных структур, является источником огромной силы для образованного программиста». Стивен С. Скиена

Введение

Сначала под землей города Москвы ничего не было. Потом была построена первая станция метро, а затем и вторая и третья. Образовалось множество станций метро. На карту было занесено множество точек. Позже между станциями стали прокладывать пути линии. И соединилась станция метро А со станцией метро Б. Все остальные станции также стали соединятся друг с другом и на карте появилось множество линий. В итоге мы имеем Московский метрополитен очень красивый, я там был проверял.

Схема Московского метро

Посмотрите какая красота. У нас имеется множество точек (которые называются вершинами или узлами), а также множество линий (называемые рёбрами или дугами). Обозначим множество вершин буквой V от английского vertex−вершина и множество рёбер обозначим E от английского edge−ребро. Граф в формулах именуют буквой G. Все вершины обязательно должны быть идентифицированы.

Отмечу, что число вершин обозначается буквой n:

Число рёбер обозначается буквой m:

Таким образом граф задается и обозначается парой V,E:

Также определение графа рассказывается в этой статье на Хабре (https://habr.com/ru/post/65367/)

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

Разберем определение графа подробней. Может ли в G быть пустым множество E? Да без проблем! Такой граф будет называться нулевым, а вершины в нем будут называться изолированными.

Нулевой граф

Только вот множество V вершины пустым быть не может. Ведь множество E рёбра задается парой неупорядоченных вершин множества V. Две вершины образующие ребро, называются концами этого ребра.

Множество E задается парой неупорядоченных вершин множества V.

Пример: Пусть множество V = <1,2,3,4,5>. Тогда множество E =

Граф будет выглядеть следующим образом:

Висячей вершиной называется вершина которая соединена только с одной соседней вершиной. В нашем случаи висячей вершиной будет вершина 5, так как она соединена только с вершиной 1.

Степень записывают, как:

Максимальная степень, то есть какое количество степеней вообще присутствуют в графе обозначаются, как:

Формула суммы степеней для G = V,E выглядит так:

То есть сумма степеней всех вершин v графа равна удвоенному количеству его рёбер E. Считаем количество степеней в нашем примере. От этого никуда не денешься. Я насчитал 12. А теперь считаем, сколько у нас рёбер. Их 6! Умножаем на 2 и получаем 12. Совпадение? Не думаю!

А давайте представим наш граф в другом виде, но с сохранением данных пар. G теперь имеет следующий вид:

Заметьте я не изменил пары между собой. Вершина 4 также соединяется с вершиной 3, а у вершины 1 степень также осталась 4. Так почему граф имеет совершенно другой вид и законно ли это?

Классификации графов

Первым признаком классификации является отсутствие или наличие ориентации у ребер.

Ребро является неориентированным если у него нет понятия начала или конца. То есть оба его конца равноправны. Такой граф называется неориентированным, обыкновенным или неографом.

Неориентированный граф

Ориентированное ребро обозначается стрелкой. И указывает ориентацию от вершины к вершине. То есть данный граф имеет начало и конец. И называется он ориентированным или орграфом.

Ориентированный граф

Также существует граф со смешанными ребрами. Это когда в графе присутствуют, как ориентированные рёбра, так и неориентированные.

Смешанный граф

Вторым признаком является отсутствие или наличие кратных ребер.

Мультиграф

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

Заключение

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

Источник

Содержание урока

Ориентированный граф

Ориентированный граф

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

Ориентированный граф (орграф) — это граф, в котором каждое ребро имеет направление.

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

На схеме на рис. 3.30 всего две дороги с двусторонним движением, по остальным можно ехать только в одну сторону.

Рёбра в орграфе называют дугами. Дуга, в отличие от ребра, имеет начало и конец.

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

Следующая страница Количество путей

Cкачать материалы урока

Источник

Орграф

В математической теории графов и информатике граф — это совокупность объектов со связями между ними.

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

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

Содержание

Определения

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

V (а значит и E ) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.

Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф

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

Смешанный граф

Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.

Прочие связанные определения

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

Ориентированным путём в орграфе называют конечную последовательность вершин v_i , для которой все пары (v_i,v_{i + 1}) являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:

Бинарное отношение на множестве вершин графа, заданное как «существует путь из u в v », является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа G. Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов

Ребро графа называется мостом, если его удаление увеличивает число компонент.

Дополнительные характеристики графов

Способы представления графа в информатике

Матрица смежности

Матрица смежности — таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).

Недостатком являются требования к памяти — очевидно, квадрат количества вершин.

Матрица инцидентности

Данный способ является самым ёмким (размер пропорционален | E | | V | ) и неудобным для хранения, но облегчает нахождение циклов в графе.

Список рёбер

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

Обобщение понятия графа

Простой граф является одномерным симплициальным комплексом.

Более абстрактно, граф можно задать как тройку , где V и E — некоторые множества (вершин и рёбер, соотв.), а — функция инцидентности (или инцидентор), сопоставляющая каждому ребру (упорядоченную или неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого понятия являются:

Под данное выше определение не подходят некоторые другие обобщения:

Литература

См. также

Ссылки

Популярные программы для визуализации графов

Источник

Орграфы и 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).

Источник