강한 정규 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Paley13.svg|섬네일| 매개변수 srg(13,6,2,3)를 갖는 강한 정규 그래프인 차수 13의 페일리 그래프 .]]
[[그래프 이론]]에서 '''강한 정규 그래프'''는 [[정규 그래프]] 중 각 꼭지점 쌍의 공통 이웃의 개수에 대해 추가적인 조건을 가지는 그래프이다. ''G'' = (''V'', ''E'')를 정점 ''v''개를 가지는 ''k-''[[정규 그래프]]라고 할 때, 어떤 [[정수]] λ, μ가 존재하여 다음 조건을 만족할 경우 ''G''를 '''강한 정규 그래프'''라고 한다.

* 모든 인접한 꼭짓점 쌍은 λ개의 공통 이웃을 갖는다.
* 모든 인접하지 않은 꼭짓점 쌍은 μ개의 공통 이웃을 갖는다.

이 조건을 만족하는 그래프를 srg(''v'', ''k'', λ, μ)으로 쓰기도 한다. 강한 정규 그래프는 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><ref>Godsil, Chris; Royle, Gordon. ''Algebraic Graph Theory''. Springer-Verlag New York, 2001, p. 218.</ref> 또는 그 [[여 그래프]]와 같이 정의를 자명하게 충족시키는 그래프를 제외하기도 한다.

{{개행 금지|srg(''v'', ''k'', λ, μ)}}의 [[여 그래프]]는 {{개행 금지|srg(''v'', ''v'' − ''k'' − 1, ''v'' − 2 − 2''k'' + μ, ''v'' − 2''k'' + λ)}}으로, 강한 정규 그래프이다.

μ가 0이 아닌 강한 정규 그래프는 직경이 2인 거리 정규 그래프이다. {{개행 금지|λ {{=}} 1}}인 강한 정규 그래프는 국소적 선형 그래프이다.

== 성질 ==

=== 매개변수 간의 관계 ===
srg(''v'', ''k'', λ, μ)의 4개 매개변수는 독립적이지 않고, 다음 관계를 따라야 한다.

: <math>(v - k - 1)\mu = k(k - \lambda - 1)</math>

위의 관계는 다음과 같은 조합론적 논증을 통해 도출할 수 있다.

# 그래프의 꼭짓점이 3개의 깊이에 있다고 상상하자. 깊이 0에 있는 정점 하나를 뿌리로 선택한다. 이 정점의 ''k개의'' 이웃은 깊이 1에 있고, 다른 모든 정점은 깊이 2에 있다.
# 깊이 1인 꼭짓점은 뿌리에 직접 연결되므로 뿌리와 공통되는 다른 이웃 λ개가 있어야 하고, 이러한 공통 이웃은 깊이 1에 있어야 한다. 각 꼭짓점의 차수가 ''k'' 이므로 깊이 2 꼭짓점에 연결하기 위한 깊이 1 꼭짓점에 남아 있는 변은 <math>k - \lambda - 1</math>개이므로, 깊이 1과 깊이 2 사이에는 변 <math>k (k - \lambda - 1)</math>개가 존재한다.
# 깊이 2 꼭짓점은 뿌리에 직접 연결되지 않으므로 뿌리와 μ개의 공통 이웃이 있어야 하고, 이러한 공통 이웃은 모두 깊이 1에 있어야 한다. 깊이 2에는 꼭짓점이 <math>(v - k - 1)</math>개 있고, 각각은 깊이 1 꼭짓점 μ 개와 연결되므로 깊이 1과 깊이 2 사이에는 변 <math>(v - k - 1)\mu</math>개가 존재한다.
# 깊이 1과 깊이 2 사이에 있는 변 개수에 대한 두 식을 등호로 연결하여 <math>(v - k - 1)\mu = k(k - \lambda - 1)</math>를 얻는다.

=== 인접행렬 ===
''I''를 [[단위행렬]], ''J''를 요소가 모두 1인 ''v'' × ''v'' 행렬이라고 하자. 강한 정규 그래프의 [[인접행렬]] ''A''는 두 방정식을 만족한다. 

: <math>AJ = JA = kJ,</math>

