次数 (グラフ理論)

ウィキペディア

次数 (グラフ理論)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/03/24 14:08 UTC 版)

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

グラフ理論における次数（じすう、英: degree, valency）は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる。頂点 $v$

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

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

包括的特性

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

参考文献

• 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.