【作者】 李丽萍；

【导师】 李胜家；

【作者基本信息】 山西大学 ， 运筹学与控制论， 2005， 硕士

【摘要】 一个图若包含Hamilton圈,则称这个图是Hamilton图。众所周知,一个极大平图是3连通图。判定一个3连通平面图是否是一个Hamilton图,这个问题是NP完备问题。然而,Chvatal和Wigderson也分别证明了判定一个极大平图是否是Hamilton图,这个问题仍是NP完备问题。因此对极大平图的Hamilton性进行研究是有重要意义的。Whitney证明了没有分离三角形的极大平图是Hamilton图(一个分离三角形是指去掉此三角形的三个顶点后使图不连通)。Tutte已经证明了4连通平图是Hamilton图。不含有分离三角形的极大平图是4连通图,因此Tutte的结果可以看作是Whitney结果的一个推广。注意到:一个极大平图若含有分离三角形,则其不是4连通的,因此不能运用Tutte的结果。Chen Chuiyuan证明了仅含有一个分离三角形的极大平图是Hamilton图。本文主要对含有分离三角形的极大平图进行了研究,主要结果叙述如下。 定理3.1若G是含有两个分离三角形的极大平图,则G有一条Hamilton路。 定理3.2若G是含有两个分离三角形的极大平图,且两分离三角形有公共边,则G是Hamilton图。 定理3.3设T是仅含有一个分离三角形的三角剖分图,且至多有七个边界点,则T有一条Hamilton路。更多还原

【Abstract】 A graph is hamiltonian if it contains a hamiltonian cycle. It is well-known that A maximal planar graph with at least four vertices is 3-connected. The problem of determining whether a 3-connected planar graph is hamiltonian is NP-complete and Chvatal and Wigderson also had independently shown that the problem of determining whether a maximal planar graph is hamiltonian is NP-complete. So it is of certain interest that the problem of determining whether a maximal planar graph is hamiltonian. A classical theory of Whitney says that any maximal planar graph with no separating triangles is hamiltonian ( where a separating triangle is a triangle whose removal separates the graph ) . It is well-known that Tutte proved that 4-connected planar graph is hamiltonian. Tutte’s result can be views as a generalization of Whitney’s result since any maximal planar graph with at least five vertices and with no separating triangles is 4-connected. Note that if a maximal planar graph has separating triangles, then it can not be 4-connected and therefore Tutte’s result can not be applied. Chen Chuiyuan had proved that any maximal planar graph with only one separating triangle is still hamiltonian. This paper mainly researchs the maximal planar graph with two separating triangles. The main results are listed as follows:Theorem 3.1 If G is a maximal planar graph with two separating triangles, then G has a hamiltonian path.Theorem 3.2 If G is a maximal planar graph with two separating triangles and two separating triangles has a common edge, then G is hamiltonian.Theorem 3.3 If a triangulation T with only one separating triangle has at most seven boundary vertices, then it has a hamiltonian path.更多还原