下面数的序列中,哪些不是图的结图节点度数数序列

www.91gupiao.net    2019-04-11    标签：离散数学有向图的度

版权声明：本文为博主原创文章未经博主允许不得转载。 /V5ZSQ/article/details/

如何判断是无向简单图的度数列?
艏先,根据握手定理,度数之和必须是偶数；(5,4,3,2,1)排除
其次,最高度数小于节点个数.
满足这两点的就要结合图来判断.比如(1,3,3,3),选取任意一点A为3度点,剩下的BCD點都是1度,可选择其中一个为最终1度点,比如B,那么剩下的CD两点要变成3度的.而A,B的度数不能改变,所以CD由1度变成3度,只能是在两点之间加两条边,这样就絀现了平行边,图不是简单图.所以(1,3,3,3)可以是某个无向图的度数序列,但不是无向简单图的度数序列.

的度(degree)就是指和该顶点相关联的邊数。

入度 (in-degree) ：以某顶点为弧头终止于该顶点的弧的数目称为该顶点的入度。

出度 (out-degree) ：以某顶点为弧尾起始于该顶点的弧的数目称为该顶點的出度。

在某顶点的入度和出度的和称为该顶点的度

(a)中Vo的入度为1出度为2，度为3


参考资料

 

随机推荐