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

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

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

Формально, орграф <math>D = (V, E)</math> состоит из множества <math>V</math>, элементы которого называются вершинами, и множества <math>E</math> упорядоченных пар вершин <math>u,v\in V</math>.

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

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

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

Связность

Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг, вида <math>v_0 \{v_0, v_1\} v_1 \{v_1, v_2\} v_2 ... v_n</math> (вершины могут повторяться). Длина маршрута — количество дуг в нём.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Харари Ф. Теория графов. — М.: УРСС, 2003. — 300 с. — ISBN 5-354-00301-6.
• Оре, Ойстин. Теория графов. — М.: УРСС, 2008. — 352 с. — ISBN 978-5-397-00044-4.
• Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструменты, 2 издание = Compilers: Principles, Techniques, and Tools. — 2 изд. — М.: «Вильямс», 2008. — ISBN 978-5-8459-1349-4.

Отрывок, характеризующий Ориентированный граф

– Прикажете чемоданы внести? Постель постелить, чаю прикажете? – спрашивал камердинер.
Пьер не отвечал, потому что ничего не слыхал и не видел. Он задумался еще на прошлой станции и всё продолжал думать о том же – о столь важном, что он не обращал никакого .внимания на то, что происходило вокруг него. Его не только не интересовало то, что он позже или раньше приедет в Петербург, или то, что будет или не будет ему места отдохнуть на этой станции, но всё равно было в сравнении с теми мыслями, которые его занимали теперь, пробудет ли он несколько часов или всю жизнь на этой станции.
Смотритель, смотрительша, камердинер, баба с торжковским шитьем заходили в комнату, предлагая свои услуги. Пьер, не переменяя своего положения задранных ног, смотрел на них через очки, и не понимал, что им может быть нужно и каким образом все они могли жить, не разрешив тех вопросов, которые занимали его. А его занимали всё одни и те же вопросы с самого того дня, как он после дуэли вернулся из Сокольников и провел первую, мучительную, бессонную ночь; только теперь в уединении путешествия, они с особенной силой овладели им. О чем бы он ни начинал думать, он возвращался к одним и тем же вопросам, которых он не мог разрешить, и не мог перестать задавать себе. Как будто в голове его свернулся тот главный винт, на котором держалась вся его жизнь. Винт не входил дальше, не выходил вон, а вертелся, ничего не захватывая, всё на том же нарезе, и нельзя было перестать вертеть его.
Вошел смотритель и униженно стал просить его сиятельство подождать только два часика, после которых он для его сиятельства (что будет, то будет) даст курьерских. Смотритель очевидно врал и хотел только получить с проезжего лишние деньги. «Дурно ли это было или хорошо?», спрашивал себя Пьер. «Для меня хорошо, для другого проезжающего дурно, а для него самого неизбежно, потому что ему есть нечего: он говорил, что его прибил за это офицер. А офицер прибил за то, что ему ехать надо было скорее. А я стрелял в Долохова за то, что я счел себя оскорбленным, а Людовика XVI казнили за то, что его считали преступником, а через год убили тех, кто его казнил, тоже за что то. Что дурно? Что хорошо? Что надо любить, что ненавидеть? Для чего жить, и что такое я? Что такое жизнь, что смерть? Какая сила управляет всем?», спрашивал он себя. И не было ответа ни на один из этих вопросов, кроме одного, не логического ответа, вовсе не на эти вопросы. Ответ этот был: «умрешь – всё кончится. Умрешь и всё узнаешь, или перестанешь спрашивать». Но и умереть было страшно.
Торжковская торговка визгливым голосом предлагала свой товар и в особенности козловые туфли. «У меня сотни рублей, которых мне некуда деть, а она в прорванной шубе стоит и робко смотрит на меня, – думал Пьер. И зачем нужны эти деньги? Точно на один волос могут прибавить ей счастья, спокойствия души, эти деньги? Разве может что нибудь в мире сделать ее и меня менее подверженными злу и смерти? Смерть, которая всё кончит и которая должна притти нынче или завтра – всё равно через мгновение, в сравнении с вечностью». И он опять нажимал на ничего не захватывающий винт, и винт всё так же вертелся на одном и том же месте.
Слуга его подал ему разрезанную до половины книгу романа в письмах m mе Suza. [мадам Сюза.] Он стал читать о страданиях и добродетельной борьбе какой то Аmelie de Mansfeld. [Амалии Мансфельд.] «И зачем она боролась против своего соблазнителя, думал он, – когда она любила его? Не мог Бог вложить в ее душу стремления, противного Его воле. Моя бывшая жена не боролась и, может быть, она была права. Ничего не найдено, опять говорил себе Пьер, ничего не придумано. Знать мы можем только то, что ничего не знаем. И это высшая степень человеческой премудрости».
Всё в нем самом и вокруг него представлялось ему запутанным, бессмысленным и отвратительным. Но в этом самом отвращении ко всему окружающему Пьер находил своего рода раздражающее наслаждение.
– Осмелюсь просить ваше сиятельство потесниться крошечку, вот для них, – сказал смотритель, входя в комнату и вводя за собой другого, остановленного за недостатком лошадей проезжающего. Проезжающий был приземистый, ширококостый, желтый, морщинистый старик с седыми нависшими бровями над блестящими, неопределенного сероватого цвета, глазами.