离散数学专题知识点讲解PPT课件

1、1) 在无向图G中，与结点v(vV)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；结点的度数 （次数）1)在有向图在有向图G中，以结点中，以结点v为始点引出的边的条数，称为该为始点引出的边的条数，称为该结点的结点的出度出度,记为记为deg+(v)；以结点；以结点v为终点引入的边的条数，称为该为终点引入的边的条数，称为该结点的结点的入度入度,记为记为deg-(v)；而结点；而结点的引出度数和引入度数之和称为的引出度数和引入度数之和称为该结点的该结点的度数度数，记为，记为deg(v)，即，即deg(v)deg+(v)+deg-(v)；第1页/共23页1) 对于图G，度数为1

2、的结点称为悬挂结点，它所关联的边称为悬挂边。2) 在图G中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。结点的度数 （次数）v5v5是悬挂结点，是悬挂结点，v1v5为悬挂边。为悬挂边。第2页/共23页度数序列设Vv1, v2,vn为图G的结点集，称(deg(v(deg(v1 1),deg(v),deg(v2 2),),deg(v,deg(vn n)为为G G的的度数序列度数序列。上图的度数序列为（上图的度数序列为（3,3,5,1,03,3,5,1,0）。）。第3页/共23页1) （3,3,2,3），（5,2,3,1,4）能成为图的度数序列吗？为什么？2) 已知图G中有10条边

3、，4个度数为3的结点，其余结点的度数均小于等于2，问G中至少有多少个结点？为什么？度数序列解解1 1）由于这两个序列中，由于这两个序列中，度数为奇数的结点个数度数为奇数的结点个数均为奇数，由握手定理均为奇数，由握手定理的推论知，它们都不能成为图的度数序列。的推论知，它们都不能成为图的度数序列。2 2）图中边数为图中边数为1010，由握手定理知，由握手定理知，G G中所有结点的度数之和为中所有结点的度数之和为2020，4 4个度数个度数为为3 3的结点占去的结点占去1212度，还剩下度，还剩下8 8度。若其余全是度数为度。若其余全是度数为2 2的结点，还需要的结点，还需要4 4个结点来占用这个结

4、点来占用这8 8度，所以度，所以G G至少有至少有8 8个结点。个结点。第4页/共23页握手定理1. 在无向图G中，则所有结点的度数的总和等于边数的两倍，即：；m2)vdeg(Vv ，m)v(deg)v(degVvVv 2.2.在有向图在有向图G GVE中，则所有结点的引出度数之和等于所有结点的引中，则所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：入度数之和，所有结点的度数的总和等于边数的两倍，即：。m2)v(deg)v(deg)vdeg(VvVvVv 第5页/共23页推论在图G中，其Vv1,v2,v3,vn，Eee1 1，e e2 2，e em m

5、 ，度数为奇数的结点个数为偶数。，度数为奇数的结点个数为偶数。证明证明设设V V1 1v|vv|v V V且且deg(v)deg(v)奇数奇数 ，V V2 2v|vv|v V V且且deg(v)deg(v)偶数偶数 。显。显然，然，V V1 1VV2 2，且，且V V1 1VV2 2V V，于是有：，于是有：。m2)vdeg()vdeg()vdeg(21VvVvVv 由于上式中的由于上式中的2m2m和和( (偶数之和为偶数偶数之和为偶数) )均为偶数，因而也为偶数。于是均为偶数，因而也为偶数。于是|V|V1 1| |为偶数为偶数( (因为因为V V1 1中的结点中的结点v v之之deg(v)d

6、eg(v)都为奇数都为奇数) )，即奇度数的结点个数为偶数。，即奇度数的结点个数为偶数。第6页/共23页度数序列设Vv1, v2,vn为图G的结点集，称(deg(v1),deg(v2),deg(vn)为G的度数序列。上图的度数序列为（上图的度数序列为（3,3,5,1,03,3,5,1,0）。）。第7页/共23页1) （3,3,2,3），（5,2,3,1,4）能成为图的度数序列吗？为什么？2) 已知图G中有10条边，4个度数为3的结点，其余结点的度数均小于等于2，问G中至少有多少个结点？为什么？解解1 1）由于这两个序列中，由于这两个序列中，度数为奇数的结点个数度数为奇数的结点个数均为奇数，由握

