Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 51 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

1. Метод разбиения графа по матрицам R и Q рассмотреть на
примере графа, изображенного на рисунке.
Решение:
Матрица достижимости R Матрица контрдостижимости Q
Умножая поэлементно матрицу контрдостижимости и матрицу
достижимости, получаем матрицу, в которой имеются одинаковые строки.
Соответсвующие этим строкам элементы группируем, получая блочно-
диагональную матрицу.
X
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
X
1
X
2
X
7
X
8
X
3
X
4
X
5
X
6
X
1
X
1
X
2
X
2
X
3
X
7
X
4
X
8
X
5
X
3
X
6
X
4
X
7
X
5
X
8
X
6
Ответ: Выделенные максимальные сильносвязные подграфы;
Gмсс
1
={. . . . . . . . . . . . . . . . . . . }, Gмсс
2
={ . . . . . . . . },
Gмсс
3
={ . . . . . . . . }, Gмсс
4
={ . . . . . . . . }.
X
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
X
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
X
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
X
1
X
2
X
3
X
4
X
5
X
6
X
7
X
8
1. Метод разбиения графа по матрицам R и Q рассмотреть на
примере графа, изображенного на рисунке.




Решение:
    Матрица достижимости R                   Матрица контрдостижимости Q

     X1 X2 X3 X4 X5 X6 X7 X8                        X1 X2 X3 X4 X5 X6 X7 X8
X1                                             X1
X2                                             X2
X3                                             X3
X4                                             X4
X5                                             X5
X6                                             X6
X7                                             X7
X8                                             X8

      Умножая поэлементно матрицу контрдостижимости и матрицу
достижимости, получаем матрицу, в которой имеются одинаковые строки.
Соответсвующие этим строкам элементы группируем, получая блочно-
диагональную матрицу.

     X1 X2 X3 X4 X5 X6 X7 X8                        X1 X2 X7 X8 X3 X4 X5 X6
X1                                            X1
X2                                            X2
X3                                            X7
X4                                            X8
X5                                            X3
X6                                            X4
X7                                            X5
X8                                            X6

Ответ: Выделенные максимальные сильносвязные подграфы;
    Gмсс1={. . . . . . . . . . . . . . . . . . . }, Gмсс2={ . . . . . . . . },
    Gмсс3={ . . . . . . . . }, Gмсс4={ . . . . . . . . }.

Страницы