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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

Глава 2. Плоские и планарные графы 59
общему числу маршрутов тогда соответствует n! возможных пере-
становок вершин полного графа.
Пусть, например, четыре города связаны по схеме на рис. 2.15.
Если движение начинается из города А, то общее число маршрутов
(n – 1)! = 6.
A
E
D
B
710
10
13
10 6
Рис. 2.15
Для решения задачи методом перебора можно построить граф-
дерево. На рис. 2.16 представлен фрагмент такого графа, содержа-
щий все шесть гамильтоновых циклов. Для рассматриваемой задачи
один из самых коротких маршрутов S
AВEDA
= 33, а один из самых
длинных S
AEBDA
= 43.
A
B
B
B
B
B
A
EE
E
E
E
D
DD
D
D
Рис. 2.16

Страницы