次数 (グラフ理論)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/03/24 14:08 UTC 版)
ナビゲーションに移動 検索に移動
グラフ理論における次数（じすう、英: degree, valency）は、グラフの頂点に接合する辺の数を意味し、ループであれば2回カウントされる[1]。頂点 
- 次数0の頂点を孤立頂点 (isolated vertex) と呼ぶ。
- 次数1の頂点を葉頂点 (leaf vertex) と呼び、その頂点と接合している辺をペンダント辺 (pendant edge) などと呼ぶ。右図で {3,5} はペンダント辺である。これはグラフ理論の中でも特に木の研究でよく使われ、特にデータ構造としての木に対してよく使われる。
包括的特性
- 全ての頂点が同じ次数 であるようなグラフを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.
- G. Sierksma and H. Hoogeveen, "Seven criteria for integer sequences being graphic, " Journal of Graph Theory 15, No. 2 (1991) 223–231.
