強正則グラフ
強正則グラフ(きょうせいそくグラフ、英: Strongly Regular Graph; SRG)
正則グラフ(regular graph)というものが先にある
正則グラフはグラフ上のどの点の次数も同じであるもの 次数はある頂点から出る辺の数
code:memo.mermaid
flowchart LR
node1((v1)) --- node2((v2))
node3((v3)) --- node4((v4))
v1から見てもv2から見ても次数(頂点から出ている辺)は1
v3から見てもv4から見ても次数は1
強正則グラフは$ srg(v, k, λ, μ) で表されることがある
$ v : 頂点
$ k : 次数(頂点から出る辺の数)
$ λ :任意の隣接する2頂点の共通隣接点の数
$ μ :任意の隣接しない2頂点の共通隣接点の数
$ (v - k - 1)μ = k(k - λ - 1) の条件を満たす必要がある
code:memo.mermaid
flowchart LR
node1((v1)) --- node2((v2))
node3((v3)) --- node1
node3 --- node2
code:memo
(v - k - 1)μ = k(k - λ - 1)
↑は強正則グラフ
長さが3の閉路グラフ, srg(3, 2, 1, 0)
$ v = 3 : 頂点は3個
$ k = 2 : 次数はすべて2
$ \lambda = 1 : 例えばv1, v2の共通する隣接点はv3の1つ
$ \mu = 0: 全ての頂点が互いに隣接しているため0
強正則グラフであるもの
長さが5の閉路グラフ, srg(5, 2, 0, 1) ↓に強正則グラフの例が載っている
確認用
Q. 強正則グラフ
参考
正則グラフ
強正則グラフ
関連
メモ