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

离散数学专题知识点讲解
现在学习的是第1页，共21页
*
专题一：图论基础问题
知识点讲解
该材料用于图论第2讲课知识点讲解环节
现在学习的是第2页，共21页
在无向图G＝<V，E>中，与结点v(vV)关联的边的点个数为偶数。
证明设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页
度数序列
设V＝{v1, v2,…,vn}为图G的结点集，称(deg(v1),deg(v2),…,deg(vn))为G的度数序列。
上图的度数序列为（3,3,5,1,0）。
现在学习的是第9页，共21页
（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页
子图
设有图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页
在如图中，给出了图G以及它的真子图G'和
生成子图G" 。G'是结点集{v1，v2，v3，v4，v5}
的导出子图。
　　显然，每个图都是它自身的子图。
子图
现在学习的是第12页，共21页
完全图
设G＝<V,E>为一个具有n个结点的无向简单图，如果G中任一个结点都与其余n-1个结点相邻接，则称G为无向完全图，简称G为完全图，记为Kn。
设G＝<V,E>为一个具有n个结点的有向简单图，若对于任意u,vV(uv)，既有有向边<u,v>，又有有向边<v,u>，则称G为有向完全图，在不发生误解的情况下，也记为Kn。
现在学习的是第13页，共21页
完全图
无向的简单完全图K3，K4，K5和有向的简单完全图K3。
无向完全图Kn的边数为　=　n(n-1)，有向完全图Kn的边数为　= n(n-1)。
现在学习的是第14页，共21页
改变才能更好的生存！
29--*
补图
设G＝<V，E>为具有n个结点的简单图,
从完全图Kn中删去G中的所有边而得到的图
称为G相对于完全图Kn的补图，简称G的补
图，记为G。
　　这里，当G为有向图时，则Kn为有向完
全图：当G为无向图时，则Kn为无向完全图
显然，G与G互为补图，即G=G。
现在学习的是第15页，共21页
改变才能更好的生存！
29--*
补图
现在学习的是第16页，共21页
图的同构
图的同构：设两个图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'。
现在学习的是第17页，共21页
图的同构
容易验证：G1≌G2，结点之间的对应关系为：a→v1，b→v2，c→v3，d→v4，e→v5；G3≌G4；G5≌G6；但G7与G8不同构。图G5称为彼得森图。
现在学习的是第18页，共21页
两个图同构的必要条件
结点数目相同；
边数相同；
度数相同的结点数相同。
注意：这三个条件并不是充分条件。例如下面两个图满足这三个条件，但它们不同构。
y
x
u
v
x
y
v
u
若图的结点可以任意挪动位置，而边是完全弹性的，只要在不拉断的条件下，一个图可以变形为另一个图，那么这两个图是同构的。
图的同构
现在学习的是第19页，共21页
图论里的图要比欧几里得几何学里的图抽象得多。
由于它描绘的是事物之间的某种“关系”，而不是事