有向グラフ
グラフ理論における「有向グラフ」について
- 有向グラフG=(Vg,Eg)は２つの要素Vg,Egからなる.
- 空でない頂点集合Vgがあり,要素は頂点またはノードと呼ばれる.
- 辺または弧の集合Eg(空でもよい)がある.
要素は有向な辺または有向な弧であり,頂点の順序対に割り当てられる.
- 入次数と出次数
・入次数…頂点vに入ってくる有向辺の数.d-(v)と表される.
・出次数…頂点vから出ていく有向辺の数.d+(v)と表される.
補題 グラフGにおいて,入次数の合計と出次数の合計は等しい.
以下に例を示す.
それぞれの頂点における入次数,出次数は以下の通り.
(入次数)d-(v1)=２ d-(v2)=1 d-(v3)=3 d-(v4)=1 d-(v5)=1 (入次数の合計８)
(出次数)d+(v1)=1 d+(v2)=2 d+(v3)=2 d+(v4)=1 d+(v5)=2 （出次数の合計８）
※補題に示した通り,(入次数の合計)=(出次数の合計)であることが分かる.
