📂グラフ理論

グラフ理論における次数

定義 ¹

有向グラフ $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)$と表示される、をレギュラーグラフと呼ぶ。