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

UptoLike

ВУЗ: 

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

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

Рубрика: 

50
Рис. 1.19.
Пусть граф G имеет n вершин и m ребер. Так
как всякое дерево с n вершинами по определению
имеет n – 1 ребер, то любое остовное дерево графа
G получается из этого графа в результате удаления
m – (n – 1) = m – n + 1 ребер.
Определение 1.39. Число
γ
= m – n + 1 называется
цикломатическим числом
графа.
11B1.11. Минимальные остовные деревья
нагруженных графов
Пусть G – связный нагруженный граф. Зада-
ча построения минимального остовного дерева
за-
ключается в том, чтобы из множества остовных
деревьев найти дерево, у которого сумма длин ре-
бер минимальна.
Приведем типичные случаи, когда возникает
необходимость построения минимального остов-
ного дерева графа.
127
в нем нулей полукольца во второй и третьей стро-
ках говорит о том, что вершина v
1
не достижима из
вершин v
2
и из v
3
.
Аналогично вычисляются остальные столб-
цы матрицы А*. Результат будет следующим:
*
0551
03
10
3540
A
⎛⎞
⎜⎟
∞
∞
⎜⎟
=
⎜⎟
∞
∞
⎜⎟
⎝⎠
Для данного простого ориентированного
графа легко сопоставить полученный алгебраиче-
ский результат с результатом «визуального» ана-
лиза ориентированного графа. Рассмотрим, на-
пример, пару вершин (v
1
, v
3
). В ориентированном
графе есть различные пути из вершины v
1
в вер-
шину v
3
. Вычислим метки по простым путям. По
пути v
1
→ v
4
→v
3
сумма меток равна 5, по пути
v
1
.→ v
3
– 10, а по пути v
1
→ v
2
→ v
3
– 8. Кратчайшее
расстояние – 5, что совпадает с ответом, получен-
ным алгебраически: элемент
*
13
a также равен 5.
Есть еще один способ вычисления замыка-
ния матрицы с элементами в замкнутом полуколь-
це. Он основан на понятия пути ранга k из верши-
ны v
i
, в вершину v
j
.
Пусть в ориентированном графе выбрана и
зафиксирована нумерация вершин. Будем пола-
                                                    в нем нулей полукольца во второй и третьей стро-
                                                    ках говорит о том, что вершина v1 не достижима из
                                                    вершин v2 и из v3.
                                                          Аналогично вычисляются остальные столб-
                                                    цы матрицы А*. Результат будет следующим:
                                                                        ⎛0    5 5 1⎞
                                                                        ⎜          ⎟
                                                                          ∞   0 3 ∞⎟
                                                                     A =⎜
                                                                      *

                    Рис. 1.19.                                          ⎜∞    1 0 ∞⎟
                                                                        ⎜          ⎟
      Пусть граф G имеет n вершин и m ребер. Так                        ⎝3    5 4 0⎠
как всякое дерево с n вершинами по определению             Для данного простого ориентированного
имеет n – 1 ребер, то любое остовное дерево графа   графа легко сопоставить полученный алгебраиче-
G получается из этого графа в результате удаления   ский результат с результатом «визуального» ана-
m – (n – 1) = m – n + 1 ребер.                      лиза ориентированного графа. Рассмотрим, на-
Определение 1.39. Число γ = m – n + 1 называется    пример, пару вершин (v1, v3). В ориентированном
цикломатическим числом графа.                       графе есть различные пути из вершины v1 в вер-
                                                    шину v3. Вычислим метки по простым путям. По
     1.11. Минимальные остовные деревья
     1B




                                                    пути v1 → v4→v3 сумма меток равна 5, по пути
              нагруженных графов                    v1.→ v3 – 10, а по пути v1 → v2→ v3 – 8. Кратчайшее
      Пусть G – связный нагруженный граф. Зада-     расстояние – 5, что совпадает с ответом, получен-
ча построения минимального остовного дерева за-     ным алгебраически: элемент a13* также равен 5.
ключается в том, чтобы из множества остовных
деревьев найти дерево, у которого сумма длин ре-           Есть еще один способ вычисления замыка-
бер минимальна.                                     ния матрицы с элементами в замкнутом полуколь-
      Приведем типичные случаи, когда возникает     це. Он основан на понятия пути ранга k из верши-
необходимость построения минимального остов-        ны vi, в вершину vj.
ного дерева графа.                                         Пусть в ориентированном графе выбрана и
                                                    зафиксирована нумерация вершин. Будем пола-


                           50                                                 127

Страницы