次数 (グラフ理論)
無向グラフの次数列 (degree sequence) とは、そのグラフの頂点の次数を増加しない順序で並べた数列である。上のグラフでは (3, 3, 3, 2, 2, 1, 0) となる。次数列はグラフ不変量であり、同型のグラフは同じ次数列を有する。しかし、一般に次数列だけでグラフを一意に特定することはできない。同型でないグラフでも同じ次数列になりうる。
次数列問題とは、正の整数の増加しない数列を次数列として与えたとき、対応するグラフの実例(または全てのグラフ)を求める問題である。次数として0を許容すると単に独立した頂点を加えればよいだけなので、出題する場合には0は使わない。
与えられた次数列に対応するグラフの個数を求める(あるいは推測する)問題は、グラフの数え上げ問題の一種である。
次数の総和の公式から、総和が奇数となるような数列(例えば (3, 3, 1))はグラフの次数列としてはあり得ないことが分かる。逆もまた真であり、数列の総和が偶数であれば、グラフの次数列としてありうる。
ループや多重辺を許容すれば次数列からグラフを描くことは簡単だが、単純グラフ (simple graph) に限定すると次数列問題はやや難しくなる。数列 (8, 4) は明らかに単純グラフの次数列ではない。