4. . Способы задания графов

1) Латинская матрица.

Направление дуг задается порядком букв в их названии.

Таблица 1

	A	B	C	D	E
A		A B	A C
B	B A			B D
C	C A				C E
D		D B
E				E D	E E

Рис. 13 .

Если граф не ориентированный, то в латинской матрице просто штрихуют соответствующие клетки в таблице.

2) Матрица смежности вершин.

A B C D E

Это квадратная матрица P порядка n, где n – число вершин. Её стоки и столбцы соответствуют вершинам графа. Элементы P_ij матрице смежности равны числу дуг, идущих из i вершины в j. Если орграф не содержит параллельных дуг то матрица является бинарной и состоит только из 0 и 1.

В случае неориентированного графа ему вместе с ребрами x_i,x_j принадлежит ребро x_j,x_i, поэтому матрица смежности вершин будет симметрической.

Теорема. Графы изоморфны тогда и только тогда, кода их матрице смежности вершин получаются друг из друга одновременными перестановками строк и столбцов.

Следствие. Ранги матриц смежности вершин изоморфных графов равны.

Матрица смежности вершин однозначно определяет структуру графа.

Определение. Рангом графа называется ранг его матрицы смежности вершин. Обозначение: rang G.

3) Матрица смежности дуг.

Это квадратная матрица Q порядка m, где m – число дуг. Элементы q_ij этой матрицы равны 1, если дуга u_i непосредственно предшествует дуге u_j и равны 0 в остальных случаях. Для неориентированного графа элемент q_ij=1 если u_i и u_j смежны, и q_ij=0 в остальных случаях.

Это матрица смежности дуг для предыдущего графа без петли u_9.

4) Матрица инциденций.

Это прямоугольная матрица R размерностью n x m, где m – число дуг, а n – число вершин. Элементы r_ij этой матрицы равны 1, если дуга u_i исходит из i-ой вершины; -1, если дуга u_j входит в i вершину; 0, если дуга не инцидентна i-ой вершине. В случае неориентированного графа элементами матрицы будут элементы 1 и 0, т.е. r_ij= 1, если вершина x_i инцидентна ребру u_j.

r_ij= 0, если вершина x_i не инцидентна ребру u_j.

Строки матрицы инциденций называется векторами инциденций графа G.

Матрица инциденций также однозначно определяет структуру графа.

5) Матрица весов - это матрица Ω=||_ij||, где _ij – вес ребра, соединяющего вершины x_i и x_j. Веса несуществующих ребер полагают равными 0 или в зависимости от приложений. Матрица весов является простым обобщение матрицы смежности вершин.

6) Матрица Кирхгофа графа G – квадратная матрица B_n×n=||b_ij||, n=Card S,

b_ij=-1, если вершины x_i и x_j смежны;

b_ij=0, если вершины x_i и x_j не смежны и i не равно j;

b_ij= P(x_i), i=j.

Свойства матрицы Кирхгофа.

1. Суммы элементов в каждой строке и каждом столбце матрице B равны 0.

2. Алгебраические дополнения всех элементов матрицы B равны между собой.

7) Матрицы связности и достижимости.

Пусть P(G) – матрица смежности вершин графа G=(S_n, U), а D=E+P+P²+…+Pⁿ. Введём матрицу C=||с_ij|| по правилу:

с_ij=1, если d_ij не равно 0,

с_ij=0, если d_ij равно 0.

Матрица C называется матрицей связности, если G – неорграф, и матрицей достижимости, если G –орграф.

В матрице C содержатся информация о существовании связей между различными элементами графа G посредством маршрутов. Это значит, что в графе G тогда и только тогда существует маршрут из вершины x_i в вершину x_j, когда c_ij=1.

8) Матрица контрдостижимости.

Определяется следующим образом:

L_n×n=||l_ij||.

l_ij= 1, если вершина x_i достижима из вершины x_j,

l_ij= 0, если вершина x_i не достижима из вершины x_j.

Теорема. L=C^T.

Матрицы C и L используются для нахождения сильных компонент графа. Пусть F=C*L, где операция * означает поэлементное произведение матриц C и L: f_ij=сijl_ij. Элемент f_ij матрицы F равен 1 тогда и только тогда, когда вершины x_i и x_j взаимно достижимы. Т.о., сильная компонента орграфа, содержащая вершину x_i, состоит из элементов x_j, для которых f_ij=1.

П ример.

Рис. 14

;

По матрице F легко определить состав вершин трёх подграфов, образующих сильно связные компоненты исходного графа.

X₂

X₃

X₆

X₅

X₄

G₂

G₃

Рис. 15