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

В результате перестановок получено три блока: {x1, x2, x3}, {x1, x3, x5, x7}, (x5, x6, x7}. Число вершин в одном из блоков равно четырем. Следовательно, r(G)=4.Для определения неплотности графа необходимо найти дополнительный граф G=<X; `r>, определить для него матрицу достижимости q+  и выполнить необходимое число перестановок строк и столбцов, чтобы найти блоки, опирающиеся на максимальное число вершин.

Для графа G=<X; r> (см. рис. 20) найден граф ùG=<X;`r>. Ниже приведена матрица ||`r||, по которой вычислены матрицы ||h+|| и выполнены необходимые перестановки ее строк и столбцов. В результате перестановок получено три блока: {x0, x2, x5}, {x0, x2, x4, x6}, (x1, x4, x6}. Число вершин в одном из блоков равно четырем. Следовательно, 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+||, ||r2|| и ||h+2||.

Матрица ||h+2|| оформлена в результате перестановок строк и столбцов. Анализ этой матрицы показывает два блока связности. Первый блок опирается на вершины {x1;x4;x5;x6}, а второй - {x2;x3;x7;x8}. Эти два блока формируют два связных подграфа G1=<X1; r1> и G2=<X2; r2>, не связанных между собой. То есть для исходного графа G=<X; r> число компонент связности равно k(G)=2.