 |
Матричное представление графов
|
|
|
|
Орграфы и матрицы. Матрицей сложностей A (D) орграфа D называется (рхр)-матрица \\аи\\> У которой ai}=\, если vfl,— дуга орграфа D, и atj~Q в противном случае. Сумма по столбцу легко проверить, что суммы элементов по строкам матрицы A (D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам — полустепеням захода. Как и в случае графов, степени матрицы смежностей. А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую. Есть еще три матрицы, связанные с орграфом D — матрица достижимостей, матрица расстояний и матрица обходов. Матрицу достижимостей орграфа можно использовать для нахождения его сильных компонент. Формула для числа остовных входящих деревьев данного орграфа была найдена BOTTOM и Мейберри, а доказана Таттом. Чтобы сформулировать этот результат, известный как матричная теорема о деревьях для орграфов, введем еще матрицы, связанные с D. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента 1-й строки матрицы Mod равно числу остовных входящих деревьев, у которых вершина vt является стоком. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента j-го столбца матрицы Mid равно числу остовных выходящих деревьев, у которых вершина Vj является источником. Эйлеров контур в орграфе D — это замкнутый остовный маршрут, в котором каждая дуга орграфа D встречается по одному разу. Орграф называется эйлеровым, если в нем есть эйлеров контур. Для графов, можно легко показать, что слабый орграф D эйлеров тогда и только тогда, когда у каждой его вершины полустепень захода равна полустепени исхода. Сформулируем теперь теорему, в которой дается формула для числа эйлеровых контуров в эйлеровых орграфах. Эту теорему можно доказать очень изящно с помощью матричной теоремы о деревьях для орграфов; В эйлеровом орграфе число эйлеровых контуров равно с \\ (d,-—1)! Заметим, что для эйлерова орграфа МоА=М\А и все суммы и по строкам, и по столбцам равны нулю, так что все алгебраические дополнения равны между собой. Первый орграф с тремя вершинами называется транзитивной тройкой, второй — циклической тройкой.
|
|
|
Орграф называется строго слабым, если он слабый и не односторонний; строго односторонним, если он односторонний и не сильный. Пусть С0— класс всех несвязных орграфов, GI— класс всех строго слабых орграфов, С2— класс всех строго односторонних орграфов и Ся— класс всех сильных орграфов. Тогда максимум и минимум числа q дуг среди всех орграфов с р вершинами, относящихся по соединимости к категории С;, i=0, 1, 2, 3,. Орграф, являющийся декартовым произведением DjXZ^ двух орграфов, имеет VjX У2 в качестве множества вершин, и вершина («j, и2) смежна к вершине (уь у2) тогда и только тогда, когда или [ui=0i и u, adj гл2], или \u. Если орграф D относительно соединимости находится в категории С„, то будем писать c(D)=n. Ни один строго слабый орграф не содержит вершину, удаление которой приводит к сильному орграфу.
Реберный орграф L(D) имеет множество всех дуг данного орграфа D в качестве множества вершин, и две его вершины х и у смежны тогда и только тогда, когда дуги х к у порождают маршрут в орграфе D. Выразить число вершин и число дуг орграфа L(D) через соответствующие величины орграфа D. Реберный орграф L (D) слабого орграфа D изоморфен самому орграфу D тогда и только тогда, когда D или D' — функциональный орграф. Если D — несвязный орграф, то утверждение, содержащееся в предыдущем упражнении, не верно. Пусть S и Т — непересекающиеся множества вершин орграфа D, а X (S, Т) — множество всех дуг, идущих из S в Т. Орграф D реберный тогда и только тогда, когда не существует множеств 5 и Т, имеющих по две вершины и таких, что \Х (S,T)|=3. Число эйлеровых путей орграфа D равно числу гамильтоновых контуров реберного орграфа L(D]. Пусть орграф 7\ состоит из одной вершины с двумя ориентированными петлями. Пусть T2=L(T1) — реберный орграф (здесь, если быть более точным, нужно использовать термин «псевдоорграф») орграфа Тг, определенный естественным образом; рекурсивно определяется Tn=L(Tn,l). (Такие орграфы Т„ известны под названием «телетайпных диаграмм».) Тогда число эйлеровых путей в орграфе Т„ равно 22""1-1. Каждый орграф, у которого id (v)^p/2, od (v)^p/2 для любой вершины v, гамильтонов.
|
|
|
Рассмотрим орграфы, у которых для любой вершины и сумма ^d(u, v) расстояний от этой вершины до всех остальных постоянна. Найти среди этих орграфов орграф, не являющийся вершинно-симметрическим. Орграф D, его дополнение D и обратный к нему D' имеют одну и ту же группу (автоморфизмов). Пусть А—матрица смежностей реберного орграфа полного симметрического орграфа.
Два орграфа называются коспектральными, если их матрицы смежностей имеют один и тот же характеристический многочлен. Существуют в точности три различных коспектральных сильных орграфа с четырьмя вершинами.
Орграф, называемый конъюнкцией D=Dl/\D2 двух орграфов Z)j и D2, имеет в качестве множества вершин K=V1XV2, и вершина u=(u1, ы2) смежна к вершине v=(v-L,v2) тогда и только тогда, когда %adj г,^ в орграфе Dl и ы2 adj v.
Матрица смежностей А конъюнкции D=Dl/\D2 есть тензорное произведение матриц смежностей орграфов D1 и D2. Пусть Dl и D2— два орграфа, a d,-— наибольший общий делитель длин всех простых контуров орграфа D,-, t=l,2. Конъюнкция Dlf\D^ является сильным орграфом тогда и только тогда, когда Ог и D2 — сильные орграфы, a d1 и d2 взаимно просты.
Орграф называется примитивным, если какая-нибудь степень его матрицы смежностей целиком состоит из положительных чисел. Орграф примитивен тогда и только тогда, когда длины его простых контуров имеют наибольший общий делитель, равный 1. Пусть D — примитивный орграф. Аналогично для вершин и и v орграфа из и в v. Исключение составляют (3,3)-орграф и (4,6)-орграф. П2, составленной Обершельпом, приведены числа орграфов с р вершинами, Эти числа вычислены с помощью соотношения (15. L(D) реберный орграф орграфа D.
|
|
|
ОРИЕНТИРОВАННЫЙ ГРАФ (ОРГРАФ) 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 = .
, {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 =
, если вершина k и ребро ei не инцидентны
Матрица I называется матрицей инцидентности графа G. В каждом её столбце ровно две единицы, равных столбцов нет. Как и выше, соответствие G→I(G) является биекцией множества помеченных (n, m)-графов с занумерованными ребрами на множество n×m- матриц, удовлетворяющих описанным условиям.
Матрица инцидентности I для орграфа:
1 − если вершина k является началом дуги
I ki = −1 − если вершина k является концом дуги
− если вершины 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 нет контуров. Очевидно, что конденсация каждого сильного орграфа есть тривиальный орграф. Можно показать, что орграф является односторонним тогда и только тогда, когда его конденсация имеет единственный остовный путь.
|
|
|
