Составители:
Рубрика:
126
Из первого уравнения системы сразу следу-
ет, что х
1
= 0, так как одно из слагаемых в правой
части есть элемент 0. Напомним, что итерация лю-
бого элемента в рассматриваемом полукольце рав-
на единице полукольца. Учитывая этот факт, из
второго уравнения получаем
x
2
= 2*(3x
3
+∞ ) = 3x
3
Исключая x
2
из остальных уравнений систе-
мы и учитывая, что х
1
= 0, получаем
x
2
= 3 x
3
+ ∞
x
3
= 1(3 x
3
) + ∞
x
4
= 3·0 + 4x
3
+ ∞.
Далее, из второго уравнения имеем
x
3
= (1·3) x
3
+∞ = 4x
3
+∞
откуда x
3
= 4*·∞ = ∞, и поэтому
x
4
= 3 · 0 +4 · ∞ = 3 +∞ = 3.
Подставляя найденное значение х
3
в выра-
жение для х
2
, получаем х
2
.=.∞. Первый столбец ис-
комой матрицы вычислен:
0
3
⎛⎞
⎜⎟
∞
⎜⎟
⎜⎟
∞
⎜⎟
⎝⎠
Этот столбец содержит кратчайшие расстоя-
ния от всех вершин графа до вершины v
1
. Наличие
51
а) Нужно соединить n городов железнодорожными
линиями (автомобильными дорогами, линиями
электропередач, сетью трубопроводов и т.д.) так,
чтобы суммарная длина линий или стоимость была
бы минимальной.
б) Требуется построить схему электрической сети,
в которой клеммы должны быть соединены с по-
мощью проводов наименьшей общей длины.
Задачу построения минимального остовного
дерева можно
решить с помощью следующего ал-
горитма.
Алгоритм 2. (Алгоритм Краскала)
Шаг 1. Установка начальных значений. Вводится
матрица длин ребер C графа G.
Шаг 2. Выбрать в графе G ребро минимальной
длины. Построить граф G
2
, состоящий из данного
ребра и инцидентных ему вершин. Положить i = 2.
Шаг 3. Если i = n, где n – число ребер графа, то за-
кончить работу (задача решена), в противном слу-
чае перейти к шагу 4.
Шаг 4. Построить граф G
i + 1,
добавляя к графу G
i
новое ребро минимальной длины, выбранное сре-
ди всех ребер графа G, каждое из которых инци-
дентно какой-нибудь вершине графа G
i
и одновре-
менно инцидентно какой-нибудь вершине графа G,
не содержащейся в G
i
. Вместе с этим ребром
включаем в G
i + 1
и инцидентную ему вершину, не
Из первого уравнения системы сразу следу- а) Нужно соединить n городов железнодорожными
ет, что х1 = 0, так как одно из слагаемых в правой линиями (автомобильными дорогами, линиями
части есть элемент 0. Напомним, что итерация лю- электропередач, сетью трубопроводов и т.д.) так,
бого элемента в рассматриваемом полукольце рав- чтобы суммарная длина линий или стоимость была
на единице полукольца. Учитывая этот факт, из бы минимальной.
второго уравнения получаем б) Требуется построить схему электрической сети,
x2 = 2*(3x3 +∞ ) = 3x3 в которой клеммы должны быть соединены с по-
Исключая x2 из остальных уравнений систе- мощью проводов наименьшей общей длины.
мы и учитывая, что х1 = 0, получаем Задачу построения минимального остовного
дерева можно решить с помощью следующего ал-
x2 = 3 x3 +∞ горитма.
x3 = 1(3 x3) + ∞ Алгоритм 2. (Алгоритм Краскала)
x4 = 3·0 + 4x3 + ∞. Шаг 1. Установка начальных значений. Вводится
Далее, из второго уравнения имеем матрица длин ребер C графа G.
x3 = (1·3) x3 +∞ = 4x3 +∞ Шаг 2. Выбрать в графе G ребро минимальной
откуда x3 = 4*·∞ = ∞, и поэтому длины. Построить граф G2, состоящий из данного
x4 = 3 · 0 +4 · ∞ = 3 +∞ = 3. ребра и инцидентных ему вершин. Положить i = 2.
Подставляя найденное значение х3 в выра- Шаг 3. Если i = n, где n – число ребер графа, то за-
жение для х2, получаем х2.=.∞. Первый столбец ис- кончить работу (задача решена), в противном слу-
комой матрицы вычислен: чае перейти к шагу 4.
⎛0⎞ Шаг 4. Построить граф Gi + 1, добавляя к графу Gi
⎜ ⎟ новое ребро минимальной длины, выбранное сре-
⎜∞⎟ ди всех ребер графа G, каждое из которых инци-
⎜∞⎟
⎜ ⎟ дентно какой-нибудь вершине графа Gi и одновре-
⎝3⎠ менно инцидентно какой-нибудь вершине графа G,
Этот столбец содержит кратчайшие расстоя- не содержащейся в Gi. Вместе с этим ребром
ния от всех вершин графа до вершины v1. Наличие включаем в Gi + 1 и инцидентную ему вершину, не
126 51
Страницы
- « первая
- ‹ предыдущая
- …
- 49
- 50
- 51
- 52
- 53
- …
- следующая ›
- последняя »
