3--连通且基本9--连通线图是哈密尔顿连通图的开题报告

精品文档---下载后可任意编辑3--连通且基本 9--连通线图是哈密尔顿连通图的开题报告1. 引言在图论中，哈密尔顿图是一种具有特别性质的有向或无向图，其中一条经过每个节点且不重复的哈密尔顿路径称为哈密尔顿路径，哈密尔顿路径构成哈密尔顿回路，则称该图为哈密尔顿图。哈密尔顿图是图论中一个重要的讨论方向，它既具有理论讨论价值，又有广泛的应用。在实际问题中，哈密尔顿图常常被用来描述路线规划、电路设计和网络规划等问题。2. 相关概念（1）连通图：在无向图中，假如从顶点 u 到顶点 v 有路径相连，则称 u 和 v 是连通的；若无向图的任意两个顶点之间都是连通的，则称该图为连通图。（2）线图：将无向图的每一条边替换为一对没有公共顶点的有向边所得到的图称为线图。（3）基本 9--连通线图：假如线图的每个顶点的入度和出度之和都不小于 9，则称该线图是基本 9--连通的。（4）哈密尔顿图：在一个图中，存在一条遍历该图所有顶点恰好一次的路径，则称该图是哈密尔顿图。3. 结论若一个无向图为连通且基本 9--连通的线图，则该无向图为哈密尔顿连通图。证明：设 G 是一个连通且基本 9--连通的线图，我们要证明 G 是一个哈密尔顿连通图，即存在一条遍历所有顶点的路径。从 G 中任取一个顶点 v0，由于 G 是连通的，因此存在一条连通 v0的路径。设 v1,v2,…,vk 均属于该路径，并且与 vk 相邻的点是 vk+1，那么 vk 与 vk+1 之间的边由于基本 9--连通的性质，就可以沿着这条边走到 vk+1。精品文档---下载后可任意编辑假设从 v0 开始，一直沿着这样的方式行走，走到了 vk，但是无法找到一条可以走的边去到 vk+1，此时 vk 一定还有出边没有走过。我们设 vk 的出边分别是 e1,e2,…,em，且这些边指向的顶点是 u1,u2,…,um。由于 G 是基本 9--连通的线图，所以每个顶点的出度不小于 9，因此vk 的出边只是 vk 点出度的一部分，那么除了这 m 条边，在 vj 中 vj 的出度还至少有 9-m 个顶点没有连接。因此，对于 vk 的每一条出边 ei，都存在一条从 ui 到 vj（vj 不等于vk）的路径。为了避开走重复的路径，我们只考虑从 ui 到 vj 的最短路径。将这些最短路径根据 vj 排列，得到一列顶点序列：v1,v2,v3,…,vk,u1,vj1,vj2,…,vjm,vk+1其中，vj1,vj2,…,vjm 代表 vk 的出边。这样的顶点序列可能存在一些顶点相同的情况，但不妨认为它们是不同的。我们考虑从这个顶点序列构建一...