第10章 特殊图last.doc

《第10章 特殊图last.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第10章特殊图10.1欧拉图与哈密顿图10.1.1欧拉图及欧拉路径定义10.1图G称为欧拉图(Eulergraph)，如果图G上有一条经过G的所有顶点、所有边的闭路径，或图G为一个孤立顶点。图G称为欧拉路径(Eulerwalk)，如果图G上有一条起始于一个顶点，经过G所有顶点、所有边而终止于另一顶点的路径。定理10.1无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。有向图G为欧拉图，当且仅当G是弱连通的，并且每个顶点的出度与入度相等。定理10.2无向图G为欧拉路径，当且仅当G连通，并且恰有两个顶点的度是奇数。有向图G为欧拉路径，当且仅当G连通，并且恰有两个顶点的入度与

2、出度不等，它们中一个的出度比入度多1，另一个入度比出度多l。10.1.2哈密顿图及哈密顿通路定义10.2如果无向图G上有一条经过所有顶点的回路，或图G为一个孤立顶点，那么，称图G为哈密顿图(Hamiltongraph)，（也称这一回路为哈密顿回路）。如果无向图G上有一条起始于一个顶点，经过G所有顶点而终止于另一顶点的通路，那么，称图G上有哈密顿通路(Hamiltonpath)。定理10.3设图G为具有n（n≥3）个顶点的简单无向图，如果G的每一对顶点的度数之和都不小于n–1，那么G中有一条哈密顿通路；如果G的每一对顶点的度数之和不小于n，那么G为一哈密顿图。定理10.4当n为不

3、小于3的奇数时，Kn上恰有条互不相同的哈密顿回路；恰有条互相均无公共边的哈密顿回路。定义10.3如果可以用两种颜色对图G的所有顶点着色，每个顶点着一种颜色，并且使得相邻的顶点着不同的颜色，那么，称图G是可2-着色的。定理10.5设图G是可2-着色的。如果G是哈密顿图，那么着两种颜色的顶点数目相等；如果G有哈密顿通路，那么着两种颜色的顶点数目之差至多为一。定理10.5只指出了哈密顿图和哈密顿通路存在的必要条件，它并不充分，很容易作出可2-着色且两种颜色顶点数目相等的图，它却不是哈密顿图。定理10.5用来判定某些图不是哈密顿图或没有哈密顿通路是方便的，但是，它要求图是可2-着色的，

4、这并不是任何图都能满足的。当一个图不可2-着色时，可以在二度顶点所关联的边上添加顶点，使图可以二着色。练习10.11、选择题（1）欧拉图是（　　）A、路径　　B、闭路径C、回路D、通路【答案】：B（2）哈密尔顿图是（　　）A、路径B、闭路径C、回路D、三者都不是【答案】：C（3）设G=(n,m)是欧拉图，则n,m有关系（　　）A、n=mB、n,m的奇偶性必相同C、n,m的奇偶性必相反D、n,m的奇偶性既可相同也可相反【答案】：D2、填空题（1）无向图G有一条欧拉路径，当且仅当。【答案】：G连通且恰有零个或两个奇数度节点。（2）当n为时，Kn必为欧拉图。【答案】：奇数（3）当n为

5、时，Kn必为哈密尔顿图。【答案】：大于2的整数（4）当n为时，n个顶点的树必非欧拉图和哈密尔顿图。【答案】：大于1的整数3、“蚂蚁赛跑问题”：图10.1中，在结点v2，v3上的两只蚂蚁跑过图的所有边（至少一次）到达目标v4，谁花费的时间多？（假设蚂蚁通过每一条边所花费时间相同）。v1v4v5v2v3图10.1【答案】：解.结点v2上的蚂蚁花费的时间多。根据定理10.2，图10.13有一条v3到v4的欧拉路径，即由v3到v4有一条经过图中的每条边一次且仅一次的路径；而要想找一条从v2到v4且经过每条边的拟路径，必有边重复。所以由v3到v4只需经过9条边，从v2到v4所经过的边数必

6、多于9条。4、试作出四个图的图示，使第一个既为欧拉图又为哈密顿图；第二个是欧拉图而非哈密顿图；第三个是哈密顿图却非欧拉图；第四个既非欧拉图也非哈密顿图。【答案】：解.图10.2(a)既为欧拉图又为哈密顿图；(b)是欧拉图而非哈密顿图；(c)是哈密顿图却非欧拉图；(d)既非欧拉图也非哈密顿图。(a)(b)(c)(d)图10.25、像第4题要求的那样对欧拉路径和哈密顿通路作出四个图。【答案】：解.图10.3(a)既有欧拉路径又有哈密顿通路；(b)有欧拉路径而无哈密顿通路；(c)有哈密顿通路却无欧拉路径；(d)既无欧拉路径也无哈密顿通路。（a）(b)(c)(d)图10.36、问n为何

7、种数值时，Kn既是欧拉图又是哈密顿图。问k为何值时，k-正则图既是欧拉图又是哈密顿图。【答案】：解.n为奇数时，Kn既是欧拉图又是哈密顿图。k为大于或等于n/2的偶数时，k-正则图既是欧拉图又是哈密顿图。7、证明：恰有两个奇数度顶点u,v的无向图G是连通的,当且仅当在G上添加边(u,v)后所得的图G*是连通的。【答案】：证.必要性是显然的。设G*是恰有两个奇数度顶点u,v的无向图G添加边（u，v）后所得，且是连通的,那么图G*是一个欧拉图（每一个顶点都是偶数度的连通图），因此G*中删除边（u