次数 (グラフ理論)のソースを表示

[[ファイル:UndirectedDegrees.svg|thumb|各頂点に次数を記したグラフ]]
[[グラフ理論]]における'''次数'''（じすう、{{lang-en-short|degree, valency}}）は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる<ref>Diestel p.5</ref>。頂点 <math>v</math> の次数を <math>\deg(v)</math> と表記する。グラフ ''G'' の最大次数を Δ(''G'') と表記し、その中の頂点群の最大次数を意味する。また、グラフの最小次数は δ(''G'') と表記し、その中の頂点群の最小次数を意味する。右のグラフでは、最大次数は3、最小次数は0である。[[正則グラフ]]では全頂点の次数が等しく、その次数をグラフの次数と呼ぶこともある。

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

== 握手補題 ==
グラフ <math>G=(V, E)</math> の次数の総和は次の公式で表される。

:<math>\sum_{v \in V} \deg(v) = 2|E|\,</math>

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

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

== 次数列 ==
無向グラフの'''次数列''' (degree sequence) とは、そのグラフの頂点の次数を増加しない順序で並べた数列である<ref>Diestel p.278</ref>。上のグラフでは (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 [[:en:Tibor Gallai|Gallai]] (1960)、[[:en:V. J. Havel|V. J. Havel]] (1955)、[[:en:S. L. Hakimi|S. L. Hakimi]] (1961)、[[:en:S. A. Choudum|S. A. Choudum]] and Sierksma et al. (1991) などの例がある。

例えば、Erdős-Gallai の定理では、数列 (d<sub>i</sub>)<sub>i=1,...,n</sub> は、総和が偶数でかつ 1 と n の間の全ての k について
:<math>\sum_{i=1}^{k}d_i \leq k(k-1) + \sum_{i=k+1}^n  \min(d_i,k)</math>
であるときのみ単純グラフの数列である。Havel と Hakimi は、(d<sub>2</sub>-1,d<sub>3</sub>-1,...,d<sub>d<sub>1</sub>+1</sub>-1,d<sub>d<sub>1</sub>+2</sub>, d<sub>d<sub>1</sub>+3</sub>,...,d<sub>n</sub>) が単純グラフの次数列であるときだけ (d<sub>1</sub>,d<sub>2</sub>,...,d<sub>n</sub>) が単純グラフの次数列であることを証明した。

== 特殊な値 ==
[[ファイル:Depth-first-tree.png|thumb|葉ノード 4, 5, 6, 7, 10, 11, 12 を持つ無向グラフ]]
* 次数0の頂点を'''孤立頂点''' (isolated vertex) と呼ぶ。
* 次数1の頂点を葉頂点 (leaf vertex) と呼び、その頂点と接合している辺をペンダント辺 (pendant edge) などと呼ぶ。右図で {3,5} はペンダント辺である。これはグラフ理論の中でも特に[[木 (数学)|木]]の研究でよく使われ、特に[[データ構造]]としての[[木構造 (データ構造)|木]]に対してよく使われる。

== 包括的特性 ==
* 全ての頂点が同じ次数 <math>k</math> であるようなグラフを[[正則グラフ|''k''-正則グラフ]]と呼び、グラフ自体の次数が <math>k</math> とされる。
* 無向[[連結グラフ]]が[[オイラー路]]を持つとき、奇数の次数の頂点は0個または2個だけである。奇数次数の頂点が0個の場合、そのオイラー路はオイラー[[閉路]]である。
* 有向グラフが[[:en:pseudoforest|pseudoforest]]であるとき、各頂点の出次数は高々1である。全頂点の出次数が1のpseudoforestを functional graph と呼ぶ。
* [[:en:Brooks' theorem|Brooks' theorem]] によれば、クリークや[[閉路グラフ|奇閉路]]以外の任意のグラフの[[グラフ彩色]]数は高々 Δ であり、[[:en:Vizing's theorem|Vizing's theorem]] によれば、任意のグラフの[[彩色指数]]は高々 Δ&nbsp;+&nbsp;1 である。

== 脚注・出典 ==
{{reflist}}

== 参考文献 ==
* {{Citation | last1=Diestel | first1=Reinhard | title=Graph Theory | url= http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ | publisher=Springer-Verlag | location=Berlin, New York | edition=3rd | isbn=978-3-540-26183-4 | year=2005 }}.
* G. Sierksma and H. Hoogeveen, "Seven criteria for integer sequences being graphic, " Journal of Graph Theory 15, No. 2 (1991) 223&ndash;231.

{{DEFAULTSORT:しすう}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]