1. Матриці суміжності та інцидентності
Нехай D=(V,X) орієнтований граф, V={v
1
,...,v
n
}, X={x
1
,...,x
m
}.
Матриця суміжності орієнтованого графа D - квадратна матриця
A(D)=[a
ij
] порядку n, де )
( )
î
í
ì
Ï
Î
=
X
v
v
X
v
v
a
j
i
j
i
ij
,
,
0
,
,
1
Матриця інцидентності - матриця B(D)=[b
ij
] порядку n
´m, де
ï
î
ï
í
ì
-
-
-
-
=
,
0
,
,
1
,
,
1
j
i
j
i
j
i
ij
x
на
неінцидент
v
x
дуги
початок
v
x
дуги
кінець
v
b
Матрицею
суміжності неорієнтованого графа
G=(V,X)
називається квадратна симетрична матриця A(G)=[a
ij
] порядку n, де }
{ Для орієнтованого графа
ï
ï
î
ïï
í
ì
÷
ø
ö
ç
è
æ
÷
ø
ö
ç
è
æ
Ï
Î
=
X
j
v
i
v
X
j
v
i
v
ij
a
,
,
0
,
,
1
Матрицею інцидентності графа G називається матриця
A(G)=[a
ij
] порядку n
´m, де
î
í
ì
-
-
=
,
0
,
,
1
j
i
j
i
ij
x
ребру
на
неінцидент
v
x
ребру
інцидентна
v
b
2. Звязність, компоненти зв'язності
Підграфом графа G (орієнтованого графа D) називається граф, всі
вершини і ребра якого містяться серед вершин і ребер графа G (D).
Підграф називається власним, якщо він відмінний від самого графа.
Кажуть, що вершина w орієнтованого графа D (графа G) досяжна з вершини v, якщо або w=v, або існує шлях (маршрут) з v в Граф (орієнтований граф) називається зв'язковим (сильно зв'язковим), якщо для будь-яких двох його вершин v, w існує
маршрут (шлях, що з'єднує v і Компонентою
зв'язності графа (сильної зв'язності
орієнтованого графа D) називається його зв'язний (сильно зв'язний)
підграф, який не є власним подграфом ніякого іншого зв'язного
(сильно зв'язного) подграфа графа G (орієнтованого графа D).

3. Матриці досяжності і зв'язності
Нехай A(D) - матриця суміжності орієнтованого псевдографа
D=(V,X) (або псевдографа G=(V,X)), де V={v
1
,…, v
n
}. Позначимо через k -ту степінь матриці суміжності A(D).
Елемент a
(k)
ij
матриці A
k
орієнтованого псевдографа D=(V,X)
(псевдографа G=(V,X)) дорівнює числу всіх шляхів (маршрутів)
довжини k з v
i
у v
j
Матриця досяжності орієнтованого графа D - квадратна матриця
T(D)=[t
ij
] порядку n, елементи якої дорівнюють
î
í
ì
=
,
0
,
,
1
випадку
іншому
у
v
з
досяжна
v
t
i
j
ij
Матриця сильної зв'язності орієнтованого графа D - квадратна матриця S(D)=[s
ij
] порядку n, елементи якої дорівнюють
î
í
ì
=
,
0
,
1
випадку
іншому
у
v
з
досяжна
v
і
v
досяжназз
v
s
j
i
i
j
ij
Матриця зв'язності графа G - квадратна матриця порядку n, елементи якої дорівнюють
î
í
ì
=
,
0
,
'
,
,
1
випадку
іншому
у
v
и
v
єднює
з
що
маршрут
існує
якщо
s
i
j
ij
Твердження 3. Нехай D=(V,X) - орієнтований граф, V={v
1
,…, v
n
},
A(D) - його матриця суміжності. тоді
1) T(D)=sign[E+A+A
2
+A
3
+… A
n-1
],
2) S(D)=T(D)
&T
T
(D) (T
T
-транспонована матриця,
&- поелементне множення).
Нехай G=(V,X) - граф, V={v
1
,…, v
n
}, A(G) - його матриця суміжності. тоді
S(G)=sign[E+A+A
2
+A
3
+… A
n-1
] (E - одинична матриця порядку n).
4. Компоненти сильної зв'язності орієнтованого графа
За допомогою матриці суміжності знайти компоненти сильної
зв'язності орієнтованого графа D.
Складаємо матрицю суміжності A(D) розмірності
n
n
´
(n - кількість вершин) для даного орієнтованого графа вона складається з нулів і одиниць, номери рядків - індекси вершин, з яких виходять дуги, номери стовпців - індекси вершин, в які дуги входять (якщо є
дуга, яка виходить із вершини v
i
і входить в v
j
, то елемент матриці
суміжності, що стоїть на перетині того рядка і того стовпця дорівнює 1, інакше - 0.).