強正則グラフのソースを表示

[[Image:Paley13.svg|thumb|upright=1.1|頂点数13の{{仮リンク|ペイリーグラフ|en|Paley graph}}は、パラメータ srg(13,6,2,3) の強正則グラフである。]]

[[グラフ理論]]において'''強正則グラフ'''（きょうせいそくグラフ、{{Lang-en-short|strongly regular graph}}）は次のように定義される。頂点数 ''v''、次数 ''k'' の[[正則グラフ]] ''G'' = (''V'', ''E'') が'''強正則'''であるとは、[[整数]] λ と μ が存在して、

* 任意の隣接する2頂点は、ちょうど λ 個の近傍を共有する。
* 任意の隣接しない2頂点は、ちょうど μ 個の近傍を共有する。

の2条件を満たすことを言う。このようなグラフは srg(''v'', ''k'', λ, μ) と表されることがある。強正則グラフは{{仮リンク|ラジ・チャンドラ・ボース|en|Raj Chandra Bose}}によって1963年に導入された<ref>https://projecteuclid.org/euclid.pjm/1103035734, R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific
J. Math 13 (1963) 389–419. (p. 122)</ref>。

著者によっては、条件を自明に満たすグラフ、つまり、[[完全グラフ]]および頂点数が同一の複数の完全グラフの非交和から成るグラフ<ref>[http://homepages.cwi.nl/~aeb/math/ipm.pdf Brouwer, Andries E; Haemers, Willem H. ''Spectra of Graphs''. p. 101] {{Webarchive|url=https://web.archive.org/web/20120316102909/http://homepages.cwi.nl/~aeb/math/ipm.pdf |date=2012-03-16 }}</ref>{{sfn|Godsil|Royle|2001|p=218}}と、それらの[[補グラフ]]（同一個数の独立集合の集まりからできる完全{{仮リンク|多部グラフ|en|multipartite graph}}）を強正則グラフに含めないこともある。

強正則グラフ srg(''v'', ''k'', λ, μ) の補グラフはまた強正則グラフ、srg(''v'', ''v−k''−1, ''v''−2−2''k''+μ, ''v''−2''k''+λ) になる。

強正則グラフは μ が0でないとき、[[グラフ理論#距離と直径|直径]]2の{{仮リンク|距離正則グラフ|en|distance-regular graph}}（distance-regular graph）である。強正則グラフは λ が1であるとき、{{仮リンク|局所線形グラフ|en|locally linear graph}}（locally linear graph）である。

==性質==

===パラメータ間の関係===
srg(''v'', ''k'', λ, μ) の4つのパラメータは独立ではなく、以下の関係を満たしていなければならない：
:<math>(v-k-1)\mu = k(k-\lambda-1)</math>
この関係式は、数え上げ論法により非常に簡単に示すことができる。
# グラフの全頂点を3つの階層に分ける。任意の頂点を1つ選んで、これは根（root）で、階層0にあるものとする。その ''k'' 個の近傍は階層1にあるとし、それ以外の全ての頂点は階層2にあるとする。
# 階層1の頂点は根と直接つながっているので、根と共有する近傍が λ 個あることになり、これらは階層1にある。どの頂点の次数も ''k'' だから、階層1の頂点が持つ階層2の頂点との辺は、残った <math>k-\lambda-1</math> 本である。よって階層1と階層2の間には合計 <math>k\times(k-\lambda-1)</math> 本の辺がある。
# 階層2の頂点は根と直接つながっていないので、根と共有する近傍が μ 個あることになり、これらは全て階層1になければいけない。階層2の頂点は <math>(v-k-1)</math> 個で、どの頂点も階層1の頂点 μ 個とつながっている。よって階層1と階層2の間には合計 <math>(v-k-1)\times\mu</math> 本の辺がある。
# 階層1と階層2の間にある辺の本数を表す2つの表現を等しいと置けばよい。

===隣接行列===
''I'' を[[単位行列]]、''J'' を {{ill2|matrix of ones|en|matrix of ones}}（全成分が1の行列）で、いずれも ''v'' 次（行列）であるとする。強正則グラフの[[隣接行列]] ''A'' は2つの方程式を満たさねばならない。まず、
:<math>AJ = JA = kJ</math>
これはグラフの正則性を述べなおした自明な関係である。これより、''k'' は隣接行列の固有値で、全成分が1のベクトルがそれに対する固有ベクトルであることがわかる。

次は2次式の関係式で、グラフの強正則性を表す。

:<math>{A}^{2} = k{I} + \lambda{A} + \mu({J-I-A})</math>

左辺の ''ij''-成分は、頂点 ''i'' から頂点 ''j'' への長さ2の道の本数を表す。右辺の最初の項は頂点 ''i'' を自分自身と結ぶ、つまり ''k'' 本の「出」と「入り」の辺の数である。第2項は頂点 ''i'' と頂点 ''j'' が隣接しているときに、2辺でこれらを結ぶ道の本数を表す。第3項は頂点 ''i'' と頂点 ''j'' が隣接していないときの本数である。これら3つの場合は排他的で、かつ全てを尽くしているから、単純に和をとって等式が得られる。

逆に、グラフの隣接行列がこれら2条件を満たし、完全グラフでも[[空グラフ]]でもないとき、強正則グラフである<ref>{{citation|first1=P.J.|last1=Cameron|first2=J.H.|last2=van Lint|title=Designs, Graphs, Codes and their Links|publisher=Cambridge University Press|series=London Mathematical Society Student Texts 22|year=1991|isbn=978-0-521-42385-4|page=37}}</ref>。

===固有値===
強正則グラフの隣接行列はちょうど3個の[[固有値]]を持つ：
*''k'' は[[重複度 (数学)|重複度]]1である（上述したもの）。
* <math>\frac{1}{2}\left[(\lambda-\mu)+\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right],</math> この重複度は <math>\frac{1}{2} \left[(v-1)-\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]</math> である。
* <math>\frac{1}{2}\left[(\lambda-\mu)-\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right],</math> この重複度は <math>\frac{1}{2} \left[(v-1)+\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]</math> である。
重複度は整数でなければいけないから、これらの表現から ''v'', ''k'', ''μ'', ''λ'' の間にはさらに制約が加わることになる。これはクレイン条件（Krein conditions）と呼ばれている。

<math>2k+(v-1)(\lambda-\mu) = 0</math> である強正則グラフは、対称{{仮リンク|カンファレンス行列|en|conference matrix}}（conference matrix）との関連から{{仮リンク|カンファレンスグラフ|en|conference graph}}（conference graph）と呼ばれる。このときパラメータは

::<math>\text{srg}\left(v, \tfrac{1}{2}(v-1), \tfrac{1}{4}(v-5), \tfrac{1}{4}(v-1)\right)</math>

となる。<math>2k+(v-1)(\lambda-\mu) \ne 0</math> である強正則グラフの隣接行列は、重複度の異なる整数固有値を持つことになる。

逆に、連結正則グラフは隣接行列の固有値が高々3個であるとき、強正則グラフである{{sfn|Godsil|Royle|2001|loc=Lemma 10.2.1|p=220}}。

==例==
* 長さ5の[[閉路グラフ]]：srg(5, 2, 0, 1)
* [[ピーターセングラフ]]：srg(10, 3, 0, 1)
* {{仮リンク|クレブシュグラフ|en|Clebsch graph}}（Clebsch graph）：srg(16, 5, 0, 2)
* {{仮リンク|シュリクハンデグラフ|en|Shrikhande graph}}（Shrikhande graph）は srg(16, 6, 2, 2) であり、[[距離推移グラフ]]ではない。
* ''n''&nbsp;×&nbsp;''n'' の正方{{仮リンク|ルークのグラフ|en|rook's graph}}（rook's graph）、つまり両部が同じ頂点数からなる[[完全2部グラフ]] ''K<sub>n,n</sub>'' の [[:en:line graph]]であり、srg(''n''<sup>2</sup>, 2''n''&nbsp;−&nbsp;2, ''n''&nbsp;−&nbsp;2, 2) と表せる。''n''=4 のときはシュリクハンデグラフとパラメータが一致するが、これらはグラフ同型ではない。
* [[ホフマン–シングルトングラフ]]：srg(50, 7, 0, 1)
* {{仮リンク|ジェウィルスグラフ|en|Gewirtz graph}}（Gewirtz graph）：srg(56, 10, 0, 2)
* {{仮リンク|M22グラフ|en|M22 graph}}：srg(77, 16, 0, 4)
* {{仮リンク|ヒグマン–シムスグラフ|en|Higman–Sims graph}}（Higman–Sims graph）：srg(100, 22, 0, 6)
* [[バーレカンプ–ヴァン・リント–ザイデルグラフ]]（Berlekamp–van Lint–Seidel graph）：srg(243, 22, 1, 2)
* [[マクラフリングラフ]]（McLaughlin graph）：srg(275, 112, 30, 56)

強正則グラフは、自身とその補グラフがいずれも連結であるとき原始的（primitive）であると言う。ここに挙げた例は全て原始的である（さもなければ μ=0 または λ=k でなければならない）。

[[コンウェイの99グラフ問題]]はパラメータ srg(99, 14, 1, 2) のグラフが構成できるかを問う問題である。このようなグラフが存在するか否かは未解決であり、[[ジョン・ホートン・コンウェイ]]はこの問題の賞金に1000ドルを提示した<ref>{{citation
 | last = Conway | first = John H. | author-link = John Horton Conway
 | accessdate = 2019-02-12
 | publisher = Online Encyclopedia of Integer Sequences
 | title = Five $1,000 Problems (Update 2017)
 | url = https://oeis.org/A248380/a248380.pdf}}</ref>。

===ムーアグラフ===
λ&nbsp;=&nbsp;0 の強正則グラフは{{仮リンク|トライアングルフリー|en|triangle free}}（triangle free）である。頂点数が3未満の完全グラフと、全ての完全2部グラフ以外では、上に挙げた7つ（五角形、ピーターセングラフ、クレブシュグラフ、ホフマン–シングルトングラフ、ジェウィルスグラフ、M22グラフ、ヒグマン–シムスグラフ）が知られている全てである。

λ&nbsp;=&nbsp;0 かつ μ&nbsp;=&nbsp;1 の強正則グラフは[[内周 (グラフ理論)|内周]]5の[[ムーアグラフ]]になる。再び、上に挙げたグラフのうち3つ（五角形、ピーターセングラフ、ホフマン–シングルトングラフ）は、それぞれパラメータは (5, 2, 0, 1), (10, 3, 0, 1), (50, 7, 0, 1) で、知られているものはこれらで全てである。

ムーアグラフを作るパラメータとして残っている唯一の候補は (3250, 57, 0, 1) だが、これを満たすグラフが存在するかどうか、また存在すればそれは一意的かどうかは未解決である。

==関連項目==
* {{ill2|Partial geometry|en|Partial geometry}}
* {{仮リンク|ザイデル隣接行列|en|Seidel adjacency matrix}}
* {{ill2|Two-graph|en|Two-graph}}

==注釈・出典==
{{reflist}}

==参考文献==
* A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), ''Distance Regular Graphs''.  Berlin, New York: Springer-Verlag.  {{ISBN2|3-540-50619-5}}, {{ISBN2|0-387-50619-5}}
* {{cite book
    |last1              = Godsil
    |first1             = C.
    |last2              = Royle
    |first2             = G.
    |year               = 2001
    |title              = Algebraic Graph Theory
    |url                = {{google books|GeSPBAAAQBAJ|plainurl=yes}}
    |publisher          = Springer-Verlag
    |isbn               = 0-387-95241-1
    |mr                 = 
    |zbl                = 0968.05002
    |ref                = harv
}}

==外部リンク==
* [[Eric W. Weisstein]], [http://mathworld.wolfram.com/StronglyRegularGraph.html Mathworld article with numerous examples.]
* [[Gordon Royle]], [https://web.archive.org/web/20080503090520/http://people.csse.uwa.edu.au/gordon/remote/srgs/ List of larger graphs and families.]
* [[Andries E. Brouwer]], [http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html Parameters of Strongly Regular Graphs.]
* [[Brendan McKay]], [http://cs.anu.edu.au/~bdm/data/graphs.html Some collections of graphs.]
* [[Ted Spence]], [http://www.maths.gla.ac.uk/~es/srgraphs.php Strongly regular graphs on at most 64 vertices.]

{{DEFAULTSORT:きようせいそくくらふ}}
[[Category:グラフ理論のグラフ]]
[[Category:数学に関する記事]]
[[Category:代数的グラフ理論]]