이는 정규 그래프 조건을 간단하게 다시 기술한 것이다. 이것은 ''k'' 가 all-one 고유 벡터를 갖는 인접 행렬의 고유값임을 보여준다. 두 번째는 강한 정규성을 나타내는 이차방정식

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

이다. 좌변의 ''ij'' 번째 요소는 ''i''에서 ''j'' 까지의 길이 2인 경로의 수이다. 우변의 첫 번째 항은 ''i''에서 자기 자신으로의 경로 수, 즉 자신의 각 이웃에 대해 ''i''에서 이웃으로 갔다가 다시 ''i''로 돌아오는 경로 ''k''개이다. 두 번째 항은 ''i'' 와 ''j'' 가 직접 연결된 경우 길이 2인 경로의 수를 나타낸다. 세 번째 항은 ''i'' 와 ''j'' 가 연결되지 않은 경우 길이 2인 경로의 수이다. 세 가지 경우가 [[상호 배타적]]이고 집합적으로 완전하므로 위와 같은 등식이 성립한다.

반대로, 인접 행렬이 위의 두 조건을 모두 만족하고 완전 그래프 또는 빈 그래프가 아닌 그래프는 강한 정규 그래프이다.<ref>{{인용|출판사=Cambridge University Press|url=https://archive.org/details/designsgraphscod0000came/page/37|제목=Designs, graphs, codes, and their links|성1=Cameron|성2=Peter|이름2=Jephson}}</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'', ''μ'' 및 ''λ'' 값에 대한 추가 제약을 준다.

<math>2k + (v - 1)(\lambda - \mu) \ne 0</math>인 강한 정규 그래프는 중복도가 같지 않은 정수 고유값을 가진다.

<math>2k + (v - 1)(\lambda - \mu) = 0</math>인 강한 정규 그래프는 대칭 [[회의 매트릭스|회의 행렬]]과의 연결 때문에 [[회의 그래프]]라고 한다. 매개변수는 다음으로 감소한다.

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

반대로, 3개의 고유값만을 가지는 연결된 정규 그래프는 강한 정규 그래프이다.<ref>Godsil, Chris; Royle, Gordon. ''Algebraic Graph Theory''. Springer-Verlag, New York, 2001, Lemma 10.2.1.</ref>

== 예 ==

* 길이 5인 [[순환 그래프]]는 srg(5, 2, 0, 1)이다.
* [[페테르센 그래프]]는 srg(10, 3, 0, 1)이다.
* [[클레브쉬 그래프|Clebsch 그래프]]는 srg(16, 5, 0, 2)이다.
* [[슈리칸드 그래프|Shrikhande 그래프]]는 [[거리 전이 그래프]]가 아닌 srg(16, 6, 2, 2)이다.
* ''n'' × ''n'' [[룩 그래프]], 즉 균형 잡힌 완전 [[이분 그래프]] ''K''<sub>''n'', ''n''</sub> 의 선 그래프는 srg(''n''<sup>2</sup>, 2 ''n'' - 2, ''n'' - 2, 2)이다. {{개행 금지|''n'' {{=}} 4}}일 때, 매개변수는 Shrikhande 그래프의 매개변수와 같지만 두 그래프는 동형이 아니다.
* 완전 그래프 ''K<sub>n</sub>''의 [[선 그래프]]는 <math display="inline">\operatorname{srg}\left(\binom{n}{2}, 2(n - 2), n - 2, 4\right)</math>이다.
* Chang 그래프는 srg(28, 12, 6, 4)로 매개변수가 ''K''<sub>8</sub>의 선 그래프와 같지만 이 4개의 그래프는 동형이 아니다.
* 일반화된 사변형 GQ(2, 4)의 [[선 그래프]]는 srg(27, 10, 1, 5)이다. 사실 모든 일반화된 차수(s, t)의 사각형은 다음과 같은 방식으로 강한 정규 그래프를 제공한다. 즉, srg((s + 1)(st + 1), s(t + 1), s − 1, t + 1).
* Schläfli 그래프는 srg(27, 16, 10, 8)이다.<ref>{{매스월드|제목=Schläfli graph}}</ref>
* [[호프만–싱글턴 그래프|호프만-싱글턴 그래프]]는 srg(50, 7, 0, 1)이다.
* Sims-Gewirtz 그래프는 (56, 10, 0, 2)이다.
* [[M22 그래프|M<sub>22</sub> 그래프]]는 srg(77, 16, 0, 4)이다.
* Brouwer-Haemers 그래프는 srg(81, 20, 1, 6)이다.
* [[히그먼-심스 그래프]]는 srg(100, 22, 0, 6)이다.
* 국소 매클로플린 그래프는 srg(162, 56, 10, 24)이다.
* Cameron 그래프는 srg(231, 30, 9, 3)이다.
* Berlekamp-van Lint-Seidel 그래프는 srg(243, 22, 1, 2)이다.
* 매클로플린 그래프는 srg(275, 112, 30, 56)이다.
* 차수 ''q'' 의 [[페일리 그래프]]는 srg(''q'', (''q'' - 1)/2, (''q'' - 5)/4, (''q'' - 1)/4)이다.  가장 작은 페일리 그래프({{개행 금지|''q'' {{=}} 5}}인 경우)는 5-순환 그래프이다.
* 자기 보완 [[대칭 그래프|호 전이]] 그래프는 강한 정규 그래프이다.

강한 정규 그래프와 그 여 그래프가 모두 연결되어 있는 경우 '''원시적'''이라고 한다. 위에서 제시된 모든 그래프는 원시적이다. 원시적이지 않은 강한 정규 그래프는 {{개행 금지|μ {{=}} 0}} 또는 {{개행 금지|λ {{=}} ''k''}} 의 매개변수를 가진다.

[[콘웨이의 99-그래프 문제]]는 srg(99, 14, 1, 2)의 구성을 묻는 문제이다. 이러한 매개변수가 있는 그래프가 존재하는지 여부는 알려져 있지 않으며 [[존 호턴 콘웨이]]는 이 문제에 대한 해결책으로 1000달러의 상금을 제안하였다.<ref>{{인용|postscript=John Horton Conway|출판사=Online Encyclopedia of Integer Sequences|url=https://oeis.org/A248380/a248380.pdf|제목=Five $1,000 Problems (Update 2017)|성1=[[존 호턴 콘웨이]]}}</ref>

== 같이 보기 ==
* [[부분 기하학]]
* [[자이델 인접 행렬]]
* [[2 그래프]]

== 각주 ==
{{각주}}

== 참고 문헌 ==

* AE Brouwer, AM Cohen 및 A. Neumaier(1989), ''Distance Regular Graphs''. 베를린, 뉴욕: Springer-Verlag.{{ISBN|3-540-50619-5}}[[ISBN (identifier)|ISBN]]&nbsp;[[Special:BookSources/3-540-50619-5|3-540-50619-5]] ,{{ISBN|0-387-50619-5}}
* Chris Godsil 및 Gordon Royle(2004), ''Algebraic Graph Theory''. 뉴욕: Springer-Verlag.{{ISBN|0-387-95241-1}}[[ISBN (identifier)|ISBN]]&nbsp;[[Special:BookSources/0-387-95241-1|0-387-95241-1]]

== 외부 링크 ==
{{위키공용분류}}
* [[에릭 웨이스타인|Eric W. Weisstein]], [http://mathworld.wolfram.com/StronglyRegularGraph.html Mathworld 기사, 다양한 예.]
* Gordon Royle, [https://web.archive.org/web/20080503090520/http://people.csse.uwa.edu.au/gordon/remote/srgs/ 더 큰 그래프족 목록.]
* Andries E. Brouwer, [http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html 강한 정규 그래프의 매개변수.]
* Brendan McKay, [http://cs.anu.edu.au/~bdm/data/graphs.html 일부 그래프 모음.]
* Ted Spence, [http://www.maths.gla.ac.uk/~es/srgraphs.php 최대 64개의 정점에 대한 강한 정규 그래프.]

[[분류:강한 정규 그래프]]
[[분류:정규 그래프]]
[[분류:대수적 그래프 이론]]
[[분류:그래프족]]