Что такое орграф когда для представления данных используются орграфы приведите примеры

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

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

Содержание

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

Формально, орграф 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 … Справочник технического переводчика

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

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

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

Источник

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

Источник

Лекция 6. п.7. Графы. Орграфы

7.1. Графы и орграфы. Основные понятия.

Теория графов – это раздел дискретной математики, имеющий многочисленные приложения в различных областях экономики, социологии, техники, программирования. Почему же графам оказывается столь явное предпочтение? Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи. Это связано еще с тем, что графы в наглядной графической интерпретации передают изучаемый объект. Например, в теории множеств мы с помощью орграфа показывали бинарные отношения.

Теория графов многократно «открывалась» разными авторами при решении различных прикладных задач.

Но полноправно можно сказать, что теория графов берет начало с решения задачи о кенигсбергских мостах в 1736 году знаменитым математиком Леонардом Эйлером (: родился в Швейцарии, жил и работал в России).

Задача о кенигсбергских мостах.

Жителям Кенигсберга нравилось гулять по дорожкам, которые включали семь мостов, соединяющие два острова и берега реки Преголя. Люди интересовались, могут ли они, начав путь с одного участка суши, обойти все мосты, посетив каждый лишь однажды, и вернуться в точку начала пути, не переплывая реку. Для решения задачи Эйлер построил граф: участки суши изобразил вершинами, а дорожки через мосты – как ребра. Сначала им была сформулирована и доказана теорема. И опираясь на эту теорему, Эйлер показал, что такого маршрута нельзя построить. Далее мы рассмотрим, как Эйлер решил эту задача.

Кроме задачи о кенигсбергских мостах, классическими задачами стали: задача о трех домах и трех колодцах; задача о четырех красках.

Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена (показано, что решения не существует) К Куратовским (1896 – 1979) в 1930 году.

Задача о четырех красках. Разбиение плоскости на непересекающиеся области называется картой. Области карты называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две области не были закрашены одним цветом. С конца XIX века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которая базировалось на переборе вариантов с помощью компьютера.

Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они все сделали правильно.

Теперь познакомимся с основными понятиями из теории графов.

Определение 7.1. Графом G=G(V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множество E двухэлементных подмножеств множества V. Множество E называется множеством ребер.

Вершины vi и vj множества V называются соединенными ребром (vi, vj) или инцидентны к ребру (vi, vj), если (vi, vj)ÎE. Если (vi, vj) – ребро, тогда вершины vi и vj называются концами ребра (vi, vj). Ребро (vi, vj) называется также инцидентным к вершинам vi и vj. Две вершины называются смежными, если они инцидентны к одному ребру. Два ребра называются смежными, если они инцидентны к общей вершине.

.

Определение 7.2. Ориентированный граф или орграф G=G(V, E) – это такой граф, который состоит из множества V вершин и множества E упорядоченных пар элементов из V. Элемент множества E называется дугой. Если (vi, vj)ÎE, то vi называется начальной вершиной дуги (vi, vj), а vj называется конечной вершиной.

Геометрическое представление графов следующее:

1) вершина графа – точка в пространстве (на плоскости);

2) ребро неориентированного графа – отрезок;

3) дуга ориентированного графа – направленный отрезок.

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

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

Аналогично, как и для графа, для орграфа вводится понятие ориентированный подграф.

Определение 7.4. Граф называется полным, если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через Kn.

Определение 7.5. Граф G=G(V, E) называется двудольным, если V можно представить как объединение непересекающихся множеств, скажем V=AÈB, так что каждое ребро имеет вид (vi, vj), где viÎA и vjÎB. Двудольный граф называется полным двудольным графом Km, n, если A содержит m вершин, B содержит n вершин и для каждого viÎA, vjÎB имеем (vi, vj)ÎE.

Пример 7.2. Построить полный двудольный граф K2,4 и полный граф K4.

Таким образом, путь длины k имеет k ребер. По причине избыточности обозна-чений в этом определении для графа в общем случае путь будет обозначаться через v0v1v2…vk.

Если все ребра различны, то путь называется цепью. Если все вершины различны (а значит, и ребра), то путь называется простой цепью. Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим.

Аналогично, как и для графа, для орграфа вводятся понятия ориентированный путь, ориентированный цикл.

Определение 7.7. Граф G=G(V, E) называется связным, если имеется цепь между любыми двумя его различными вершинами.

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

G1), если f: V®V1 и f: E® E1 представляют собой взаимно однозначные соответствия. Если f:G®G1 – изоморфизм, то G и G1 называются изоморфными.

Пример 7.4. Дан неориентированный помеченный граф G1(V1; E1). Построить изоморфные ему графы.

Теорема 7.1. Изоморфизм графов есть отношение эквивалентности.

Доказательство. Действительно, изоморфизм обладает всеми необходимыми свойствами отношения эквивалентности:

G, где требуемая биекция есть тождественная функция;

[Симметричность.] Если G1

[Транзитивность.] Если G1

Определение 7.10. Степенью вершины v для неориентированного графа, обозначается d(v), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей.

Определение 7.11. Полустепенью исхода вершины v для орграфа называется количество дуг, для которых v является начальной вершиной, обозначается . Полустепенью захода вершины v называется количество дуг, для которых v является конечной вершиной, обозначается . Если , то вершина v называется истоком. Если , то вершина v называется стоком.

Теорема 7.2. (Теорема Эйлера) Сумма степеней вершин графа равна удвоенному количеству ребер:

.

Доказательство. При подсчете суммы степеней вершин каждое ребро учитывается два раза: для одного конца ребра и для другого.

Следствие 1. Число вершин нечетной степени четно.

Доказательство. По теореме Эйлера сумма степеней всех вершин – четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, следовательно, их четное число.

Следствие 2. Сумма полустепеней вершин орграфа равна удвоенному количеству дуг:

.

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

Пример 7.5. Определить степени вершин данного графа.

Пример 7.6. Определить полустепени исхода и захода данного орграфа.

Источник