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

UptoLike

ВУЗ: 

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

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

Рубрика: 

52
содержащуюся в G
i
. Присваиваем i: = i + 1 и пере-
ходим к шагу 3.
Пример 1.24.
Найдем минимальное остовное дерево для
графа, изображенного на рис. 1.20.
Рис. 1.20.
Шаг 1. Установка начальных значений.
Введем матрицу длин ребер C:
С =
1 1 5
1 2 1 3
2 4
1 1 4 3
5 3 3
∞
∞
⎛⎞
⎜⎟
∞
⎜⎟
⎜⎟
∞
∞∞
⎜⎟
∞
⎜⎟
⎜⎟
∞∞
⎝⎠
.
125
решение нужно искать, используя метод исключе-
ния.
Задача 5.7.
Для графа, изображенного на рис. 5.9, вы-
числить матрицу кратчайших расстояний, перейдя
к полукольцу R
+
.
Решение.
Взвешенный ориентированный граф задает-
ся следующей матрицей А.
5101
23
1
34
A
∞
⎛⎞
⎜⎟
∞
∞
⎜⎟
=
⎜⎟
∞
∞∞
⎜⎟
∞
∞
⎝⎠
Система для вычисления первого столбца
матрицы А* имеет вид
x
1
= 5x
2
+ 10x
3
+ 1x
4
+ 0
x
2
= 2x
2
+ 3x
3
+ ∞
x
3
= 1x
2
+ ∞
x
4
= 3x
1
+ 4x
3
+ ∞
Обратим внимание на нюансы, связанные с
работой в полукольце R
+
: элементы 1 и 0 не явля-
ются единицей и нулем полукольца, т.е.
x ≠ x + 0, x ≠ 1·x
в общем случае. 
содержащуюся в Gi. Присваиваем i: = i + 1 и пере-   решение нужно искать, используя метод исключе-
ходим к шагу 3.                                     ния.
                Пример 1.24.                                         Задача 5.7.
      Найдем минимальное остовное дерево для              Для графа, изображенного на рис. 5.9, вы-
графа, изображенного на рис. 1.20.                  числить матрицу кратчайших расстояний, перейдя
                                                    к полукольцу R+.
                                                                       Решение.
                                                          Взвешенный ориентированный граф задает-
                                                    ся следующей матрицей А.
                                                                       ⎛ ∞ 5 10 1 ⎞
                                                                       ⎜          ⎟
                                                                       ⎜ ∞ 2 3 ∞⎟
                                                                    A=
                                                                       ⎜∞ 1 ∞ ∞⎟
                                                                       ⎜          ⎟
                                                                       ⎝ 3 ∞ 4 ∞⎠
                                                         Система для вычисления первого столбца
                                                    матрицы А* имеет вид
                    Рис. 1.20.
                                                                x1 =       5x2 + 10x3 + 1x4 + 0
Шаг 1. Установка начальных значений.                            x2 =       2x2 + 3x3       +∞
     Введем матрицу длин ребер C:                               x3 =       1x2             +∞
                 ⎛∞ 1 ∞          1 5⎞                           x4 = 3x1       + 4x3       +∞
                 ⎜1 ∞ 2          1 3 ⎟⎟
                 ⎜                                        Обратим внимание на нюансы, связанные с
             С = ⎜∞ 2 ∞          4 ∞⎟.              работой в полукольце R+: элементы 1 и 0 не явля-
                 ⎜                    ⎟
                 ⎜1 1 4          ∞ 3⎟               ются единицей и нулем полукольца, т.е.
                 ⎜5 3 ∞          3 ∞ ⎟⎠                             x ≠ x + 0, x ≠ 1·x
                 ⎝
                                                    в общем случае.



                           52                                                125

Страницы