|
|
|
Теорема 12. |
|
Число |
(vi – vj)-маршрутов длины n |
в графе G = (V, X), равно |
элементу |
||||||||||||||||||||
n |
матрицы An. Здесь An – n-я степень матрицы A = A(G) графа G. |
|
|
|
|
|||||||||||||||||||||||
aij |
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
Следствие. Расстояние ρ(vi, vj) в графе G равно наименьшему из целых чисел n, для которых |
|||||||||||||||||||||||||
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
0 . |
|
|
|
|
элемент aij |
|
матрицы An отличен от нуля, т.е. vi , v j inf n : aij |
|
|
|
|||||||||||||||||||||||
|
|
|
Если граф G связный, то |
|
|
vi , v j : vi , v j q , |
значит, указанным следствием можно |
|||||||||||||||||||||
пользоваться для проверки связности графов и отыскания расстояний между вершинами. |
|
|
|
|||||||||||||||||||||||||
|
|
|
Теорема 13. Граф G = (V, X) не связный тогда и только тогда, когда существует нумерация |
|||||||||||||||||||||||||
вершин, при которой матрица смежности A(G) имеет квазидиагональный вид. |
|
|
|
|||||||||||||||||||||||||
|
|
|
Матрица смежности мультиграфа G = (V, X), V p , – (p×p)-матрица, в которой элемент |
|||||||||||||||||||||||||
aij равен числу кратных ребер, соединяющих вершины vi и vj. |
|
|
|
|
||||||||||||||||||||||||
|
|
|
Для псевдографов диагональные элементы матрицы A(G) могут отличными от нуля: aii ≠ 0, |
|||||||||||||||||||||||||
если имеется петля в вершине vi. |
|
|
|
|
|
|
|
A p p , в которой aij : vi , v j . |
||||||||||||||||||||
|
|
|
Матрица смежности орграфа G = (V, Γ) – матрица |
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T |
|
|
|
|
Матрица смежности |
орграфа, вообще говоря, |
не является симметричной |
( A |
A ). |
|||||||||||||||||||||
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Симметризации орграфа можно добиться симметризацией матрицы A G . |
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
Теорема 14. если G = (V, Γ) – орграф с петлями и кратными дугами, то элемент a ij |
матрицы |
||||||||||||||||||||||||
A |
n |
|
равен числу (vi – vj)-путей длины n. |
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
Отсюда следует, что если существует n0 такое, что |
An 0 при всех n > n0, то в орграфе нет |
||||||||||||||||||||||||
контуров. Подобные результаты справедливы и для простых графов. |
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Операции над графами |
|
|
|
|
||||
|
|
|
Унарные операции |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
Пусть дан граф G = (V, X); |
W V |
, Y X , A – произвольное конечное множество вершин |
|||||||||||||||||||||||
( A V ); B – множество ребер, не входящих в X: B v, w : v, w V & B X . |
|
|
|
|||||||||||||||||||||||||
1. |
|
Удаление множества вершин W из G – операция, при которой из графа G получается граф |
|
|||||||||||||||||||||||||
|
|
G W V |
, X |
|
: |
V |
|
V \ W |
& |
|
X |
|
|
X \ x X : w W x инцидентно w . |
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2. |
|
Удаление множества ребер Y из G – операция, при которой из графа G получается граф |
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
: |
V |
|
|
V |
& |
X |
|
X |
\ Y . |
|
|
|
|
|
||||||
|
|
G Y V , X |
|
|
|
|
|
|
|
|
|
|||||||||||||||||
3. |
|
Добавление множества вершин A к G – операция, при которой получается граф |
|
|
|
|||||||||||||||||||||||
|
|
G A |
V |
, X |
|
: |
V |
|
|
V A |
& |
|
X |
|
|
X v, w : v V & w A . |
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
4. |
|
Добавление множества ребер B к G – операция, при которой получается граф |
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
: |
V |
|
V |
& |
X |
|
X B . |
|
|
|
|
|
||||||||
|
|
G B V |
, X |
|
|
|
|
|
|
|
|
|
Если удаляемое / добавляемое множество состоит из одного элемента, фигурные скобки в его записи опускаются: например, если A = {w}, вместо G + {w} пишем G + w.
5.Замыкание / отождествление вершин vi и vj графа G – операция, при которой они заменяются одной новой вершиной v, все ребра, инцидентные vi и vj, становятся инцидентными v.
6.Элементарное стягивание ребра графа – операция, при которой это ребро отбрасывается и отождествляются вершины, являющиеся его концами.
Граф G стягиваем к H, если H можно получить из G конечным числом элементарных стягиваний.
7.Подразбиение ребра x = {u, v} – операция, при которой отбрасывается ребро x и добавляется два новых ребра x1 = {u, w} и x2 = {w, v}.
2