次数と正則グラフ
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/01/02 08:06 UTC 版)
「次数 (グラフ理論)」も参照 頂点 v {\displaystyle v} に接続する枝の数を次数といい、 d ( v ) {\displaystyle d(v)} で表す。有向グラフにおいては、 v {\displaystyle v} に入ってくる辺数のことを入次数、 v {\displaystyle v} から出て行く辺数のことを出次数という。すべての頂点が同数の隣接点、つまり次数をもつグラフを正則グラフと呼ぶ。任意の頂点 v {\displaystyle v} について、 d ( v ) = k {\displaystyle d(v)=k} が成り立つとき、k -正則という。k -正則なグラフのことをk -正則グラフという。グラフ G {\displaystyle G} が持つ頂点の次数の最小値を δ ( G ) {\displaystyle \delta (G)} 、最大値を Δ ( G ) {\displaystyle \Delta (G)} で表す。また、次数 0 の頂点のことを孤立点という。
※この「次数と正則グラフ」の解説は、「グラフ理論」の解説の一部です。
「次数と正則グラフ」を含む「グラフ理論」の記事については、「グラフ理論」の概要を参照ください。
- 次数と正則グラフのページへのリンク