离散数学：6-2 特殊的图

请交作业五P116:21,22,23,24P137:1,4,5,8P138:12,13,14,15,18,19,20P154:4,5,8P155:16,18

作业讲评四P115:13P116:14,15P115:13x1x2z3z2z1y1y2FGF

∘GP116:14abcdeP116:15对任意非空集合S，P(S)-{}是S的非空子集族，那么P(S)-{}能否构成S的划分？例：设S={1,2}P(S)={,{1},{2},{1,2}}P(S)-{}={{1},{2},{1,2}}——不是划分例：设S={1}P(S)={,{1}}P(S)-{}={{1}}——是划分所以若|S|>1时，P(S)-{}不构成S的划分补充题设R、S是对称的，试给出R∘S不是对称的例子；

R={<1,2>,<2,1>},S={<1,1>}R∘

S={<1,2>}设

R、S是反对称的，试给出R∘S不是反对称的例子。R={<2,1>,<2,2>},S={<1,2>,<2,2>}

R∘S={<1,1>,<1,2>,<2,1>,<2,2>}第6章特殊的图

6.1二部图6.2欧拉图6.3哈密顿图6.4平面图

哈密顿周游世界问题1859年，数学家哈密顿发明了一个周游世界的游戏：在一个实心的正十二面体，每面是一个正五边形。共计20个顶点标上世界著名大城市的名字，要求游戏者从某一城市出发，遍历各城市一次，最后回到原地。周游世界问题——即找一条经过所有顶点(城市)的回路。6.3哈密顿图哈密顿回路:经过图中所有顶点一次且仅一次的回路.哈密顿图:具有哈密顿回路的图.哈密顿通路:经过图中所有顶点一次且仅一次的通路.半哈密顿图:具有哈密顿通路而无哈密顿回路的图.

几点说明：平凡图是哈密顿图.哈密顿回路是初级回路.哈密顿通路是初级通路，环与平行边不影响图的哈密顿性.下列图中哪些是哈密顿图？半哈密顿图?(1)是哈密顿图;(2)是哈密顿图;(3)是半哈密顿图.(4)既不是哈密顿图,也不是半哈密顿图.

无向哈密顿图的一个必要条件

定理：设无向图G=<V,E>是哈密顿图,则对V1V且V1,均有p(GV1)|V1|.

证：设C为G中任一条哈密顿回路,(1)当

V1中顶点在C上均不相邻时，

p(CV1)=|V1|(2)当

V1中顶点在C中有彼此相邻时，p(CV1)<|V1|所以，有p(CV1)|V1|.

又因为CG,故p(GV1)

p(CV1)

|V1|.

无向哈密顿图的一个必要条件

由定理知,

Kr,s当sr+1时不是哈密顿图.而Kr,r+1是半哈密顿图.当r2时,Kr,r是哈密顿图,哈密顿图的必要条件：p(GV1)|V1|实例1设G为n阶无向连通简单图,若G中有割点或桥,则G不是哈密顿图.证:

设v为割点,删除结点v，图成为不连通的，且至少有两个连通分支。则p(Gv)2>|{v}|=1.

根据定理,G不是哈密顿图.

(2)如果G中有桥，则该桥的一个端点是割点。可以归结为G中有割点的情况。所以G也不是哈密尔顿图。

哈密顿图的必要条件：p(GV1)|V1|vv实例2

下图为彼得森图。它满足定理的条件，在删除任意一个或两个顶点，仍是连通的；删除3个顶点，最多只能得到有两个连通分支的子图；删除4个顶点，最多只能得到有3个连通分支的子图；删除≥5个顶点，余下子图的顶点数都不大于5，故必不能有5个以上的连通分支数，所以，满足p(G-S)|S|。但此图是典型的非哈密尔顿图!哈密顿图的必要条件：p(GV1)|V1|无向哈密顿图的一个必要条件

定理：设无向图G=<V,E>是哈密顿图,则对V1V且V1,均有p(GV1)|V1|.几点说明即满足此定理条件的图不一定是哈密顿图，而不满足此定理条件的图一定不是哈密顿图。无向哈密顿图的一个充分条件

定理

设G是n阶无向简单图,若任意两个不相邻的顶点的度数之和大于等于n1,则G中存在哈密顿通路.

d(u)+d(v)≥n-1(u,v

不相邻)推论当n3时,若任意两个不相邻的顶点的度数之和大于等于n,则G中存在哈密顿回路.

d(u)+d(v)≥n(u,v不相邻)说明：

定理中的条件是存在哈密顿通路(回路)的充分条件,但不是必要条件.哈密顿通路(回路)的存在性下图有6个结点，任意两个结点度数的和小于5，但图中存在一条哈密顿通路。下图也有6个结点，任意两个结点度数的和小于6，但图中存在一条哈密顿回路。判断某图是否为哈密顿图至今还是一个难题!

