Основные понятия теории графов. Гладких О.Б - 54 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

54
Вместе с этим ребром включаем в G
4
вершину x
3
,
не содержащуюся в G
3
. Полагаем i = 4 и перехо-
дим к шагу 3.
Шаг 3. Так как i
≠ n, поэтому переходим к шагу 4.
Шаг 4. Строим граф G
5
, добавляя к графу G
3
новое
ребро минимальной длины из ребер (x
1
, x
5
), (x
2
, x
5
),
(x
4
, x
5
). Таких ребер длины три два:
(x
2
, x
5
) и (x
4
, x
5
).
Возьмем (x
2
, x
5
). Вместе с этим ребром включаем в
G
5
вершину x
5
, не содержащуюся в G
4
. Полагаем
i.= 5 и переходим к шагу 3.
Шаг 3. Так как i = n, то граф G
5
– искомое мини-
мальное остовное дерево. Суммарная длина ребер
равна 1 + 1 + 2 + 3 = 7.
Процесс построения минимального остовно-
го дерева изображен на рис. 1.21.
Рис. 1.21.
123
1
0
0
1
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
Второй столбец определяется из системы
x
1
= x
2
+ x
3
+ x
4
+ 0
x
2
= x
2
+ x
3
+ 1
x
3
= x
2
+ 0
x
4
= x
1
+ x
3
+ 0
Исключая х
1
, получаем
x
2
= x
2
+ x
3
+ 1
x
3
= x
2
+ 0
x
4
= x
2
+ x
3
+ x
4
+ 0
Из второго уравнения имеем
x
2
= 1*(x
3
+ 1) = x
3
+ 1.
Далее находим
x
3
= x
3
+ 1
x
4
= x
3
+ x
4
+ 1
Отсюда х
3
= 1*1 = 1 и х
4
= х
4
+ 1.
В итоге
х
4
= 1*1 = 1, х
2
= 1 + 1 = 1,
x
1
= 1 + 1 + 1 + + 0 = 1.
Таким образом, второй столбец А* есть 
Вместе с этим ребром включаем в G4 вершину x3,                                     ⎛1⎞
                                                                                   ⎜ ⎟
не содержащуюся в G3. Полагаем i = 4 и перехо-                                     ⎜0⎟
дим к шагу 3.                                                                      ⎜0⎟
                                                                                   ⎜ ⎟
Шаг 3. Так как i ≠ n, поэтому переходим к шагу 4.                                  ⎝1⎠
Шаг 4. Строим граф G5, добавляя к графу G3 новое             Второй столбец определяется из системы
ребро минимальной длины из ребер (x1, x5), (x2, x5),
(x4, x5). Таких ребер длины три два:                               x1 =      x2 + x3 + x4 + 0
                   (x2, x5) и (x4, x5).                            x2 =      x2 + x3      +1
Возьмем (x2, x5). Вместе с этим ребром включаем в                  x3 =      x2           +0
G5 вершину x5, не содержащуюся в G4. Полагаем                      x4 = x1      + x3      +0
i.= 5 и переходим к шагу 3.                                  Исключая х1, получаем
Шаг 3. Так как i = n, то граф G5 – искомое мини-                           x2 = x2 + x3      +1
мальное остовное дерево. Суммарная длина ребер                             x3 = x2           +0
равна 1 + 1 + 2 + 3 = 7.                                                   x4 = x2 + x3 + x4 + 0
        Процесс построения минимального остовно-
го дерева изображен на рис. 1.21.                           Из второго уравнения имеем
                                                                    x2 = 1*(x3 + 1) = x3 + 1.
                                                       Далее находим
                                                                           x3 = x3       +1
                                                                            x4 = x3 + x4 + 1
                                                            Отсюда х3 = 1*1 = 1 и х4 = х4 + 1.
                                                       В итоге
                                                                    х4 = 1*1 = 1, х2 = 1 + 1 = 1,
                                                                    x1 = 1 + 1 + 1 + + 0 = 1.
                                                            Таким образом, второй столбец А* есть

                     Рис. 1.21.



                            54                                                     123

Страницы