次数 (グラフ理論)

グラフ理論における次数（じすう、英: degree, valency）は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる^[1]。頂点 ${\displaystyle v}$ の次数を ${\displaystyle \deg(v)}$ と表記する。グラフ G の最大次数を Δ(G) と表記し、その中の頂点群の最大次数を意味する。また、グラフの最小次数は δ(G) と表記し、その中の頂点群の最小次数を意味する。右のグラフでは、最大次数は3、最小次数は0である。正則グラフでは全頂点の次数が等しく、その次数をグラフの次数と呼ぶこともある。

各頂点に次数を記したグラフ

有向グラフでは、頂点に入ってくる辺数を入次数 (indegree)、頂点から出て行く辺数を出次数 (outdegree) と呼ぶ。

握手補題

グラフ ${\displaystyle G=(V,E)}$ の次数の総和は次の公式で表される。

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,}$

これの証明は double counting という手法（二通りに数え上げる）の例である。グラフ内の辺と頂点の接合の個数は式の左辺のように各頂点の次数の総和でも表されるし、右辺のように辺の両端を数え上げてもよい。

この公式が意味するのは、次数が奇数の頂点の個数は偶数個だということである。これを握手補題 (handshaking lemma) と呼ぶ。この補題の名称は、あるグループ内で奇数人の人々と握手した人の数は常に偶数になるという数学の証明問題に由来する。

次数列

無向グラフの次数列 (degree sequence) とは、そのグラフの頂点の次数を増加しない順序で並べた数列である^[2]。上のグラフでは (3, 3, 3, 2, 2, 1, 0) となる。次数列はグラフ不変量であり、同型のグラフは同じ次数列を有する。しかし、一般に次数列だけでグラフを一意に特定することはできない。同型でないグラフでも同じ次数列になりうる。

次数列問題とは、正の整数の増加しない数列を次数列として与えたとき、対応するグラフの実例（または全てのグラフ）を求める問題である。次数として0を許容すると単に独立した頂点を加えればよいだけなので、出題する場合には0は使わない。

与えられた次数列に対応するグラフの個数を求める（あるいは推測する）問題は、グラフの数え上げ問題の一種である。

次数の総和の公式から、総和が奇数となるような数列（例えば (3, 3, 1)）はグラフの次数列としてはあり得ないことが分かる。逆もまた真であり、数列の総和が偶数であれば、グラフの次数列としてありうる。

ループや多重辺を許容すれば次数列からグラフを描くことは簡単だが、単純グラフ (simple graph) に限定すると次数列問題はやや難しくなる。数列 (8, 4) は明らかに単純グラフの次数列ではない。何故なら Δ(G) が頂点数から1を引いた値より大きいという矛盾があるためである。数列 (3, 3, 3, 1) も単純グラフの次数列ではないが、こちらの理由は前者ほど明らかではない。単純グラフの次数列の一般的基準を求めることは古典的問題であり、Erdős and Gallai (1960)、V. J. Havel (1955)、S. L. Hakimi (1961)、S. A. Choudum and Sierksma et al. (1991) などの例がある。

例えば、Erdős-Gallai の定理では、数列 (d_i)_i=1,...,n は、総和が偶数でかつ 1 と n の間の全ての k について

${\displaystyle \sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)}$

であるときのみ単純グラフの数列である。Havel と Hakimi は、(d₂-1,d₃-1,...,d_d1+1-1,d_d1+2, d_d1+3,...,d_n) が単純グラフの次数列であるときだけ (d₁,d₂,...,d_n) が単純グラフの次数列であることを証明した。

特殊な値

葉ノード 4, 5, 6, 7, 10, 11, 12 を持つ無向グラフ

• 次数0の頂点を孤立頂点 (isolated vertex) と呼ぶ。
• 次数1の頂点を葉頂点 (leaf vertex) と呼び、その頂点と接合している辺をペンダント辺 (pendant edge) などと呼ぶ。右図で {3,5} はペンダント辺である。これはグラフ理論の中でも特に木の研究でよく使われ、特にデータ構造としての木に対してよく使われる。

包括的特性

• 全ての頂点が同じ次数 ${\displaystyle k}$ であるようなグラフをk-正則グラフと呼び、グラフ自体の次数が ${\displaystyle k}$ とされる。
• 無向連結グラフがオイラー路を持つとき、奇数の次数の頂点は0個または2個だけである。奇数次数の頂点が0個の場合、そのオイラー路はオイラー閉路である。
• 有向グラフがpseudoforestであるとき、各頂点の出次数は高々1である。全頂点の出次数が1のpseudoforestを functional graph と呼ぶ。
• Brooks' theorem によれば、クリークや奇閉路以外の任意のグラフのグラフ彩色数は高々 Δ であり、Vizing's theorem によれば、任意のグラフの彩色指数は高々 Δ + 1 である。

脚注・出典

1. Diestel p.5
2. Diestel p.278

参考文献

• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/.
• G. Sierksma and H. Hoogeveen, "Seven criteria for integer sequences being graphic, " Journal of Graph Theory 15, No. 2 (1991) 223–231.