判断是否是哈密顿图的可行方法观察出一条哈密顿回路例如：右图(周游世界问题)中红边给出一条哈密顿回路,故它是哈密顿图。满足充分条件如当n3时,Kn中任意两个不相邻顶点u,v,均有d(u)+d(v)=2(n1)

n,所以Kn为哈密顿图.不满足必要条件

如Kr,r+1不满足p(GV1)|V1|.所以,不是哈密顿图哈密顿通路(回路)的存在性判断无向哈密顿图的必要条件无向哈密顿图的充分条件必定是哈密顿图必定不是哈密顿图不能确定是否是哈密顿图

应用实例——圆桌排座问题某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？解：作无向图G=<V,E>,其中

V={v|v为与会者}，

E={(u,v)|u,vV,u与v有共同语言,且uv}.G为简单图.根据条件,vV,d(v)4.于是，u,vV,有d(u)+d(v)8.由定理可知G为哈密顿图.服务员可在G中找一条哈密顿回路，按它的相邻关系安排座位即可.哈密顿图的实质是能将图中所有的顶点排在同一个圈中哈密顿回路的应用——格雷码000100101111110010011001n=5时,需要计算12个权值.n=25时,需要计算24!/23.11023个权值.如果计算每个哈密顿回路权值需要1ns,共需1千万年才能全部算完,找到权值最小的哈密顿回路.货郎担问题（旅行商问题）TravelingSalesmanProblem——TSP

一个货郎需要经过n个城镇,然后回到出发点.已知每两个城镇之间的距离,这个货郎应如何选择路线,经过每个城镇一次且仅一次,并且总的行程最短?算法:求每一条哈密顿回路的总权值,然后从中找出最小值.对于n个顶点的完全图有

(n-1)!条不同的哈回路.同构意义下,需要计算(n-1)!/2个权值.货郎担问题（旅行商问题）TravelingSalesmanProblem——TSP

以往世界解决TSP问题的情况6.4平面图——引例1考虑把三座房屋与三种设施(水、电、煤气)每种都连接起来的问题：能否使得连接线路不交叉?经简化变为:能否画出K3,3使得没有两条边发生交叉？

平面图——引例2在许多实际问题中，往往会涉及图的可平面化问题，如：电路设计经常要考虑布线是否可以避免交叉以减少元件间的互感影响----单层印刷电路板布线问题;为安全起见，建筑物的地下水管、煤气管、电缆线等不能交叉。平面图和平面嵌入

定义

如果能将图G除顶点外边不相交地画在平面上,则称G是平面图.这个画出的无边相交的图称作G的平面嵌入.没有平面嵌入的图称作非平面图.

完全图K3是平面图完全图K4是平面图K2,3是平面图平面图和平面嵌入设GG,若G为平面图,则G也是平面图;设GG,若G为非平面图,则G也是非平面图.K5和K3,3是非平面图Kn(n5),K3,n(n3)都是非平面图.平行边与环不影响图的平面性.

K5K3,3平面图的面与次数设G是一个平面嵌入，G的面:由G的边将平面划分成的每一个区域。无限面(外部面):面积无限的面,用R0表示。有限面(内部面):面积有限的面,用R1,R2,…,Rk表示。面Ri的边界:包围Ri的所有边构成的回路组。面Ri的次数:Ri边界的长度，用deg(Ri)表示。说明:构成一个面的边界的回路组可能是初级

回路、简单回路,也可能是复杂回路,

甚至还可能是非连通的回路之并.R0R3R2R1上图共有4个面：deg(R1)=1deg(R2)=3deg(R3)=2deg(R0)=8右图和左图是同构的。

R0:外部面(左图),内部面(右图)R1:内部面(左图),外部面(右图)其实，在平面嵌入中可把任何面作为外部面.平面图的面与次数R0R1R2R1R2R0平面图的面与次数定理

在一个平面图G中，所有面的次数之和等于边数m的2倍.其中，r为面数。说明G中每条边无论作为两个面的公共边界，还是作为一个面的边界，在算总次数时都计算两次。极大平面图

定义若G是简单平面图,并且在任意两个不相邻的顶点之间加一条新边所得图为非平面图,则称G为极大平面图.若简单平面图中已无不相邻顶点，则是极大平面图。3个图都是平面图,但只有右边的图为极大平面图.

极大平面图的性质

K3是极大平面图K4是极大平面图n(n3)阶极大平面图Ri=3若简单平面图中已不相邻顶点，则是极大平面图。如K1、K2、K3、K4都是极大平面图。极大平面图必连通。任何n(n3)阶极大平面图不可能有割点和桥。若G为n(n3)阶极大平面图，则G每个面的次数均为3.任何n(n4)阶极大平面图G均有(G)3。极小非平面图

定义

若G是非平面图,并且任意删除一条边所得图都是平面图,则称G为极小非平面图.说明:

K5

是极小非平面图

K3,3是极小非平面图极小非平面图必为简单图K3,3K5欧拉公式证：对边数m做归纳证明.

m=0,G为平凡图,n=1,r=1.1-0+1=2，结论为真.

设m