离散数学专题知识点讲解

离散数学专题知识点讲解第一页，共二十一页，2022年，8月28日16二月2023专题一：图论基础问题知识点讲解该材料用于图论第2讲课知识点讲解环节第二页，共二十一页，2022年，8月28日在无向图G＝<V，E>中，与结点v(vV)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；结点的度数（次数）在有向图G＝<V，E>中，以结点v为始点引出的边的条数，称为该结点的出度,记为deg+(v)；以结点v为终点引入的边的条数，称为该结点的入度,记为deg-(v)；而结点的引出度数和引入度数之和称为该结点的度数，记为deg(v)，即deg(v)＝deg+(v)+deg-(v)；第三页，共二十一页，2022年，8月28日对于图G＝<V，E>，度数为1的结点称为悬挂结点，它所关联的边称为悬挂边。在图G＝<V，E>中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。结点的度数（次数）v5是悬挂结点，<v1，v5>为悬挂边。第四页，共二十一页，2022年，8月28日度数序列设V＝{v1,v2,…,vn}为图G的结点集，称(deg(v1),deg(v2),…,deg(vn))为G的度数序列。上图的度数序列为（3,3,5,1,0）。第五页，共二十一页，2022年，8月28日（3,3,2,3），（5,2,3,1,4）能成为图的度数序列吗？为什么？已知图G中有10条边，4个度数为3的结点，其余结点的度数均小于等于2，问G中至少有多少个结点？为什么？度数序列解1）由于这两个序列中，度数为奇数的结点个数均为奇数，由握手定理的推论知，它们都不能成为图的度数序列。2）图中边数为10，由握手定理知，G中所有结点的度数之和为20，4个度数为3的结点占去12度，还剩下8度。若其余全是度数为2的结点，还需要4个结点来占用这8度，所以G至少有8个结点。第六页，共二十一页，2022年，8月28日握手定理在无向图G＝<V，E>中，则所有结点的度数的总和等于边数的两倍，即：在有向图G＝<V，E>中，则所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：第七页，共二十一页，2022年，8月28日推论在图G＝<V，E>中，其V＝{v1,v2,v3,…,vn}，E＝{e1，e2，……，em}，度数为奇数的结点个数为偶数。证明设V1＝{v|vV且deg(v)＝奇数}，V2＝{v|vV且deg(v)＝偶数}。显然，V1∩V2＝Φ，且V1∪V2＝V，于是有：由于上式中的2m和(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。■第八页，共二十一页，2022年，8月28日度数序列设V＝{v1,v2,…,vn}为图G的结点集，称(deg(v1),deg(v2),…,deg(vn))为G的度数序列。上图的度数序列为（3,3,5,1,0）。第九页，共二十一页，2022年，8月28日（3,3,2,3），（5,2,3,1,4）能成为图的度数序列吗？为什么？已知图G中有10条边，4个度数为3的结点，其余结点的度数均小于等于2，问G中至少有多少个结点？为什么？解1）由于这两个序列中，度数为奇数的结点个数均为奇数，由握手定理的推论知，它们都不能成为图的度数序列。2）图中边数为10，由握手定理知，G中所有结点的度数之和为20，4个度数为3的结点占去12度，还剩下8度。若其余全是度数为2的结点，还需要4个结点来占用这8度，所以G至少有8个结点。度数序列第十页，共二十一页，2022年，8月28日子图定义8.7

设有图G＝<V,E>和图G'＝<V',E'>。若V'V，E'E，则称G'是G的子图，记为G'G。若G'G，且G'≠G（即V'V或E'E），则称G'是G的真子图，记为G'G。若V'=V，E'E，则称G'是G的生成子图。设V"V且V"≠，以V"为结点集，以两个端点均在V"中的边的全体为边集的G的子图称为V"导出的G的子图，简称V"的导出子图。第十一页，共二十一页，2022年，8月28日

在如图中，给出了图G以及它的真子图G'和生成子图G"。G'是结点集{v1，v2，v3，v4，v5}的导出子图。显然，每个图都是它自身的子图。子图第十二页，共二十一页，2022年，8月28日完全图设G＝<V,E>为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。设G＝<V,E>为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边<u,v>，又有有向边<v,u>，则称G为有向完全图，在不发生误解的情况下，也记为Kn。第十三页，共二十一页，2022年，8月28日完全图无向的简单完全图K3，K4，K5和有向的简单完全图K3。无向完全图Kn的边数为=

n(n-1)，有向完全图Kn的边数为=n(n-1)。第十四页，共二十一页，2022年，8月28日改变才能更好的生存！29--15补图设G＝<V，E>为具有n个结点的简单图,从完全图Kn中删去G中的所有边而得到的图称为G相对于完全图Kn的补图，简称G的补图，记为G。这里，当G为有向图时，则Kn为有向完全图：当G为无向图时，则Kn为无向完全图显然，G与G互为补图，即G=G。第十五页，共二十一页，2022年，8月28日改变才能更好的生存！29--16补图第十六页，共二十一页，2022年，8月28日图的同构图的同构：设两个图G=<V,E>和G'=<V',E'>，如果存在双射函数g：V→V'，使得对于任意的e=(vi,vj)（或者<vi,vj>）∈E当且仅当e'=(g(vi),g(vj))（或者<g(vi),g(vj)>）∈E'，并且e与e'的重数相同，则称G与G'同构，记为G≌G'。第十七页，共二十一页，2022年，8月28日图的同构

容易验证：G1≌G2，结点之间的对应关系为：a→v1，b→v2，c→v3，d→v4，e→v5；G3≌G4；G5≌G6；但G7与G8不同构。图G5称为彼得森图。第十八页，共二十一页，2022年，8月28日两个图同构的必要条件结点数目相同；边数相同；度数相同的结点数相同。注意：这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。yxuvxyvu若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，一个图可以变形为另一个图，那么这两个图是同构的。图的同构第十九页，共二十一页，2022年，8月28日图论里的图要比欧几里得几何学里的图抽象得多。由于它描绘的是事物之间的某种“关系”，而不是事物的几何形状，因此它不在乎图形的外形与大小，更不涉及长度、面积、体积、角度等这些量，它只包含顶点和边这两种要素，用这