(10)设D=<V,A>是有向图,u,v∈V,a∈A,如果a=<u,v>,则称u邻接到v,或v邻接于u,并称顶点u和v与弧a相关联.
定义8.1.5 设G=<V,E>是无向图,v∈V,若在G中共有k个环,ι条非环的边与v相关联,则称数2k+ι为顶点v的度,记为d
G
(v),或简记为d(v).
设D=<V,A>是有向图,v∈V,如果在D中共有k条弧以v为始点,有ι条弧以v为终点,则分别称k和ι为顶点v的出度与入度,并相应记为
或简记为d
+
(v),d
-
(v).定义
称d
D
(v)为顶点v的度.显然d
D
(v)亦是v在D的基础图中的度.
以下定理常被称为握手引理.
定理8.1.1 设G=<V,E>是一无向图,