グラフ理論における次数
定義 1
有向グラフ $G$が与えられているとしよう。
エッジ $vw$が存在する場合、エッジは$v$から出て$w$に入ると言われる。
- 頂点 $v$に入るエッジの数を入力次数indegreeと呼び、$\deg^{-} (v)$として表される。
- 頂点 $v$から出るエッジの数を出力次数outdegreeと呼び、$\deg^{+}(v)$として表される。
- $\deg^{-} (v) = 0$である頂点をソースsource、$\deg^{+} (v) = 0$である頂点をシンクsinkと言う。ソースでもシンクでもない点をインターナルinternalと呼ぶ。
エッジ $vw$が存在する場合、頂点 $v,w$はエッジ $vw$に接続されているincidentと言われる。
- 頂点 $v$に接続されているエッジの数を次数degreeと呼び、$\deg (v)$として表される。
- 次数が$0$である頂点を孤立頂点isolated Vertexと言う。
- 次数が$1$である頂点をエンド頂点end Vertexと言う。
グラフ$G$の最大次数を$\Delta (G)$、最小次数を$\delta (G)$として表現する。
説明
ちなみに、接続されているという表現はそれほど好ましい言い回しではない。二つの頂点 $v,w$がエッジ$e$によって繋がれている場合、$v$と$w$は隣接しているadjacentと表現され、接続されているという言葉はエッジ$e$に接続されている$v,w$を描写するために使われる。もともと形容詞のIncidentは、付随する、従うなどの意味で使われる英単語だ。
次数の概念は、長い間多くの関心を集めてきたが、特に純粋数学ではシンプルなグラフがよく扱われるため、次数に関する研究が多い。
有向グラフ
例えば、次のグラフでは、赤色が入力次数、青色が出力次数を示す。もちろん、入力次数と出力次数の合計は同じである。
ここで、入力次数が$0$の頂点をソースと言う。入るものがなく、出るだけである点から、ソースという名前は適切だと考えられる。これは動力学でのシンク、ソースと似ている。
次数
例えば、次のグラフで、各頂点の次数を計算することができる。有向グラフを単純なグラフとして表した場合、入力次数と出力次数の合計と同じであることを確認しよう。[ 注: このように方向性をなくしたグラフは、元の有向グラフの基底グラフunderlying Graphと言われる。]
次のグラフでは、頂点$C$と$F$はエンド頂点、$H$は孤立頂点だ。
応用数学では、$H$がなければ、つまりネットワークが完全に接続されている場合、$D$のようなノードをハブと呼ぶ。通常、ハブはネットワーク全体に大きな影響を与えるか、すべての通信を中継することができる要素を描写する。
レギュラーグラフ
特に、すべての頂点の次数が同じであるグラフ、$\delta (G) = \Delta (G)$と表示される、をレギュラーグラフと呼ぶ。
Wilson. (1970). グラフ理論入門: p12. ↩︎