パラメータ間の関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/14 07:02 UTC 版)
srg(v, k, λ, μ) の4つのパラメータは独立ではなく、以下の関係を満たしていなければならない： ( v − k − 1 ) μ = k ( k − λ − 1 ) {\displaystyle (v-k-1)\mu =k(k-\lambda -1)} この関係式は、数え上げ論法により非常に簡単に示すことができる。 グラフの全頂点を3つの階層に分ける。任意の頂点を1つ選んで、これは根（root）で、階層0にあるものとする。その k 個の近傍は階層1にあるとし、それ以外の全ての頂点は階層2にあるとする。 階層1の頂点は根と直接つながっているので、根と共有する近傍が λ 個あることになり、これらは階層1にある。どの頂点の次数も k だから、階層1の頂点が持つ階層2の頂点との辺は、残った k − λ − 1 {\displaystyle k-\lambda -1} 本である。よって階層1と階層2の間には合計 k × ( k − λ − 1 ) {\displaystyle k\times (k-\lambda -1)} 本の辺がある。 階層2の頂点は根と直接つながっていないので、根と共有する近傍が μ 個あることになり、これらは全て階層1になければいけない。階層2の頂点は ( v − k − 1 ) {\displaystyle (v-k-1)} 個で、どの頂点も階層1の頂点 μ 個とつながっている。よって階層1と階層2の間には合計 ( v − k − 1 ) × μ {\displaystyle (v-k-1)\times \mu } 本の辺がある。 階層1と階層2の間にある辺の本数を表す2つの表現を等しいと置けばよい。
※この「パラメータ間の関係」の解説は、「強正則グラフ」の解説の一部です。
「パラメータ間の関係」を含む「強正則グラフ」の記事については、「強正則グラフ」の概要を参照ください。
- パラメータ間の関係のページへのリンク
