原子価

有向グラフ G=(V,E,s(),t())において頂点v の(単なる)原子価(valance,degree)とはその頂点の内原子価と外原子価の和をいいます。即ち
degree(v)= in-degree(v) + out-degree(v)
です。あるいは

= Card({e: s(e)=v OR t(e)=v})

とも書けます。これはその頂点に入ってくるか出ていく辺の数です。 無向グラフでも原子価を定義できます(内原子価と外原子価は定義できない)。 それは グラフ G=(V,E,T(・)) においてその任意の頂点をvとしたとき

degree(v)= 2×Card({e: T(e)={v,v}})+Card({e: v∈T(e) and T(e)≠{v,v}})

がそれです。 ある頂点vから出てそれ自身vへ入っているような辺があるときは、 そのような辺の数は2倍して考えます(入りと出ですので)。またT(e1)={v,v2}で T(e2)={v,v2} のときe1≠e2でv≠v2 なら頂点vの原子価に、辺e1とe2の分 2が加わります。

例2

V = {A,B,C,D}, E = {u,v,w,x},

s(u) = A, t(u) = B
s(v) = B, t(v) = C
s(w) = D, t(w) = C
s(x) = A, t(x) = D

即ち

において(有向グラフ)四つの頂点の原子価はすべて2です。つまり

degree(A) = degree(B) = degree(C) = degree(D) = 2