7、手定理均为奇数，由握手定理的推论知，它们都不能成为图的度数序列。的推论知，它们都不能成为图的度数序列。2 2）图中边数为图中边数为1010，由握手定理知，由握手定理知，G G中所有结点的度数之和为中所有结点的度数之和为2020，4 4个度数个度数为为3 3的结点占去的结点占去1212度，还剩下度，还剩下8 8度。若其余全是度数为度。若其余全是度数为2 2的结点，还需要的结点，还需要4 4个结点来占用这个结点来占用这8 8度，所以度，所以G G至少有至少有8 8个结点。个结点。度数序列第8页/共23页子图定义8.7 设有图G和图G。1)若VV，EE，则称G是G的子图，记为GG。2)若GG，且GG

8、（即VV或EE），则称G是G的真子图，记为GG。3)若V=V，EE，则称G是G的生成子图。4)设VV且V，以V为结点集，以两个端点均在V中的边的全体为边集的G的子图称为V导出的G的子图，简称V的导出子图。 第9页/共23页在如图中，给出了图G以及它的真子图G和生成子图生成子图G G 。GG是结点集是结点集vv1 1，v v2 2，v v3 3，v v4 4，v v5 5 的导出子图。的导出子图。显然，每个图都是它自身的子图。显然，每个图都是它自身的子图。 子图子图第10页/共23页完全图1.设G为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简

9、称G为完全图，记为Kn。2.设G为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边，又有有向边，则称G为有向完全图，在不发生误解的情况下，也记为Kn。第11页/共23页完全图无向的简单完全图K3，K4，K5和有向的简单完全图K3。无向完全图无向完全图K Kn n的的边数边数为为= =n(n-1)n(n-1)，有向，有向完全图完全图K Kn n的的边数边数为为= n(n-1)= n(n-1)。 2nP2nC21第12页/共23页改变才能更好的改变才能更好的生存！生存！29-29-1313补图设G为具有n个结点的简单图,从完全图Kn中删去G中的所有边而得到的图称为G相对于完全图

10、Kn的补图，简称G的补图，记为G。这里，当G为有向图时，则Kn为有向完全图：当G为无向图时，则Kn为无向完全图显然，显然，G G与与G G互为补图，即互为补图，即G=GG=G。 第13页/共23页改变才能更好的改变才能更好的生存！生存！29-29-1414补图第14页/共23页图的同构图的同构：设两个图图的同构：设两个图G=和和G=，如果，如果存 在 双 射 函 数存 在 双 射 函 数 g ： V V ， 使 得 对 于 任 意 的， 使 得 对 于 任 意 的 e = ( vi, vj) （ 或 者（ 或 者 ） E 当 且 仅 当当 且 仅 当 e =( g ( vi) , g ( vj

11、) ) （ 或 者（ 或 者 ） E ，并 且并 且 e 与与 e 的 重 数 相 同 ， 则 称的 重 数 相 同 ， 则 称 G 与与 G 同 构同 构 ，记为记为G G。 第15页/共23页图的同构容易验证：G1G2，结点之间的对应关系为：av1，bv2，cv3，dv4，ev5；G3G4；G5G6；但G7与G8不同构。图G5称为彼得森图。 第16页/共23页两个图同构的必要条件1) 结点数目相同；2) 边数相同；3) 度数相同的结点数相同。注意注意：这三个条件并不是充分条件。例如下面两：这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。个图满足这三个条件，但它们不同构

12、。y yx xu uv vx xy yv vu u若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，一个图可以变形为另一个图，那么这两个图是同构的。下，一个图可以变形为另一个图，那么这两个图是同构的。 图的同构图的同构第17页/共23页图论里的图要比欧几里得几何学里的图抽象得多。由于它描绘的是事物之间的某种由于它描绘的是事物之间的某种“关系关系”，而不是事物的几何形状，因此，而不是事物的几何形状，因此它不在乎图形的外形与大小，更不涉及长度、面积、体积、角度等这些量，它不在乎图形的外形与大小，更不涉及长度、面积、体积、角度等这些量，它只包含顶点和边这两种要素，用这两种要素来描绘事物之间的种种关系它只包含顶点和边这两种要素，用这两种要素来描绘事物之间的种种关系就足够了。就足够了。在图论里判断两个图是否相同，就是说是否同构，只要看两个图所描绘的顶点和邻接关系是否相同就行了，而不需要看这两个图的形状、大小是否相同这正是图论里的图和欧几里德几