Методы решения систем с разреженными матрицами. Теория графов. Глушакова Т.Н - 20 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

20
Фактор-дерево
|
Задача 47
.
Найти компоненты связности для графа G из задачи 46.
i=0: v=8 — одна компонента связности ;
i=1: v=19, L
0
={19}, L
1
={9,3} – одна компонента связности;
i=2: v=2, L
0
={10}, L
1
={2} – одна компонента связности;
i=3: v=17, L
0
={17}, L
1
={18}, L
32
={11} – одна компонента связности;
Задача 48
.
Нарисовать портрет переупорядоченной матрицы с блочной
структурой, отвечающей фактор-дереву из задачи 46.
⇒
L
41
={4,12}, L
42
={14,16,17} –
две компоненты связности
i=4: v=4, L
0
={4}, L
1
={12}
v=16, L
0
={16}, L
1
={14,1}, L
2
={7}
4
17 18
12
10
2
9 19
14
8 3
11
20
15
16
13
7 5
10
6
L
4
L
3
L
2
L
1
L
0
L
1
L
1
L
2
L
3
L
4
L
5
L
4
L
3
L
4
L
5
L
6
L
5
L
4
L
4
L
5
8
9 19 3
10
2
17 18 11
12 4 14 16 1 7
13 15 5 20
6
L
0
:
L
1
:
L
2
:
L
3
:
L
4
:
L
5
:
L
6
:
Древесные
ребра
2
5
8
9
,
19
,
3
2, 10
17, 18, 11
12, 4 14, 16, 1, 7
13, 15
5, 20
6
9
8
7
6
3
1
4 
                                                          20


                                                                      Древесные
   L4 12 L 4 L5 13                       15 L5                        ребра
          4                                                     8
                                                   L0:
   L3 17 L3 18 L4 14                     16 L4
                                                   L1:   9      19     3
   L2        L2            L3                 L4
        2         10            11       10
             L1                                    L2:   2      10
   L1                      L4                 L5
        9         19             7       5

   L0        L1            L5                 L6   L3: 17       18     11
        8            3          20       6


                                                   L4: 12       4      14     16      1       7

              Фактор-дерево
                                                                13     15             5       20
                                                   L5:
                 9          8

             8           9, 19, 3                  L6:                                    6

             7            2, 10
                    |
             6 17, 18, 11
        5 12, 4                 14, 16, 1, 7 4

            3 13, 15                 5, 20    2

                                1 6


Задача 47. Найти компоненты связности для графа G из задачи 46.

i=0: v=8 — одна компонента связности ;
i=1: v=19, L0={19}, L1={9,3} – одна компонента связности;
i=2: v=2, L0={10}, L1={2} – одна компонента связности;
i=3: v=17, L0={17}, L1={18}, L32={11} – одна компонента связности;
i=4: v=4, L0={4}, L1={12}                                ⇒ L41={4,12}, L42={14,16,17} –
     v=16, L0={16}, L1={14,1}, L2={7}                      две компоненты связности


Задача 48. Нарисовать портрет переупорядоченной матрицы с блочной
      структурой, отвечающей фактор-дереву из задачи 46.

Страницы