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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

2. Находим T
+
( x
1
) ∩ T
-
( x
1
) = {x
1
, x
7
, x
11
}. Эти вершины и составляют первый
выделенный максимальный сильно связный подграф G
1
= ( X
1
, A
1
), где X
1
={x
1
,
x
7
, x
11
}, а матрица смежности A
1
подграфа G
1
показана на рис.22,a
3. Из исходного графа G вычитаем подграф G
1
G' = G \ G
1
;
G' = (X', A'), X' = { x
2
, x
3
, x
4
, x
5
, x
6
, x
8
, x
9
, x
10
}.
4. Так как X' не пустое множество, то G' принимаем за G и переходим ко
второму разбиению.
РАЗБИЕНИЕ. - 2
1. Выбираем любую вершину принадлежащую X, например x
2
, и находим
T
+
( x
2
) и T
-
( x
2
). Это показано на рис.22,б. T
+
( x
2
) = { x
2
, x
8
}; T
-
( x
2
) = { x
2
}. 
       2. Находим T+( x1 ) ∩ T- ( x1 ) = {x1, x7, x11}. Эти вершины и составляют первый
выделенный максимальный сильно связный подграф G1 = ( X1, A1), где X1={x1,
x7, x11}, а матрица смежности A1 подграфа G1 показана на рис.22,a
       3. Из исходного графа G вычитаем подграф G1 G' = G \ G1;
       G' = (X', A'), X' = { x2, x3, x4, x5, x6, x8, x9, x10 }.
       4. Так как X' не пустое множество, то G' принимаем за G и переходим ко
второму разбиению.


        РАЗБИЕНИЕ. - 2
       1. Выбираем любую вершину принадлежащую X, например x2, и находим
T+( x2 ) и T-( x2 ). Это показано на рис.22,б. T+ ( x2 ) = { x2, x8 };   T- ( x2 ) = { x2 }.

Страницы