索红军

(渭南师范学院数学与信息科学学院，陕西渭南714000)

0 引言

图是一种多对多的复杂的网状数据结构，当给图的各条边赋予具有一定实际意义的数值时，就成为赋权图(也称为网)，赋权图是解决一些实际问题的非常有效的工具.赋权图中两顶点之间的最短路径、赋权图的最小生成树等都与解决实际问题密切相关.在此，我们提出应用赋权图解决环路访问的最小代价问题研究.

1 问题的提出

在赋权图中，研究过图的遍历、最小生成树、最短路径［1］、哈密尔顿回路［2］等很多方面.其中图的遍历要求从图的一个顶点开始，访问完所有顶点且每个顶点只能访问一次即可，图的最小生成树只要求各顶点之间有通路且路径的权值之和最小即可，最短路径研究的是两顶点间的路径，哈密尔顿回路要求每个顶点只能访问一次.然而现实问题中存在与哈密尔顿回路和最短路径相似但又不同的问题，即从图中某一顶点出发，访问完所有的顶点后又要回到起点，例如快递员从快递公司出发送完货物后又要回到快递公司等.这样的问题不同于传统旅行商问题［3］，不要求每个顶点只到达(访问)一次，也不完全等同于中国邮递员问题［2］(欧拉回路)，不要求所有的边都走到，但必须要求访问完所有的顶点后，又要回到出发顶点，并且在整个过程中经过的边的权值之和最小.对于这样的问题，在比较庞大的赋权图中，目前还没有公认的比较好的完……