シコウノストレージ

自分自身の考えを整理するために書いています。

グラフ【1】

グラフ問題を解くうえで理論もそうだが、まず用語とか区別の仕方が分かってないのでそれを調べてまとめることとする。

 

グラフとは何なのか|

頂点と頂点を辺で結んだもの。

頂点は形あるものでもよいし、形のないものを頂点とみなしても良い。

 

有向グラフ、無向グラフ|

辺に向きの制限があるかどうか。

あるのは有効グラフ、ないのは無効グラフ。

 

完全グラフ|

各頂点からすべて自分以外のすべての頂点に辺が伸びているもの。

無向グラフである必要はない。

 

2部グラフ|

2部グラフは隣接しない頂点集合を2つにわけることができるグラフ。

2部グラフの集合をA,Bとすると辺は必ずA-Bの関係になっている。

 

完全2部グラフ|

2部グラフであり、各Aの頂点から各Bの頂点すべてに辺があるグラフ。

A1,A2,A3があるならA1-B1,A1-B2,A1-B3,A2-B1.....となっている。

 

連結グラフ、非連結グラフ|

任意の2点間に道が存在する(直接または間接的に辺があるかどうか)場合連結グラフ。

そうでなければ非連結グラフ。

 

パス|

f:id:slwmtin:20210807180800p:plain



サイクル(閉路)|

f:id:slwmtin:20210807181213p:plain

 なお頂点の数が偶数の場合「偶閉路」、奇数の場合「奇閉路」

 

木|

閉路を含まない連結グラフ。

有向グラフなら有向木と呼ぶこともある。

有向木の場合、辺の向きが根から葉or葉から根に統一されていなければならない。

 

葉、枝|

グラフを木とみなせるので、2つ以上頂点を葉、辺を枝と呼ぶことがある。

 

根付き木|

ある頂点を根として考えたときの木

 

DAG(有向非巡回グラフ)|

閉路を持たない有向グラフ