グラフ (離散数学)
「Oriented graph」の定義の1つは、 ( x , y ) {\displaystyle (x,y)} と ( y , x ) {\displaystyle (y,x)} のうち高々1つがグラフの辺となりうる有向グラフ。すなわち、単純無向グラフに向き付け (orientation) を行うことで形成されうる有向グラフである。
一部の著者は「有向グラフ」と同じ意味で「Oriented graph」を使っている。与えられた無向グラフや多重グラフへの任意の向き付けという意味で「Oriented graph」を使っている著者もいる。
位数 n ≥ 3 {\displaystyle n\geq 3} の「閉路グラフ (cycle graph)」とは、頂点の集合を v 1 , v 2 , ⋯ , v n {\displaystyle v_{1},v_{2},\cdots ,v_{n}} のように順序付けすることで、辺の集合が { v i , v i + 1 } {\displaystyle \{v_{i},v_{i+1}\}} (ここで i = 1 , 2 , ⋯ , n − 1 {\displaystyle i=1,2,\cdots ,n-1} )に { v n , v 1 } {\displaystyle \{v_{n},v_{1}\}} を付け加えたものとなりうるグラフ。ダイアグラムは閉路状になる。閉路グラフはあらゆる頂点の次数が2の連結グラフという特徴がある。他のグラフの部分グラフとして閉路グラフを作った場合、元のグラフにおける閉路(または回路)にあたる。