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

UptoLike

ВУЗ: 

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

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

Рубрика: 

124
1
1
1
1
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
Аналогично вычисляем третий и четвертый
столбцы и в результате получаем матрицу А*:
*
1111
0110
0110
1111
A
⎛⎞
⎜⎟
⎜⎟
=
⎜⎟
⎜⎟
⎝⎠
Анализ этой матрицы показывает, что дан-
ный граф связен и имеет две бикомпоненты:
{v
1
, v
4
}, {v
2
, v
3
}
В полукольце В можно упростить решение
систем уравнений, воспользовавшись свойствами
полукольца. Легко видеть, что наименьшее реше-
ние уравнения
1
1
n
kii
i
xax
=
=+
∑
есть x
k
= 1 и не зависит от значений переменных в
правой части уравнения. Из первого уравнения
сразу получаем х
1
= 1. Тогда четвертое уравнение
принимает вид х
4
= х
3
+ 1, откуда х
4
= 1. Поскольку
x
1
и х
4
не входят в оставшиеся два уравнения, их
53
Шаг 2. Выберем ребро минимальной длины. Ми-
нимальная длина ребра равна единице. Таких ре-
бер три:
(x
1
, x
2
), (x
1
, x
4
), (x
2
, x
4
).
В этом случае можно взять любое. Возьмем (x
1
, x
2
).
Построим граф G
2
, состоящий из данного ребра и
инцидентных ему вершин x
1
и x
2
. Положим i = 2.
Шаг 3. Так как n = 5, то i
≠ n, поэтому переходим к
шагу 4.
Шаг 4. Строим граф G
3,
добавляя к графу G
2
новое
ребро минимальной длины, выбранное среди всех
ребер графа G, каждое из которых инцидентно од-
ной из вершин x
1
, x
2
и одновременно инцидентно
какой–нибудь вершине графа G, не содержащейся
в G
2
, т.е. одной из вершин x
3
, x
4
, x
5
. Таким образом,
нужно выбрать ребро минимальной длины из ре-
бер (x
1
, x
4
), (x
1
, x
5
), (x
2
, x
3
), (x
2
, x
4
), (x
2
, x
5
). Таких ре-
бер длины единица два:
(x
1
, x
4
) и (x
2
, x
4
).
Можно выбрать любое. Возьмем (x
1
, x
4
). Вместе с
этим ребром включаем в G
3
вершину x
4
, не
содержащуюся в G
2
. Полагаем i = 3 и переходим к
шагу 3.
Шаг 3. Так как i
≠ n, поэтому переходим к шагу 4.
Шаг 4. Строим граф G
4
, добавляя к графу G
3
новое
ребро минимальной длины из ребер (x
1
, x
5
), (x
2
, x
3
),
(x
2
, x
5
), (x
4
, x
5
). Такое ребро длины два одно:
(x
2
, x
3
). 
                              ⎛ 1⎞                    Шаг 2. Выберем ребро минимальной длины. Ми-
                              ⎜ ⎟                     нимальная длина ребра равна единице. Таких ре-
                              ⎜ 1⎟
                              ⎜ 1⎟                    бер три:
                              ⎜ ⎟                                         (x1, x2), (x1, x4), (x2, x4).
                              ⎝ 1⎠
                                                      В этом случае можно взять любое. Возьмем (x1, x2).
     Аналогично вычисляем третий и четвертый          Построим граф G2, состоящий из данного ребра и
столбцы и в результате получаем матрицу А*:           инцидентных ему вершин x1 и x2. Положим i = 2.
                       ⎛1       1 1 1⎞                Шаг 3. Так как n = 5, то i ≠ n, поэтому переходим к
                       ⎜             ⎟                шагу 4.
                         0      1 1 0⎟
                    A =⎜
                     *
                                                      Шаг 4. Строим граф G3, добавляя к графу G2 новое
                       ⎜0       1 1 0⎟
                       ⎜             ⎟                ребро минимальной длины, выбранное среди всех
                       ⎝1       1 1 1⎠
                                                      ребер графа G, каждое из которых инцидентно од-
      Анализ этой матрицы показывает, что дан-        ной из вершин x1, x2 и одновременно инцидентно
ный граф связен и имеет две бикомпоненты:             какой–нибудь вершине графа G, не содержащейся
                 {v1, v4}, {v2, v3}                   в G2, т.е. одной из вершин x3, x4, x5. Таким образом,
      В полукольце В можно упростить решение          нужно выбрать ребро минимальной длины из ре-
систем уравнений, воспользовавшись свойствами         бер (x1, x4), (x1, x5), (x2, x3), (x2, x4), (x2, x5). Таких ре-
полукольца. Легко видеть, что наименьшее реше-        бер длины единица два:
ние уравнения                                                                 (x1, x4) и (x2, x4).
                        n                             Можно выбрать любое. Возьмем (x1, x4). Вместе с
                  xk = ∑ ai xi + 1                    этим ребром включаем в G3 вершину x4, не
                       i =1
                                                      содержащуюся в G2. Полагаем i = 3 и переходим к
есть xk = 1 и не зависит от значений переменных в     шагу 3.
правой части уравнения. Из первого уравнения          Шаг 3. Так как i ≠ n, поэтому переходим к шагу 4.
сразу получаем х1 = 1. Тогда четвертое уравнение      Шаг 4. Строим граф G4, добавляя к графу G3 новое
принимает вид х4 = х3 + 1, откуда х4 = 1. Поскольку   ребро минимальной длины из ребер (x1, x5), (x2, x3),
x1 и х4 не входят в оставшиеся два уравнения, их      (x2, x5), (x4, x5). Такое ребро длины два одно:
                                                                                    (x2, x3).

                              124                                                      53

Страницы