次数列
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/03/24 14:08 UTC 版)
「次数 (グラフ理論)」の記事における「次数列」の解説
無向グラフの次数列 (degree sequence) とは、そのグラフの頂点の次数を増加しない順序で並べた数列である。上のグラフでは (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 の定理では、数列 (di)i=1,...,n は、総和が偶数でかつ 1 と n の間の全ての k について ∑ i = 1 k d i ≤ k ( k − 1 ) + ∑ i = k + 1 n min ( d i , k ) {\displaystyle \sum _{i=1}^{k}d_{i}\leq k(k-1)+\sum _{i=k+1}^{n}\min(d_{i},k)} であるときのみ単純グラフの数列である。Havel と Hakimi は、(d2-1,d3-1,...,dd1+1-1,dd1+2, dd1+3,...,dn) が単純グラフの次数列であるときだけ (d1,d2,...,dn) が単純グラフの次数列であることを証明した。
※この「次数列」の解説は、「次数 (グラフ理論)」の解説の一部です。
「次数列」を含む「次数 (グラフ理論)」の記事については、「次数 (グラフ理論)」の概要を参照ください。
- 次数列のページへのリンク
