包括的特性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/03/24 14:08 UTC 版)
「次数 (グラフ理論)」の記事における「包括的特性」の解説
全ての頂点が同じ次数 k {\displaystyle k} であるようなグラフをk-正則グラフと呼び、グラフ自体の次数が k {\displaystyle k} とされる。 無向連結グラフがオイラー路を持つとき、奇数の次数の頂点は0個または2個だけである。奇数次数の頂点が0個の場合、そのオイラー路はオイラー閉路である。 有向グラフがpseudoforestであるとき、各頂点の出次数は高々1である。全頂点の出次数が1のpseudoforestを functional graph と呼ぶ。 Brooks' theorem によれば、クリークや奇閉路以外の任意のグラフのグラフ彩色数は高々 Δ であり、Vizing's theorem によれば、任意のグラフの彩色指数は高々 Δ + 1 である。
※この「包括的特性」の解説は、「次数 (グラフ理論)」の解説の一部です。
「包括的特性」を含む「次数 (グラフ理論)」の記事については、「次数 (グラフ理論)」の概要を参照ください。
ウィキペディア小見出し辞書の「包括的特性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 包括的特性のページへのリンク
