为重边,所以此图不是简单图. 一条边的两个顶点称为相邻的(adjacent). 若
是边 的一个顶点,则称 和 是关联的(incident). 对于无环图,和 关联的
边的个数称为 的度 (degree),记为 . 对于有环图,环记 2 度. 在图 1 中,
关于顶点度数,我们有下面的基本定理.
定理 1.1.3 设图 的顶点集为 ,且 = , 则
=
推论 1.1.4 图中度为奇数的顶点个数为偶数.
我们称一个图的所有顶点度数的非递增序列为这个图的度序列 (degree
sequence). 例如图 1 的度序列为(5,3,3,2,1). 每个图都有一个度序列;反
之,并非每个非递增序列都为某个图的度序列. 例如(5,4,3,2,1)就不可能是
某个图的度序列,因为定理 1.1.3 告诉我们,一个非递增序列要成为某个图的
度序列,必须先满足序列的元素和为偶数. 其实,这个显然的必要条件也是充
分的.
定理 1.1.5 非负整数 , ,..., 是某个图的所有顶点度数当且仅当
是偶数.
证明 由定理 1.3,显然.
设 . 显然集合 : 是奇 的元素个数为偶数. 将
此集合中元素两两配对,对每个元素对,构造一条边使其端点为此元素对 . 则
此时每个顶点 需要的度数是偶数(非负),在 处加上 (表示数的下
取整,如 )个环,就得到以 为顶点集的图,且 的度为 .
定理 1.5 的证明是构造性的,当然可以用其它方法来证明,例如用归纳法
(对 或 进行归纳),证明留给读者. 定理 1.5 中对度序列的刻画比较
简单是因为允许使用环. 如果不允许使用环, 是偶数的条件就不充分了.
我们在习题中给出无环图度序列的刻画. 关于简单图度序列的刻画以及更多关
于度序列的内容参考[1] .
评论0
最新资源