ОРИЕНТИРОВАННЫЙ ГРАФ (ОРГРАФ) G есть пара G=(V,E), где V - к–нечное множество вершин, а E - п–оизвольное подмножество V*V – множество ориентированных (направленных) ребер (дуг). Предложения.
а) Ориентированный граф G=(V,E) определяет отношение на V.
б) Пусть V - к–нечное множество. Тогда отношение на V определяет ориентированный граф, у которого множество вершин - V–
Доказательство.
а) Как и в случае неориентированных графов, определим R(E) следующим образом: vR(E)w тогда и только тогда, когда (v,w) in E. Очевидно, что R(E) - о–ношение.
б) Если R - о–ношение на V, то ориентированный граф G=(V,E), определяемый R, имеет множество дуг Е, где (v,w) in E тогда и только тогда, когда vRw.
Направление дуги обозначают порядком в V*V; если (v,w) in E, то говорят, что дуга выходит из v и входит в w. На диаграмме в этом случае для указания направления используют стрелки.
Матрицу смежности A для орграфа определим следующим образом:
Aij=1, если дуга (vi,vj) in E, 0 в противном случае.
### Пусть G=({v1, v2, v3},{(v1,v2), (v2,v3), (v3,v1)}). Тогда матрица смежности и изображение орграфа имеют вид:
\ | /-------->+
1 1 1 +<---------v1<--------+ |
0 0 1 | | /
1 0 0 v2------------------->v3
Поскольку реберное отношение для орграфа не обязательно нерефлексивно или симметрично, то вообще говоря, не обязательно, чтобы А=А^T или Aii=0. Дуги типа (v,v) называют ПЕТЛЕЙ.
СТЕПЕНЬ ВЕРШИНЫ v in V, может быть записана в виде суммы
delta(v)=delta+(v)+delta-(v),
где delta+(v) - чис–о дуг, выходящих из v (полустепень исхода);
delta-(v) - чис–о дуг, входящих в v (полустепень захода);
Для орграфов справедливо утверждение:
Сумма полустепеней исхода всех вершин орграфа равна сумме полустепеней захода и равна числу его дуг:
SUM delta+(v)=SUM delta-(v)=|E|.
v in V v in V
Определим матрицу инцидентности I орграфа. Пусть G=(V,E) - орг–аф, |V|=n, |E|=m. Если перенумеровать некоторым образом дуги, то матрица инцидентности - бин–рная n*m матрица вида:
| 1, если вершина vk является началом дуги el;
Ikl=| -1, если вершина vk является концом дуги el;
| 0, если вершина vk и дуга el не инцидентны.
Орграфы изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга последовательностью одинаковых перестановок строк и столбцов.
Пусть G –помеченный граф порядка n, VG={1, 2, ... , n}. Определим бинарную n×n- матрицу A=A(G), положив
1, {i, k } ∈ EG
Aik = .
0, {i, k } ∉ EG
A(G) называется матрицей смежности графа G. Это симметричная матрица с нулями на диагонали. Число единиц в строке равно степени соответствующей вершины. Очевидно, что соответствие G→A(G) определяет биекцию множества помеченных графов порядка n на множество бинарных симметричных n×n- матриц с нулевой диагональю. Аналогично определяются матрицы смежности A мульти- и псевдографов: Aik равно числу ребер, соединяющих вершины i и k (при этом петля означает два ребра). Также определяется матрица смежности A(G) ориентированного графа.
Очевидно, что если A(G) – матрица смежности орграфа G порядка n, то
n n
∑ Aik = d + ( i ) , ∑A i =1
k =1 ik = d − (i ),
I.е. число единиц в i-й строке матрицы A(G) равно полустепени исхода i-й вершины, а число единиц в k-м столбце равно полустепени захода k-й вершины.
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одинаковыми перестановками строк и столбцов.
Теорема верна также для мультиграфов, псевдографов и орграфов.
Пусть G – (n, m)-граф, VG={1, 2, ... , n} EG={e1, e2, ... , em}. Определим бинарную n×m- матрицу I=I(G) условиями
1, если вершина k и ребро ei инцидентны I ki =
0, если вершина k и ребро ei не инцидентны
Матрица I называется матрицей инцидентности графа G. В каждом её столбце ровно две единицы, равных столбцов нет. Как и выше, соответствие G→I(G) является биекцией множества помеченных (n, m)-графов с занумерованными ребрами на множество n×m- матриц, удовлетворяющих описанным условиям.
Матрица инцидентности I для орграфа:
1 − если вершина k является началом дуги
I ki = −1 − если вершина k является концом дуги
0 − если вершины k и i не смежны
Теорема. Графы изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга произвольными перестановками строк и столбцов.
Теорема верна также для мультиграфов, псевдографов и орграфов.
Свойства матриц смежности и инцидентности:
1) Сумма элементов матрицы A(G), где G=(V, E) – мультиграф, V={v1, v2, ..., vn}, по i-й строке (или по i-му столбцу) равна δ(vi).
2) Сумма элементов матрицы A(G), где G=(V, E) – ориентированный псевдограф,
V={v1, v2, ... , vn}, по i-й строке и по i-му столбцу соответственно равны δ+(vi), δ– (vi).
3) Пусть G – ориентированный мультиграф с непустым множеством дуг. Тогда:
а) сумма строк матрицы I(G) является нулевой строкой;
б) любая строка матрицы I(G) является линейной комбинацией остальных строк;
в) ранг матрицы I(G) не превосходит n–1;
г) для любого контура матрицы G сумма столбцов матрицы I(G), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.
4) Пусть G – мультиграф с непустым множеством ребер. Тогда при покоординатном сложении по модулю 2:
а) сумма строк матрицы I(G) является нулевой строкой;
б) любая строка матрицы I(G) является суммой остальных строк;
в) для любого цикла в G сумма столбцов матрицы I(G), соответствующих ребрам, входящим в этот цикл, равна нулевому столбцу.
Для того чтобы подсчитать все варианты, которые могли бы здесь возникнуть, заметим, что можно рассматривать или граф G, или ориентированный граф (орграф) D, в котором разделяются. Сеть N можно определить как граф или орграф, рассматриваемый вместе с функцией, приписывающей каждому ребру некоторое положительное действительное число. Если G — произвольный планарный (р, орграф и р^З, то а^Зр — 6. Ориентированный граф, или орграф, D состоит из конечного непустого множества V вершин и заданного набора X упорядоченных пар различных вершин.
Направленный граф — это орграф, не имеющий симметричных пар ориентированных ребер.
Матрица смежностей помеченного орграфа D определяется аналогично: Л =Л (D)—||а^-||, где а^=1, если дуга v{V] принадлежит D, и ац=0 в противном случае. Из определения матрицы A (D) следует, что матрицу смежностей данного графа можно также рассматривать как матрицу смежностей симметрического орграфа. Если D — орграф с линейными подграфами DI, » = 1, 2,. Любому графу G поставим в соответствие орграф D, в котором вершины vt и V) соединены дугами vtVj и VjVt только в том случае, если эти вершины смежны в G. Компоненты линейного подграфа графа G, являющиеся отдельными ребрами, взаимно однозначно соответствуют 2-контурам линейного подграфа орграфа D, а компоненты, являющиеся простыми циклами графа G, соответствуют двум простым контурам орграфа D.
Далее, каждой дуге орграфа D (F), скажем идущей из вершины fi в вершину fj, приписывается цвет, связанный с элементом /71// группы F. Чтобы построить граф G, группа (автоморфизмов) Г (G) которого изоморфна F, он заменяет каждую дугу fifj орграфа D (F). Для р^г 4 не существует таких орграфов D, чтоГ(/})==А^. Для орграфов нужно использовать редуцированную упорядоченную парную группу Sp2. По определению группа 5р2 действует на множестве V^ как индуцированная группой Sp: каждая подстановка а из Sp индуцирует такую подстановку а' из 5р2', что а' (i, /) = (ai, а/) для (г,/) из 1^4 Применяя теорему Пойа к цикловому индексу группы S[P2\ получаем многочлен dp(x), в котором коэффициент при х9 равен числу орграфов с q ориентированными ребрами.
Свойства орграфов, которые отличают их от графов. Сформулировав принцип ориентированной двойственности, мы перейдем к изучению матриц, связанных с орграфами, и затем приведем аналог матричной теоремы о деревьях в графах.
Орграфы и соединимость
Орграф D состоит из конечного множества V вершин и набора упорядоченных пар различных вершин. В орграфе (ориентированным) маршрутом называется чередующаяся последовательность вершин и дуг v9, хг, uit. Средние вершины совпадают; основной маршрут содержит все вершины. Поскольку граф может быть либо связным, либо нет, то существуют три различных способа определения связности орграфа и каждый из них имеет свою собственную идиосинкразию). Ясно, что каждый сильный орграф — односторонний, а каждый односторонний орграф — слабый, но обратные утверждения не верны.
Орграф называется несвязным, если он даже не слабый. Заметим, что тривиальный орграф, состоящий только из одной вершины, является (по определению) сильным, поскольку в нем нет двух различных вершин. Сформулируем теперь необходимые и достаточные условия, обеспечивающие орграфу одну из этих трех типов соединимости. Орграф сильный тогда и только тогда, когда он имеет остовный замкнутый маршрут; односторонний тогда и только тогда, когда он имеет основной маршрут; слабый тогда и только тогда, когда он имеет основной полупуть. Для орграфа определены три типа компонент (связности). Сильной компонентой орграфа называется максимальный сильны л подграф, односторонней компонентой — максимальный односторонний подграф и слабой компонентой — максимальный слабый подграф. Это, в частности, демонстрирует способ построения по сильным компонентам орграфа D нового орграфа, который хотя и проще D, но сохраняет некоторые его структурные свойства. Конденсацией l) D* орграфа D называется орграф, множеством вершин которого служит множество {Si, 52,. , Sn} всех сильных компонент орграфа D, а дуга идет из St к Sj, если в орграфе D имеется по крайней мере одна дуга, идущая из некоторой вершины компоненты St к вершине компоненты Sj.
Орграф и его конденсация
Из максимальности сильных компонент следует, что в конденсации D* любого орграфа D нет контуров. Очевидно, что конденсация каждого сильного орграфа есть тривиальный орграф. Можно показать, что орграф является односторонним тогда и только тогда, когда его конденсация имеет единственный остовный путь.