3.4.1.6. Поиск числа компонент связности графа

Для этого следует в матрице достижимости выделить блоки наибольшей связности вершин графа. Число таких блоков определит число компонент (G).

Пример: на рис. 3.15 дан граф G=<x, r>. Определить (G).

В таблице r приведена матрица смежностей графа G

1, если x_i смежна x_j,

r(i, j)=

0, в противном случае.

Ниже приведены матрица смежности и матрица достижимости ||q||=I||r||, элементы которой определяют по формуле q(i, j) = 1(i, i) r(i, j) при ij.

r	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	0	0	0	0	0	1	0	0	0	0
x2	0	0	0	0	1	0	0	0	0	0
x3	0	0	0	0	0	0	1	1	0	0
x4	0	0	0	0	0	0	0	0	1	0
x5	0	1	0	0	0	0	0	0	1	1
x6	1	0	0	0	0	0	1	1	0	0
x7	0	0	1	0	0	1	0	0	0	0
x8	0	0	1	0	0	1	0	0	0	0
x9	0	0	0	1	1	0	0	0	0	1
x10	0	0	0	0	1	0	0	0	1	0

q	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	1	0	0	0	0	1	0	0	0	0
x2	0	1	0	0	1	0	0	0	1	1
x3	0	0	1	0	0	0	1	1	0	0
x4	0	0	0	1	0	0	0	0	1	0
x5	0	1	0	0	1	0	0	0	1	1
x6	1	0	0	0	0	1	1	1	0	0
x7	0	0	1	0	0	1	1	0	0	0
x8	0	0	1	0	0	1	0	1	0	0
x9	0	0	0	1	1	0	0	0	1	1
x10	0	0	0	0	1	0	0	0	1	1

В таблице r² элементы определяют по формуле:

r² (i, j) =_k=1ⁿ (r(i, k)r(k, j)).

r^2	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	1	0	0	0	0	0	1	1	0	0
x2	0	1	0	0	0	0	0	0	1	1
x3	0	0	1	0	0	1	0	0	0	0
x4	0	0	0	1	1	0	0	0	0	1
x5	0	0	0	1	1	0	0	0	0	1
x6	0	0	1	0	0	1	0	0	0	0
x7	1	0	0	0	0	0	1	1	0	0
x8	1	0	0	0	0	0	1	1	0	0
x9	0	1	0	0	0	0	0	0	1	1
x10	0	1	0	1	1	0	0	0	1	1

В таблице q² элементы определяют по формуле:

q²(i, j) =q(i, j)r²(i, j) при ij.

q^2	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	1	0	0	0	0	1	1	1	0	0
x2	0	1	0	0	1	0	0	0	1	1
x3	0	0	1	0	0	1	1	1	0	0
x4	0	0	0	1	1	0	0	0	1	1
x5	0	1	0	1	1	0	0	0	1	1
x6	1	0	1	0	0	1	1	1	0	0
x7	1	0	1	0	0	1	1	1	0	0
x8	1	0	1	0	0	1	1	1	0	0
x9	0	1	0	1	1	0	0	0	1	1
x10	0	1	0	1	1	0	0	0	1	1

В таблице r³ элементы определяют по формуле:

r³(i, j) =_k=1ⁿ (r(i, k)r²(k, j)).

r^3	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	0	0	1	0	0	1	0	0	0	0
x2	0	0	0	1	1	0	0	0	1	1
x3	1	0	0	0	0	0	1	1	0	0
x4	0	1	0	0	1	0	0	0	1	1
x5	0	1	0	1	1	0	0	0	1	1
x6	1	0	0	0	0	0	1	1	0	0
x7	0	0	1	0	0	1	0	0	0	0
x8	0	0	1	0	0	1	0	0	0	0
x9	0	1	0	1	1	0	0	0	1	1
x10	0	1	0	1	1	0	0	0	1	1

В таблице q³ элементы определяют по формуле:

q³(i, j) =q²(i, j) r³(i, j) при ij.

q^3	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	1	0	1	0	0	1	1	1	0	0
x2	0	1	0	1	1	0	0	0	1	1
x3	1	0	1	0	0	1	1	1	0	0
x4	0	1	0	1	1	0	0	0	1	1
x5	0	1	0	1	1	0	0	0	1	1
x6	1	0	1	0	0	1	1	1	0	0
x7	1	0	1	0	0	1	1	1	0	0
x8	1	0	1	0	0	1	1	1	0	0
x9	0	1	0	1	1	0	0	0	1	1
x10	0	1	0	1	1	0	0	0	1	1

Дальнейший поиск q⁴, q⁵,...не приводит к изменению матриц достижимости.

Выполняя перестановку строк и столбцов матрицы q³, получим два блока связности.

q^3	x1	x3	x6	x7	x8	x2	x4	x5	x9	x10
x1	1	1	1	1	1	0	0	0	0	0
x3	1	1	1	1	1	0	0	0	0	0
x6	1	1	1	1	1	0	0	0	0	0
x7	1	1	1	1	1	0	0	0	0	0
x8	1	1	1	1	1	0	0	0	0	0
x2	0	0	0	0	0	1	1	1	1	1
x4	0	0	0	0	0	1	1	1	1	1
x5	0	0	0	0	0	1	1	1	1	1
x9	0	0	0	0	0	1	1	1	1	1
x10	0	0	0	0	0	1	1	1	1	1

Следовательно, граф G=<X, r> содержит два связных подграфа G’₁ и G'₂, т. е. k(G)=2.