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

1、定义了第九届：哈磨粉机顿图、图的矩阵表示、4.4平面图、4.4平面图、4.4.1平面图的基本概念，将4.4.1方向图g称为平面图，如果g能在一个平面上图示，则各边只在顶点相交。 否则将g称为非平面图。、2为平面连通图，由图的边包围的最小平面子摇滾乐，其内部不包含图的节点，也不包含图的边，平面图g的区域。 包含该区域的各边构成的环称为该区域的边界，区域面积有限的区域称为有限区域，在其他情况下称为无限区域。 定理1是将g作为一平面连通图，将n作为其顶点数，将m作为其边数，将r作为其区域数，则n m r=2，n m r=2，n=8，m=12，r=6，812=2，n m r=2，n=20，m=30，

2、设r=12 20 30 12=2，定理2g为平面连通简单图，其顶点数为n3，其边数为m，则m 3n 6、m=10、3n-6=9、m=9、3n-6=12，定义3为一个格拉夫G=(V，e )，在几条边(vi1，vj1 )、(vi1，vj2)、(vi2，VI 3，VI4)中，n为整数，n为整数。 vjk )将删除节点vi1和vj1、vik和vjk合并，并置换为新的节点w1、w2、wk，将所得到的新的格拉夫G=(V，e )称为格拉夫g的基本削减。 克拉托斯牛鼻子定理，定理3 (克拉托斯牛鼻子定理)图g是平面图，仅通过g的子图不能缩小为下面的两个图(K5和k3，3 )。 二部格拉夫，定义4无向图G=(V

3、，e )被称为二部格拉夫，若有非空的集合V1，V2，则设定V1V2=V，V1V2=，对于各lE，l=(vi，vj )，vi V1，vjV2。 此时，对于将二部格拉夫设为G=(V1，e，V2 )、以及定理4将无向图g设为二部格拉夫的一盏茶条件是g具有至少两个顶点，并且其所有环的长度是双位数。 定义G=(V1、e、V2)为二部分格拉夫、ME。 m是被称为g的匹配，m的任何边都没有共同的端点的情况。 在g的全匹配中边缘数最多的匹配称作最大匹配(maximal matching )。 如果V1(V2)的任何顶点与m边的端点重合，则m称为V1(V2)-完全匹配。 如果m是V1-完全匹配或V2-完全匹配，

4、则m称为g的完全匹配。 将G=(V1、e、V2)、m作为g的匹配。 (1)M中边的端点称为M-顶点，其他顶点称为非M-顶点。 (2)在g中从vk到vl的路径p称为交替链，p的起点vk和终点vl为非M-顶点，在该边的系列中非匹配边和匹配边交替出现(因此，首尾两侧必定为非匹配边，除顶点vk、vl以外的各顶点为M-顶点)。 特别是在一边(v，v )的两端为非M-顶点的情况下，路径(v，v )也称为交替链。 定义6，图G=(V1、e、V2)。 g需要V1-完全匹配的条件是，每个SV1都有N(S) S，其中N(S )是s中的节点相邻的节点集合. N(S) V2这一定理是霍尔在1935年证明的，多称为霍尔结婚的有名定理。 定理5，求最大匹配的匈牙利算法：第9回：哈磨粉机图，图的行列表现，4.5树，4.5.1树及其基本性质，4.5.1连通无回路的无向图称为无向树，简单称为树(tree )。 树中的悬挂点(次数为1的节点)称为叶，其他节点称为早午餐节点。 单个孤立节点称为空树。 各连通枝都是树的图是森林(forest )，树也是森林、树、天空的树、森林、树和森林这两个图。 树木和森林是平面