离散数学专题知识点讲解.ppt

CS|SWUSTXDC离散数学专题知识点讲解第1页，共21页，星期日，2025年，2月5日*专题一：图论基础问题知识点讲解该材料用于图论第2讲课知识点讲解环节第2页，共21页，星期日，2025年，2月5日在无向图G＝V，E中，与结点v(v?V)关联的边的条数（有环时计算两次），称为该结点的度数，记为deg(v)；结点的度数（次数）在有向图G＝V，E中，以结点v为始点引出的边的条数，称为该结点的出度,记为deg+(v)；以结点v为终点引入的边的条数，称为该结点的入度,记为deg-(v)；而结点的引出度数和引入度数之和称为该结点的度数，记为deg(v)，即deg(v)＝deg+(v)+deg-(v)；第3页，共21页，星期日，2025年，2月5日对于图G＝V，E，度数为1的结点称为悬挂结点，它所关联的边称为悬挂边。在图G＝V，E中，称度数为奇数的结点为奇度数结点，度数为偶数的结点为偶度数结点。结点的度数（次数）v5是悬挂结点，v1，v5为悬挂边。第4页，共21页，星期日，2025年，2月5日度数序列设V＝{v1,v2,…,vn}为图G的结点集，称(deg(v1),deg(v2),…,deg(vn))为G的度数序列。上图的度数序列为（3,3,5,1,0）。第5页，共21页，星期日，2025年，2月5日（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个结点。第6页，共21页，星期日，2025年，2月5日握手定理在无向图G＝V，E中，则所有结点的度数的总和等于边数的两倍，即：在有向图G＝V，E中，则所有结点的引出度数之和等于所有结点的引入度数之和，所有结点的度数的总和等于边数的两倍，即：第7页，共21页，星期日，2025年，2月5日推论在图G＝V，E中，其V＝{v1,v2,v3,…,vn}，E＝{e1，e2，……，em}，度数为奇数的结点个数为偶数。证明设V1＝{v|v?V且deg(v)＝奇数}，V2＝{v|v?V且deg(v)＝偶数}。显然，V1∩V2＝Φ，且V1∪V2＝V，于是有：由于上式中的2m和(偶数之和为偶数)均为偶数，因而也为偶数。于是|V1|为偶数(因为V1中的结点v之deg(v)都为奇数)，即奇度数的结点个数为偶数。■第8页，共21页，星期日，2025年，2月5日度数序列设V＝{v1,v2,…,vn}为图G的结点集，称(deg(v1),deg(v2),…,deg(vn))为G的度数序列。上图的度数序列为（3,3,5,1,0）。第9页，共21页，星期日，2025年，2月5日（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个结点。度数序列第10页，共21页，星期日，2025年，2月5日子图定义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的导出子图。第11页，共21页，星期日，2025年，2月5日 在如图中，给出了图G以及它的真子图G和生成子图G。G是结点集{v1，v2，v3，v4，v5}的导出子图。显然，每个图都是它自身的子图。子图第12页，共21页，星期日，2025年，2月5日完全图设G＝V,E为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。设G＝V,E为一个具有n个结点的有向简单图，若对于任意u,v?V(u?v)，既有