特殊图last.docVIP

第10章 特殊图 10.1欧拉图与哈密顿图 10.1.1欧拉图及欧拉路径 定义10.1 图G称为欧拉图(Euler graph)，如果图G上有一条经过G的所有顶点、所有边的闭路径，或图G为一个孤立顶点。图G称为欧拉路径(Euler walk)，如果图G上有一条起始于一个顶点，经过G所有顶点、所有边而终止于另一顶点的路径。 定理10.1 无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。有向图G为欧拉图，当且仅当G是弱连通的，并且每个顶点的出度与入度相等。 定理10.2 无向图G为欧拉路径，当且仅当G连通，并且恰有两个顶点的度是奇数。有向图G为欧拉路径，当且仅当G连通，并且恰有两个顶点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多l。 10.1.2 哈密顿图及哈密顿通路 定义10.2如果无向图G上有一条经过所有顶点的回路，或图G为一个孤立顶点，那么，称图G为哈密顿图(Hamilton graph)，（也称这一回路为哈密顿回路）。如果无向图G上有一条起始于一个顶点，经过G所有顶点而终止于另一顶点的通路，那么，称图G上有哈密顿通路(Hamilton path)。 定理10. 3 设图G为具有n（n≥3）个顶点的简单无向图，如果G的每一对顶点的度数之和都不小于n – 1 ，那么G中有一条哈密顿通路；如果G的每一对顶点的度数之和不小于n，那么G为一哈密顿图。 定理10.4 当n为不小于3的奇数时，Kn上恰有条互不相同的哈密顿回路；恰有条互相均无公共边的哈密顿回路。 定义10. 3 如果可以用两种颜色对图G的所有顶点着色，每个顶点着一种颜色，并且使得相邻的顶点着不同的颜色，那么，称图G是可2-着色的。 定理10. 5 设图G是可2-着色的。如果G是哈密顿图，那么着两种颜色的顶点数目相等；如果G有哈密顿通路，那么着两种颜色的顶点数目之差至多为一。 定理10.5只指出了哈密顿图和哈密顿通路存在的必要条件，它并不充分，很容易作出可2-着色且两种颜色顶点数目相等的图，它却不是哈密顿图。定理10.5用来判定某些图不是哈密顿图或没有哈密顿通路是方便的，但是，它要求图是可2-着色的，这并不是任何图都能满足的。当一个图不可2-着色时，可以在二度顶点所关联的边上添加顶点，使图可以二着色。 练习10.1 1、选择题 （1）欧拉图是（　　） A、路径　　B、闭路径 C、回路 D、通路 【答案】：B （2）哈密尔顿图是（　　） A、路径 B、闭路径 C、回路 D、三者都不是 【答案】：C （3）设G=(n,m)是欧拉图，则n,m有关系（　　） A、n=m B、nm的奇偶性必相同 C、奇偶性必相反 D、n,m的奇偶性既可相同也可相反 【答案】：D 2、填空题 （1）无向图G有一条欧拉，当且仅当 。 【答案】：G连通且有零个或两个奇数度节点。 （2）当n为 时，Kn必为欧拉图。 【答案】：奇数 （3）当n为 时，Kn必为哈密尔顿图。 【答案】：数（4）当n为时，必欧拉图哈密尔顿图。 数、“蚂蚁赛跑问题”：图中，在结点v2，v3上的两只蚂蚁跑过图的所有边（一次）到达目标v4，谁花费的时间多？（假设蚂蚁通过每一条边所花费时间相同）。 图10.1 【答案】：解. 结点v2上的蚂蚁花费的时间多。根据定理10.2，图10.13有一条v3到v4的欧拉路径，即由v3到v4有一条经过图中的每条边一次且仅一次的路径；而要想找一条从v2到v4且经过每条边的拟路径，必有边重复。所以由v3到v4只需经过9条边，从v2到v4所经过的边数必多于9条a)既为欧拉图又为哈密顿图；b)是欧拉图而非哈密顿图；c)是哈密顿图却非欧拉图；d)既非欧拉图也非哈密顿图 图10.2 5、像第4题要求的那样对欧拉路径和哈密顿通路作出四个图。 【答案】：解. 图10.3 (a)既有欧拉路径又有哈密顿通路；(b)有欧拉路径而无哈密顿通路；(c)有哈密顿通路却无欧拉路径；(d)既无欧拉路径也无哈密顿通路。 图10.3 6、问n为何种数值时，Kn既是欧拉图又是哈密顿图。问k为何值时，k-正则图既是欧拉图又是哈密顿图。 【答案】：解. n为奇数时，Kn既是欧拉图又是哈密顿图。k为大于或等于n/2的偶数时，k-正则图既是欧拉图又是哈密顿图。 7、证明：恰有两个奇数度顶点u,v的无向图G是连通的,当且仅当在G上添加边(u,v)后所得的图G*是连通的。 【答案】：证. 必要性是显然的。 设G*是恰有两个