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相邻的点是vk1，那么vk与vk1之间的边由于基本9--连通的性质，就可以沿着这条边走到vk1。 假设从v0开始，一直沿着这样的方式行走，走到了vk，但是无法找到一条可以走的边去到vk1，此时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,vk1 其中，vj1,vj2,,vjm 代表 vk 的出边。这样的顶点序列可能存在一些顶点相同的情况，但不妨认为它们是不同的。 我们考虑从这个顶点序列构建一条遍历G所有顶点的路径。首先，从v0出发到达v1，然后从v1走到v2，以此类推，最后走到vk。接下来，我们沿着上述的路径，走过每一条从vk到ui的最短路径，到达uj，然后重复上述步骤，一直到vk1。由于vj只出现在 vj1,vj2,,vjm 并且其他部分的顶点只出现一次，因此整条路径遍历了图G所有的顶点，即为哈密尔顿路径。 综上所述，连通且基本9--连通线图是哈密尔顿连通图。