Дискретная математика: Учебное пособие. Часть 3 - Основы теории графов, страница 8

В результате перестановок получено три блока: {x₁, x₂, x₃}, {x₁, x₃, x₅, x₇}, (x₅, x₆, x₇}. Число вершин в одном из блоков равно четырем. Следовательно, r(G)=4.Для определения неплотности графа необходимо найти дополнительный граф G=<X; `r>, определить для него матрицу достижимости q⁺  и выполнить необходимое число перестановок строк и столбцов, чтобы найти блоки, опирающиеся на максимальное число вершин.

Для графа G=<X; r> (см. рис. 20) найден граф ùG=<X;`r>. Ниже приведена матрица ||`r||, по которой вычислены матрицы ||h⁺|| и выполнены необходимые перестановки ее строк и столбцов. В результате перестановок получено три блока: {x₀, x₂, x₅}, {x₀, x₂, x₄, x₆}, (x₁, x₄, x₆}. Число вершин в одном из блоков равно четырем. Следовательно, r(ùG)=e(G)=4.

`r	x0	x1	x2	x3	x4	x5	x6	x7	h+=IÈ`r x5 x0 x2 x4 x6 x1 x3 x7	x5	x0	x2	x4	x6	x1	x3	x7
x0	1	0	1	1	1	1	1	0		1	1	1	0	0	0	0	0
x1	0	1	0	0	1	0	1	0		1	1	1	1	1	0	1	0
x2	1	0	1	0	1	1	1	1		1	1	1	1	1	0	0	1
x3	1	0	0	1	0	0	1	0		0	1	1	1	1	1	0	1
x4	1	1	1	0	1	0	1	1		0	1	1	1	1	1	1	0
x5	1	0	1	0	0	1	0	0		0	0	0	1	1	1	0	0
x6	1	1	1	1	1	0	1	0		0	1	0	0	1	0	1	0
x7	0	0	1	0	1	0	0	1		0	0	1	1	0	0	0	1

Поиск числа компонент связности графа G=<X; r>. Для этого следует в матрице достижимости выделить блоки связности вершин графа, число которых  определит число компонент.

x1         x2        x3      x4             x5       x6        x7       x8 Рис.21 Граф печатной платы          x5      x6       x7       x8

Для графа G=<X; r> (см. рис. 21), являющегося образом печатной платы, приведена матрица смежности ||r|| и вычислены матрицы  ||h⁺||, ||r²|| и ||h⁺²||.

Матрица ||h⁺²|| оформлена в результате перестановок строк и столбцов. Анализ этой матрицы показывает два блока связности. Первый блок опирается на вершины {x₁;x₄;x₅;x₆}, а второй - {x₂;x₃;x₇;x₈}. Эти два блока формируют два связных подграфа G₁=<X₁; r₁> и G₂=<X₂; r₂>, не связанных между собой. То есть для исходного графа G=<X; r> число компонент связности равно k(G)=2.