Математическое моделирование на графах. Часть 1. Берцун В.Н. - 58 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

58 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
9
11
13
1
10
3
4
8
5
2
19
16
18
14
15
17
12
20
6
7
Рис. 2.13
Гамильтоновым циклом в графе G называется простой цикл, про-
ходящий через каждую вершину графа в точности по одному разу.
Граф, обладающий таким свойством, называется гамильтоновым. На
рис. 2.14 изображены варианты гамильтоновых циклов и цепей.
Рис. 2.14
Из этого рисунка следует, что гамильтонов цикл может не содер-
жать всех рёбер графа.
К задаче Гамильтона близка задача о посыльном (коммивояжере),
который должен посетить n городов, расстояния между которыми
известны, и вернуться обратно, но так, чтобы в каждом городе по-
бывать один раз, а цикл имел бы наименьшую длину. Очевидно, что

Страницы