实验要求
- 实验目的：加深图的汉密尔顿路及最短路径的理解与应用
- 实验内容：搜索某旅游城市地图（至少包含10个景点），随机选取出发地点，基于图论理论建立模型，给出合理的旅行路线。要求考虑时间、成本等因素。
- 实验原理和方法： （1） 不多于3名同学一组，选择某一旅游城市为研究对象，考察该城市至少10个景点在地图中的位置，根据景点间的路径绘制路线图。 （2） 考虑两个景点间的距离、交通工具等因素，设置路线权重。 （3） 随机从任意一点出发，基于图论理论建立模型，给出合理的旅行路线。
- 参考案例 该问题是一个典型的旅行商问题，通常用加权图表示。如果已知顶点u和顶点v的距离是r，连接u和v这两点权重就是r。图中一个圈C的权指的是C中所有边的权重之和。为了解决旅行商问题，我们需要确定加权图中哈密尔顿图的最小权值。以推销员在城市间巡回旅行为例，介绍该问题的求解。 问题：一个推销员计划在一些城市间巡回旅行，城市间的距离如图所示的加权图G，那么他这次旅行的最小距离是多少？
解答：因为图G是5阶图，因此G中有(5
