![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/0/05/Paley13.svg/langja-640px-Paley13.svg.png&w=640&q=50)
強正則グラフ
ウィキペディア フリーな encyclopedia
グラフ理論において強正則グラフ(きょうせいそくグラフ、英: strongly regular graph)は次のように定義される。頂点数 v、次数 k の正則グラフ G = (V, E) が強正則であるとは、整数 λ と μ が存在して、
- 任意の隣接する2頂点は、ちょうど λ 個の近傍を共有する。
- 任意の隣接しない2頂点は、ちょうど μ 個の近傍を共有する。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/05/Paley13.svg/320px-Paley13.svg.png)
の2条件を満たすことを言う。このようなグラフは srg(v, k, λ, μ) と表されることがある。強正則グラフはラジ・チャンドラ・ボース(英語版)によって1963年に導入された[1]。
著者によっては、条件を自明に満たすグラフ、つまり、完全グラフおよび頂点数が同一の複数の完全グラフの非交和から成るグラフ[2][3]と、それらの補グラフ(同一個数の独立集合の集まりからできる完全多部グラフ(英語版))を強正則グラフに含めないこともある。
強正則グラフ srg(v, k, λ, μ) の補グラフはまた強正則グラフ、srg(v, v−k−1, v−2−2k+μ, v−2k+λ) になる。
強正則グラフは μ が0でないとき、直径2の距離正則グラフ(英語版)(distance-regular graph)である。強正則グラフは λ が1であるとき、局所線形グラフ(英語版)(locally linear graph)である。