Реферат: Орграфы, теория и применение
Орграф называется строго
слабым, если он слабый и не односторонний; строго односторонним, если он
односторонний и не сильный. Пусть С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 = .
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 упорядоченных пар различных вершин.
Страницы: 1, 2, 3, 4, 5, 6 |