2016年2月17日星期三
勿在浮沙筑高台!
程序设计领域里,每一个人都想飞
●但是,还没有学会走之前,连怕跑都别想!
2016年2月17日星期三
专题一8圖论害础问题
知识解
该材料用于图论第2讲课知识点讲解环节
结点的度数(次数)
1)在无向图G=<V,E>中,与结点vv∈V)关联的边的条
数(有环时计算两次),称为该结点的度数,记为
deg(v)
叨。1)在有向图G=<V,E>中,以结点y
为始点引出的边的条数,称为该
结点的出度,记为degt(y);以结点v
为终点引入的边的条数,称为该
结点的入度,记为deg(v);而结点
的引出度数和引入度数之和称为
该结点的度数,记为deg(),即
deg(v)=deg+(v)+deg(v);
度数序列
设V={v,v2,n}为图G的结点集,称
(deg(v),deg(v2),…deg(v))为G的度数序列。
上图的度数序列为(3,3,5,1,0)
度数序列
1)(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗?为
什么?
2)已知图G中有10条边,4个度数为3的结点,其余结点
的度数均小于等于2,问G中至少有多少个结点?为什
么?
解1)由于这两个序列中,度数为奇数的结点个数均为
奇数,由握手定理的推论知,它们都不能成为图的度
数序列。
2)图中边数为10,由握手定理知,G中所有结点的度数
之和为20,4个度数为3的结点占去12度,还剩下8度。
若其余全是度数为2的结点,还需要4个结点来占用这8
度,所以G至少有8个结点
离散数学专题1知识点讲解 来自淘豆网m.daumloan.com转载请标明出处.
