离散数学第3章讲义-2.ppt

《离散数学第3章讲义-2.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第九讲:哈密顿图、图的矩阵表示4.4平面图4.4平面图4.4.1平面图的基本概念定义4.4.1无向图G称为平面图（planargraph），如果G可以在一个平面上图示出来，而使各边仅在顶点处相交。否则称G为非平面图。afedcbafedcb定义4.4.2设G是一个平面连通图，由图中的边包围的最小平面块，其内部不包含图的结点，也不包含图的边，称为平面图G的区域（regions）。包含该区域的各边所构成的回路称为这个区域的边界（boundary），区域面积为有限的区域称为有限区域，否则称为无限区域。afedcb（欧拉公

2、式）定理1设G为一平面连通图，n为其顶点数，m为其边数，r为其区域数，那么n–m+r=2n–m+r=2n=8,m=12,r=68–12+6=2n–m+r=2n=20,m=30,r=1220–30+12=2定理2设G为一平面连通简单图，其顶点数n≥3，其边数为m，那么m≤3n–6m=10,3n-6=9m=9,3n-6=12afedcb定义3在一个图G=(V,E)中，将一些边（vi1,vj1)，（vi2,vj2)，，（vik,vjk)，删除将结点vi1与vj1，，vik与vjk合并，用新结点w1，w2,，wk代替

3、，所得的新图G’=(V’,E’)称为图G的基本缩减。库拉托夫斯基定理定理3（库拉托夫斯基定理）图G是平面图，当且仅当对G的任何子图都不可能缩减成下面的两个图（K5及K3,3）。afedcb二部图定义4无向图G=（V，E）称为二部图（bipartitegraph），如果有非空集合V1，V2使V1∪V2=V，V1∩V2=，且对每一lE，l=(vi,vj)，viV1，vjV2。这时将二部图记为G=(V1,E,V2)定理4无向图G为二部图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。定义5设G=(

4、V1，E，V2)为二部图，ME。称M为G的一个匹配（matching），如果M中任何两条边都没有公共端点。G的所有匹配中边数最多的匹配称为最大匹配（maximalmatching）。如果V1(V2)中任一顶点均为匹配M中边的端点，那么称M为V1(V2)-完全匹配(perfectmatching)。若M既是V1-完全匹配又是V2-完全匹配，则称M为G的完全匹配。设G=(V1，E，V2)，M为G的一个匹配。（1）M中边的端点称为M-顶点，其它顶点称为非M-顶点。（2）G中vk到vl的路径P称为交替链，如果P的起点vk

5、和终点vl为非M-顶点，而其边的序列中非匹配边与匹配边交替出现（从而首尾两边必为非匹配边，除顶点vk，vl以外各顶点均为M-顶点）。特别地，当一边（v,v‘）两端点均为非M-顶点，通路（v,v'）亦称为交替链。定义6设图G=(V1，E，V2)。G有V1-完全匹配的充分必要条件是：对每一SV1有N(S)≥S其中N(S)是与S中的结点邻接的结点集合.N(S)V2此定理是霍尔（Hall）于1935年证明的，通常称为霍尔婚姻著名定理。定理5求最大匹配的匈牙利算法:第九讲:哈密顿图、图的矩阵表示4.5树4.5.1

6、树及其基本性质定义4.5.1连通无回路的无向图称为无向树，简称为树（tree）。树中的悬挂点(次数为1的结点)称为树叶（leave），其它结点称为分支结点（branchednode）。单一孤立结点称为空树（nulltree）。诸连通分支均为树的图称为森林（forest），树也是森林树空树森林树和森林都是二部图。树和森林都是平面图，其面数为1。定理1设图T为一树，其顶点数、边数分别是n,m,那么n–m=1或m=n–1证明:用数学归纳法.对n进行归纳n=1时,m=0,定理成立.假设i

7、去一条边,得两个子树,分别为(n1,m1)树和(n2,m2)树,m1=n1-1;m2=n2-1那么m=m1+m2+1=n1-1+n2-1+1=n-1证毕.定理2具有两个以上结点的树至少有两片叶。证明:因为(n,m)树m=n-1所有结点的次数之和为2m=2(n-1)若叶少于2,则分支结点数至少为n-1.因为分支结点的次数大于等于2,则所有结点的次数之和大于2(n-1).矛盾.证毕.定理3命题“（n，m）图T为树”与下列5命题中的每一命题等价：（1）T连通且m=n–1。（2）T无回路且m=n–1。（3）T连通，但删去任

8、一边时便不再连通（T的每一边均为割边）。（4）T无回路，但任意添加边时，T中产生唯一的一条回路。（5）任意两个不同顶点之间有且仅有一条路径。(证明见同济大学书)4.5.2生成树定义2图T称为无向图G的生成树（spanningtree），如果T为G的生成子图且T为树。定理4任一连通图G都至少有一棵生成树。4.5.3有向树定义3在有向图中,如果去掉方向所得到的无