Орграфы, теория и применение (стр. 2 из 6)
Формально, орграф D=(V, E) есть множество E упорядоченных пар вершин
.Дуга {u, v} инцидентна вершинам u и v. При этом говорят, что u — начальная вершина дуги, а v — конечная вершина.
Орграф, полученный из простого графа (Простой граф — граф, в котором нет кратных рёбер и петель.) ориентацией ребер называется направленным. В отличие от последнего, в произвольном простом орграфе две вершины могут соединяться двумя разнонаправленными дугами.
Направленный полный граф называется турниром. Полный граф — простой граф, в котором каждая пара различных вершин смежна. Полный граф с n вершинами имеет n(n − 1) / 2 рёбер и обозначается Kn. Является регулярным графом степени n − 1.
Связность
Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг, вида v0{v0,v1}v1{v1,v2}v2…vn (вершины могут повторяться). Длина маршрута — количество дуг в нем.
Путь есть маршрут в орграфе без повторяющихся дуг, простой путь — без повторяющихся вершин. Если существует путь из одной вершины в другую, то вторая вершина достижима из первой.
Контур есть замкнутый путь.
Для полумаршрута снимается ограничение на направление дуг, аналогично определяются полупуть и полуконтур.
Орграф сильно связный, или просто сильный если все его вершины взаимно достижимы; односторонне связный, или просто односторонний если для любых двух вершин, по крайней мере одна достижима из другой; слабо связный, или просто слабый, если при игнорировании направления дуг получается связный (мульти)граф;
Максимальный сильный подграф (Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и все рёбра, инцидентные данному подмножеству. (ср. Суграф-частичный граф исходного графа — граф, содержащий все вершины исходного графа и подмножество его рёбер)) называется сильной компонентой; (Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными компонентами орграфа называются его максимально сильно связные подграфы). Односторонняя компонента и слабая компонента определяются аналогично.
Конденсацией орграфа D называют орграф D*, вершинами которого служат сильные компоненты D, а дуга в D* показывает наличие хотя бы одной дуги между вершинами, входящими в соответствующие компоненты.
Дополнительные определения
Направленный ациклический граф или гамак есть бесконтурный орграф. (Направленный ациклический граф — случай направленного графа, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса)).
Ориентированный граф, полученный из заданного сменой направления ребер на противоположное, называется обратным.
Изображение и свойства всех орграфов с тремя узлами. Легенда: С – слабый, ОС – односторонний, СС – сильный, Н – является направленным графом, Г – является гамаком, Т – является турниром.
| 0 дуг | 1 дуга | 2 дуги | 3 дуги | 4 дуги | 5 дуг | 6 дуг |
 пустой, Н, Г |  Н, Г |  |  ОС |  CC |  CC |  полный, CC |
 ОС, Н, Г |  CC, Н, Т |  CC | ||||
 C, Н, Г |  ОС, Н, Г, Т |  ОС | ||||
 C, Н, Г |  ОС |  ОС |
Применение орграфов
Орграфы широко применяются в программировании как способ описания систем со сложными связями. К примеру, одна из основных структур, используемых при разработке компиляторов и вообще для представления компьютерных программ — граф потоков данных.
Бинарные отношения
Бинарное отношение над конечным носителем может быть представлено в виде орграфа. Простым орграфом представимы антирефлексивные отношения, в общем случае требуется орграф с петлями. Если отношение симметрично, то его можно представить неориентированным графом, а орграф отношения делимости. Если антисимметрично, то направленным графом. (В математике бинарным отношением называется любое множество упорядоченных пар).
Глава 2. ТЕОРИЯ ГРАФОВ
Граф G – совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности. Каждое ребро e из E инцидентно ровно двум вершинам v', v'', которые оно соединяет. При этом вершина v' и ребро e называются инцидентными друг другу, а вершины v' и v'' называются смежными. Часто пишут v', v'' из G и e из G. Если |V(G)|=n, |E(G)|=m, то граф G есть (n,m) граф, где n – порядок графа, m – размер графа.
Определения
Ребро (v',v'') может быть ориентированным и иметь начало (v') и конец (v'') (дуга в орграфе).
Ребро (v,v) называется петлей (концевые вершины совпадают).
Граф, содержащий ориентированные ребра (дуги), называется орграфом.
Граф, не содержащий ориентированные ребра (дуги), называется неографом.
Ребра, инцидентные одной паре вершин, называются параллельными или кратными.
Граф с кратными ребрами называется мультиграфом.
Граф, содержащий петли (и кратные ребра), называется псевдографом.
Конечный граф – число вершин и ребер конечно.
Пустой граф – множество ребер пусто (число вершин может быть произвольным).
Полный граф – граф без петель и кратных ребер, каждая пара вершин соединена ребром. Обозначение для полного графа с n вершинами – Kn.
Граф называется двудольным, если существует такое разбиение множества его вершин на две части, что концы каждого ребра принадлежат разным частям (долям).
Если любые две вершины двудольного графа, входящие в разные доли, смежны, то граф называется полным двудольным . Обозначение для полного двудольного графа с n и m вершинами – Kn,m.
Локальная степень вершины – число ребер ей инцидентных. В неографе сумма степеней всех вершин равна удвоенному числу ребер (лемма о рукопожатиях). Петля дает вклад, равный 2 в степень вершины.
Следствие 1 из леммы о рукопожатиях. Произвольный граф имеет четное число вершин нечетной степени.
Следствие 2 из леммы о рукопожатиях. Число ребер в полном графе n(n-1)/2.
В орграфе две локальных степени вершины v: deg(v)+ и deg(v) – (число ребер с началом и концом в v)
Графы равны, если множества вершин и инцидентных им ребер совпадают.
Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.
Граф называется регулярным (однородным), если степени всех его вершин равны.
Способы задания графов
Матрица инцидентности A. По вертикали указываются вершины, по горизонтали – ребра. Aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро – петля, то aij=2. Список ребер. В первом столбце ребра, во втором вершины им инцидентные. Матрица смежности – квадратная симметричная матрица. По горизонтали и вертикали – все вершины. Dij= число ребер, соединяющее вершины i,j. Матрица Кирхгофа: bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны, bii=deg(i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.
Связность
Отношение вершин графа «существует маршрут, связывающий вершины» является отношением эквивалентности, задающее разбиение графа на компоненты связности. Индекс разбиения – k.
МАРШРУТЫ, ЦЕПИ, ЦИКЛЫ
Чередующаяся последовательность v1, e1, v2, e2, … , en, vn+1 вершин и ребер графа такая, что ei =vivi+1 (i=1, n ), называется маршрутом, соединяющим вершины 1 и vn+1 (или (v1vn+1)-маршрутом). Очевидно, что для задания маршрута в графе достаточно задать последовательность v1, v2, …, vn+1. его вершин, либо последовательность e1, e2,… , en его ребер.