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

UptoLike

ВУЗ: 

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

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

Рубрика: 

128
гать, что все вершины пронумерованы подряд на-
туральными числами, начиная с 1.
Путь
01
...
m
ii i
vv v→→→
длины m называют
путем ранга k при m > 1, если k – наибольшее сре-
ди чисел i
1
, …, i
m-1
, и путем ранга 0 при m = 1.
Путь нулевой длины также считают путем ранга 0.
Таким образом, ранг пути – это максимальный но-
мер вершины, в которую разрешено заходить по
пути из v
i
в v
j
(исключая вершины v
i
и v
j
). Путь
ранга 0 не содержит промежуточных вершин.
Максимальный ранг пути в ориентированном гра-
фе при указанном выше способе нумерации равен
числу его вершин.
Задача 5.8.
В ориентированном графе, изображенном на
рис. 5.10, путь v
1
→ v
4
→v
1
имеет ранг 4,
v
4
→ v
1
→v
2
– ранг 1,
v
4
→ v
1
→v
3
→ v
2
v
4
→ v
3
→v
2
– ранг 3,
v
4
→ v
1
→v
3
→ v
2
– ранг 3,
v
4
→ v
2
→v
2
→v
3
→ v
2
– ранг 3.
Определить матрицу стоимостей.
Решение.
Обозначим через C
(k)
матрицу стоимостей
прохождения между различными парами вершин
49
а) дерево есть связный граф, содержащий n
вершин и n – 1 ребер;
б) дерево есть граф, любые две вершины ко-
торого можно соединить простой цепью.
Пример 1.22.
Графы, изображенные на рис. 1.18, являются
деревьями.
Рис. 1.18
Если граф несвязный и не имеет циклов, то
каждая его связная компонента будет деревом. Та-
кой граф называется лесом. Можно интерпретиро-
вать рис. 1.18 как лес, состоящий из трех деревьев.
Определение 1.38. Остовным деревом связного
графа G называется любой его подграф, содержа-
щий все вершины графа G и являющийся деревом.
Пример 1.23.
Для графа, изображенного на рис. 1.19 а),
графы на рис. 1.19 б) и 1.19 в) являются остовны-
ми деревьями. 
гать, что все вершины пронумерованы подряд на-           а) дерево есть связный граф, содержащий n
туральными числами, начиная с 1.                            вершин и n – 1 ребер;
      Путь vi → vi → ... → vi длины m называют
             0   1         m
                                                         б) дерево есть граф, любые две вершины ко-
путем ранга k при m > 1, если k – наибольшее сре-           торого можно соединить простой цепью.
ди чисел i1, …, im-1, и путем ранга 0 при m = 1.                          Пример 1.22.
Путь нулевой длины также считают путем ранга 0.
Таким образом, ранг пути – это максимальный но-          Графы, изображенные на рис. 1.18, являются
мер вершины, в которую разрешено заходить по        деревьями.
пути из vi в vj (исключая вершины vi и vj). Путь
ранга 0 не содержит промежуточных вершин.
Максимальный ранг пути в ориентированном гра-
фе при указанном выше способе нумерации равен
числу его вершин.
                       Задача 5.8.
                                                                            Рис. 1.18
      В ориентированном графе, изображенном на
рис. 5.10, путь v1 → v4→v1 имеет ранг 4,                  Если граф несвязный и не имеет циклов, то
                v4 → v1→v2 – ранг 1,                каждая его связная компонента будет деревом. Та-
                v4 → v1→v3 → v2                     кой граф называется лесом. Можно интерпретиро-
                v4 → v3→v2 – ранг 3,                вать рис. 1.18 как лес, состоящий из трех деревьев.
                v4 → v1→v3→ v2 – ранг 3,            Определение 1.38. Остовным деревом связного
                v4 → v2→v2 →v3 → v2 – ранг 3.       графа G называется любой его подграф, содержа-
Определить матрицу стоимостей.                      щий все вершины графа G и являющийся деревом.
                  Решение.                                                Пример 1.23.
     Обозначим через C(k) матрицу стоимостей             Для графа, изображенного на рис. 1.19 а),
прохождения между различными парами вершин          графы на рис. 1.19 б) и 1.19 в) являются остовны-
                                                    ми деревьями.


                         128                                                   49

Страницы