课题的目的及意义

图的理论是应用在很多地方的,是运筹学里的一部分。已在科学管理,信息理论,化 学中的应用,计算机电子等各个领域中广泛得到应用了。在实际生活、生产和科学研究 过程中,我们能够运用图的伦理和还有一些方法来处理很多的问题。就像在结合生产中, 为完成某些任务,各工学和理学之间怎么样联接,才能够使生产的任务完成变得方便又省 事。一个邮递员送邮件,要他走完他所负责邮递的所有街道,然后回到邮局,应该按照怎 么样的路线走,才能够找出最佳路线。中国邮递员问题是在 1960 年里,在实际过程中首 次提出数学问题。原本在实际生活问题是这样的:“一个邮递员要把他所负责的邮件送到 每条街道,应该怎么走才能让走的路程又快又短,”。在以前开始研究中国邮递员问题时, 国外就有人研究过旅行售货员的问题,即:“一个售货员要到 n 个城市去售货,要走遍所 有城市时,应当如何选择出一条最佳的路线,走的路程又短”。这个难题就比较难解决了。 当 n 较大时,即便使用大型的计算机,也是很难解决。邮递员在面临问题时显然可以归纳 为旅行售货员的问题。实际上,把邮递员必须送的每一个地点看作是一个城市就好了。但 是一般来说,邮递员要每次到约二、三百多个地点送信,若归纳为旅行售货员问题来解决, 这将是一个规模很大的问题了,是没有解决的。但是在仔细了解了邮递员遇到的问题后, 发觉这个问题具有一定的特点,即需要送邮件的地点一般都是比较稠密的排序在街道上 的。所以真实上像这样的“最短邮递路问题”,在 1965 年后来在国外就称为“中国邮员问 题”。论文网

1.2 国内外研究现状与发展趋势

1.3 基本概念及符号说明

1.3.1 基本概念

路(Walk):图 G 中一个点边交替出现的序列 w v0e1v1e2 ek vk 。 迹(Trail):边不重的途径。

路(Path): 顶点不重复的迹。 圈(Cycle):一条封闭的路称为圈。

简单图(Simple Graph):如果一个图 G 没有环和多重边,那么称 G 为简单图。

欧拉链(Euler chain):有一个非空连通图且存在一条链,过每边一次且仅一次。 欧拉圈(Euler circle):若有一个简易圈,过每边一次且仅一次。 欧拉图(Euler):一个图有欧拉圈。

连通性(Connectivity):在图 G V , E中,若从点 v 到点 v 有路相连,则称 v 和 v 连通。

i j i j

割边(Cut edge):若 e 是连通图 G 中的一边,如果从 G 中丢去 e,图就不连通了。 连通图(Connected graph):如果图 G 中的任意的两个点间都是连通的,则称 G 为连通图。 无向图(Undirected graph):一个图 G 是由点和边构成的。文献综述

弧(arc):带箭头的连线。

简单图(Simple Graph):如果一个图 G 没有环和多重边。

度(degree): 一个图 G (V, E) , vV (G),图 G 与 v 有关联边的边数量。 环(ring):图 G (V, E) 中端点重合为一点的边。

1.3.2 符号说明

V G:图 G 的顶点集

EG:图 G 的边集

w(e) :每条边上的权

dG (V) :图 G 上的顶点的度数

1.4 用到的定理

定理 1:若无向连通图 G (V, E) 是欧拉图,它的充要条件是在 G 中任何一个顶点的 度数为偶数。

定理 2:一个连通图有欧拉迹当且仅当它最多有两个奇点[11]

定理 3:设 C 是一条经过赋权连通图 G 的每条边至少一次的回路,则 C 是的最优回路, 当且仅当 C 对应的欧拉图 G* 满足:

上一篇:一类带避难效应的捕食食饵模型的稳定性分析
下一篇:基于BDI模型的网民行为建模仿真研究

近五年浙江省高考数列问题专题研究

浅谈中学数学函数最值问题的求解方法

浙江省近五年高考数列问题研究

函数背景下的不等式问题

近五年浙江省高考数列问题专题探究

几何画板在探究轨迹问题中的应用

数学问题情境的呈现方式...

我国风险投资的发展现状问题及对策分析

麦秸秆还田和沼液灌溉对...

ASP.net+sqlserver企业设备管理系统设计与开发

新課改下小學语文洧效阅...

老年2型糖尿病患者运动疗...

互联网教育”变革路径研究进展【7972字】

安康汉江网讯

张洁小说《无字》中的女性意识

网络语言“XX体”研究

LiMn1-xFexPO4正极材料合成及充放电性能研究