무어 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
{{미해결|수학|둘레 5, 차수 57인 무어 그래프는 존재하는가?}}

[[그래프 이론]]에서 '''무어 그래프'''(Moore graph)는 [[학위(그래프 이론)|차수]] ''d'' , [[거리 (그래프 이론)|지름]] ''k''이고 꼭짓점 개수가 <math>1+d\sum_{i=0}^{k-1}(d-1)^i</math>인 [[정규 그래프]]이다. 이 개수는 차수와 지름이 주어졌을 때 그래프가 가질 수 있는 정점 개수의 최댓값이다.

:

무어 그래프의 몇 가지 동등한 정의는 다음과 같다.

* 무어 그래프는 지름이 <math>k</math>, [[안둘레]]가 <math>2k + 1</math>인 그래프이다.
* 꼭지점 <math> n </math>개, 변 <math> m </math>개를 갖는 무어 그래프는 안둘레가 <math> g = 2k+1 </math>이고 <math>g</math>-[[순환 (그래프 이론)|순환]]을 <math> \frac{n}{g}(m-n+1) </math>개 갖는 그래프이다. 이러한  순환의 개수는 그래프의 안둘레 길이에 대해 극단인 경우이다.{{Sfnp|Azarija|Klavžar|2015}}

무어 그래프라는 이름은 앨런 호프만과 로버트 싱글턴에 의해, 이러한 그래프를 설명하고 분류하는 문제를 제기한 [[에드워드 F. 무어|Edward F. Moore]]의 이름을 따서 명명되었다. ({{하버드 인용 본문|Hoffman|Singleton|1960}})

무어 그래프는 차수와 지름이 주어졌을 때 가능한 최대 정점 수를 가질 뿐 아니라, 차수와 둘레가 주어졌을 때 가능한 최소 정점 수를 갖는다. 즉, 모든 무어 그래프는 [[케이지(그래프 이론)|케이지]]이다.{{Sfnp|Erdős|Rényi|Sós|1966}} 무어 그래프의 꼭짓점 수에 대한 공식은 짝수 둘레를 가진 무어 그래프를 허용하도록 일반화될 수 있고, 이러한 그래프 역시 케이지이다.

== 차수 및 지름에 따른 꼭지점 개수의 상한 ==
[[파일:Petersen-as-Moore.svg|섬네일| [[페테르센 그래프]]를 무어 그래프로 나타낸 그림. 모든 [[너비 우선 탐색]] 트리의 깊이 ''i''에 ''d''(''d'' − 1)<sup>''i''</sup> 개의 꼭짓점이 있다.]]
''G''를 최대 차수 ''d'' 와 지름 ''k''를 갖는 임의의 그래프라고 하고, 임의의 꼭지점 ''v''에서 시작하는 [[너비 우선 탐색]]에 의해 형성된 [[나무 그래프|나무]]를 생각하자. 이 나무는 깊이 0(''v'' 자체)에서 1개의 정점을 갖고, 깊이 1(''v''의 이웃)에서 최대 ''d''개의 정점을 갖는다. 다음 깊이에는 많아야 ''d'' (''d'' − 1) 개의 꼭짓점이 있는데, 깊이 1 꼭짓점인 ''v''의 각 이웃은 ''v''에 이미 연결되어 있으므로 깊이 2에서 최대 ''d'' − 1개의 이웃을 가질 수 있기 때문이다. 일반적으로, 모든 레벨 1 ≤ ''i'' ≤ ''k''에서 많아야 ''d''(''d'' − 1)<sup>''i''−1</sup>개의 정점이 있다. 따라서 정점 개수의 상한은 <math>1+d\sum_{i=0}^{k-1}(d-1)^i</math>이다.

:

호프만과 싱글턴은 무어 그래프를 꼭짓점 개수가 이 상한과 일치하는 그래프로 정의하였다. ({{하버드 인용 본문|Hoffman|Singleton|1960}}) 따라서, 임의의 무어 그래프는 최대 차수가 ''d'', 직경이 ''k''인 모든 그래프 중에서 가장 많은 꼭짓점을 갖는다.

이후 싱글턴은 무어 그래프를 직경 ''k'', 둘레 2''k''+1인 그래프로 정의하는 것이 원래 정의와 동등함을 보였다. ({{하버드 인용 본문|Singleton|1968}}) 이 두 가지 조건을 동시에 만족하는 그래프는 어떤 ''d''에 대해 ''d''-정규 그래프가 되고, 꼭짓점 계산 공식을 만족한다.

== 케이지로서의 무어 그래프 ==
그래프의 최대 차수와 지름을 사용하여 꼭짓점 개수에 대한 상한을 만드는 대신, 유사한 방법을 통해 최소 차수와 [[안둘레]]를 사용하여 꼭짓점 개수에 대한 하한을 만들 수 있다.{{Sfnp|Erdős|Rényi|Sós|1966}} 그래프 ''G''의 최소 차수가 ''d''이고 둘레가 2''k'' +1이라고 가정하자. 임의로 시작 정점 ''v''를 선택하고, 이전과 같이 ''v''를 뿌리로 하는 너비 우선 탐색 나무를 만든다. 이 트리는 깊이 0(''v'' 자체)에 하나의 정점이 있고, 깊이 1에서 최소한 ''d''개의 정점이 있다. ''k'' > 1의 경우, 깊이 2에 포함된 꼭짓점은 깊이 1 이하의 꼭짓점 두 개 이상과 인접하지 않음을 관찰하자. 그렇지 않다면 가정한 안둘레 2''k''+1보다 작은 길이의 순환이 형성된다. 따라서 이 경우에는 깊이 2에 적어도 ''d''(''d'' − 1)개의 꼭짓점이 있는데, 깊이 1의 각 꼭짓점에는 깊이 2에서 채워야 할 이웃이 최소한 ''d'' − 1개 있고 깊이 1인 서로 다른 꼭짓점은 하나의 레벨 2 꼭짓점과 동시에 이웃하지 않기 때문이다. 일반적으로, 모든 깊이 1 ≤ ''i'' ≤ ''k''에서 적어도 ''d''(''d'' − 1)<sup>''i''</sup> 개의 꼭짓점이 있어야 하고, 꼭짓점 개수의 하한은 <math>1+d\sum_{i=1}^{k-1}(d-1)^i</math>이다.

:

무어 그래프는 꼭짓점 개수에 대한 하한을 정확히 만족한다. 지름이 ''k''인 각 무어 그래프의 안둘레는 정확히 2''k'' +1이다. 더 긴 안둘레를 가질 만큼 정점이 충분하지 않고, 2''k'' +1보다 더 짧은 주기가 존재하면 너비 우선 탐색 나무의 처음 ''k'' 개의 깊이 중 일부에서 정점이 부족하게 된다. 따라서 모든 무어 그래프는, 최소 차수가 ''d'' 이고 둘레가 ''2k'' +1인 모든 그래프 중에서 꼭짓점이 가장 적다. 따라서 무어 그래프는 케이지이다.

짝수 안둘레 2''k''에 대해서는 한 변의 중간점에서 시작하는 너비 우선 탐색 나무를 유사하게 구성할 수 있다. 최소 차수가 ''d'' 인 이 안둘레의 그래프에서 꼭짓점 개수의 하한에 대한 결과는 다음과 같다.

: <math>2\sum_{i=0}^{k-1}(d-1)^i=1+(d-1)^{k-1}+d\sum_{i=0}^{k-2}(d-1)^i.</math>

공식의 우변은 앞에서 설명한 방법 대신 단일 정점에서 시작하는 너비 우선 탐색 나무의 꼭짓점 수를 계산한 것으로, 나무의 마지막 레벨에 있는 꼭짓점이 이전 레벨에 있는 꼭짓점 ''d'' 개에 인접할 수 있는 가능성을 고려하여 만든 것이다. 무어 그래프는 때때로 이 짝수 안둘레의 경우에서 하한을 정확히 충족하는 그래프를 포함하도록 정의된다. 이러한 경우에도 그래프는 케이지이다.

== 예시 ==
'''호프만-싱글턴 정리'''에 따르면, 둘레가 5인 무어 그래프는 차수가 2, 3, 7 또는 57이다. 무어 그래프는 다음과 같다.{{Sfnp|Bollobás|1998}}

* ''n'' > 2에 대해, ''n''개의 꼭지점 위의 [[완전 그래프]] <math> K_n </math> (지름 1, 둘레 3, 차수 ''n'' − 1, 꼭짓점 ''n'')
* 홀수 차수 [[순환 그래프]] <math> C_{2n+1} </math> (지름 ''n'', 둘레 2 ''n'' + 1, 차수 2, 꼭짓점 2 ''n'' + 1)
* [[페테르센 그래프]] (지름 2, 둘레 5, 차수 3, 꼭짓점 10)
* [[호프만-싱글턴 그래프]] (직경 2, 둘레 5, 차수 7, 꼭짓점 50)
* 존재 여부가 알려지지 않은 가상의 그래프 (직경 2, 둘레 5, 차수 57, 꼭짓점 3250){{Sfnp|Dalfó|2019}}

알려진 모든 무어 그래프는 [[정점 전이 그래프|꼭짓점 전이 그래프]]이지만, 알려지지 않은 그래프는 (만약 존재한다면) 꼭짓점 전이 그래프가 될 수 없는데, 자기동형군의 위수가 최대 375이고 이는 꼭짓점 개수보다 작기 때문이다.{{Sfnp|Mačaj|Širáň|2010}}

짝수 안둘레를 허용하는 무어 그래프의 일반화된 정의를 사용하면 짝수 안둘레 무어 그래프는 (퇴화 가능성이 있는) [[일반화 다각형]]의 인접 그래프에 해당한다. 몇 가지 예로는 다음이 있다.

* 짝수 차수 [[순환 그래프]] <math> C_{2n} </math>
* [[완전 이분 그래프]] <math> K_{n,n} </math> (안둘레 4)
* Heawood 그래프 (차수 3, 안둘레 6)
* Tutte-Coxeter 그래프 (차수 3, 안둘레 8)

더욱 일반적으로, 위에 나열되지 않은 모든 무어 그래프는 안둘레가 5, 6, 8 또는 12여야 하는 것으로 알려져 있다.<ref>{{하버드 인용 본문|Bannai|Ito|1973}}; {{하버드 인용 본문|Damerell|1973}}</ref> 짝수 둘레의 경우에는 일반화된 ''n''각형에 대해 ''n''의 가능한 값에 대한 Feit-Higman 정리도 따라야 한다.

== 같이 보기 ==
* [[정도 직경 문제|차수 직경 문제]]
* [[주어진 직경과 최대 차수의 알려진 가장 큰 그래프의 표]]

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

== 참고 문헌 ==

* {{인용|title=Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles|author2-link=Sandi Klavžar|last1=Azarija|first1=Jernej|last2=Klavžar|first2=Sandi|journal=[[Journal of Graph Theory]]|volume=80|pages=34–42|year=2015|doi=10.1002/jgt.21837|arxiv=1210.6342|s2cid=333785}}
* {{인용|last1=Bannai|first1=E.|last2=Ito|first2=T.|title=On finite Moore graphs|url=http://repository.dl.itc.u-tokyo.ac.jp/dspace/handle/2261/6123|journal=Journal of the Faculty of Science, the University of Tokyo. Sect. 1 A, Mathematics|volume=20|pages=191–208|year=1973|mr=0323615|url-status=dead|archiveurl=https://web.archive.org/web/20120424231252/http://repository.dl.itc.u-tokyo.ac.jp/dspace/handle/2261/6123|archive-date=2012-04-24}}
* {{인용|last=Bollobás|first=Béla|author-link=볼로바시 벨러|publisher=[[슈프링어|Springer-Verlag]]|series=[[Graduate Texts in Mathematics]]|title=Modern Graph Theory|volume=184|year=1998}}
* {{인용|last=Dalfó|first=C.|doi=10.1016/j.laa.2018.12.035|journal=Linear Algebra and Its Applications|mr=3901732|pages=1–14|title=A survey on the missing Moore graph|volume=569|year=2019|hdl=2117/127212|s2cid=126689579|hdl-access=free|url=https://upcommons.upc.edu/bitstream/2117/127212/1/monster%2818oct2017-rev30dec2018%29.pdf}}
* {{인용|last=Damerell|first=R. M.|title=On Moore graphs|journal=Mathematical Proceedings of the Cambridge Philosophical Society|volume=74|issue=2|pages=227–236|year=1973|mr=0318004|doi=10.1017/S0305004100048015|bibcode=1973PCPS...74..227D}}
* {{인용|first1=Paul|last1=Erdős|pages=215–235|archive-date=2016-03-09|archive-url=https://web.archive.org/web/20160309214909/http://www.math-inst.hu/~p_erdos/1966-06.pdf|access-date=2010-02-23|year=1966|volume=1|url=http://www.math-inst.hu/~p_erdos/1966-06.pdf|title=On a problem of graph theory|journal=Studia Sci. Math. Hungar.|author3-link=Vera T. Sós|first3=Vera T.|last3=Sós|author2-link=Alfréd Rényi|first2=Alfréd|last2=Rényi|author1-link=에르되시 팔|url-status=dead}}.
* {{인용|author1-link=Alan Hoffman (mathematician)|last1=Hoffman|first1=Alan J.|last2=Singleton|first2=Robert R.|title=Moore graphs with diameter 2 and 3|journal=IBM Journal of Research and Development|volume=5|issue=4|year=1960|pages=497–504|doi=10.1147/rd.45.0497|mr=0140437}}
* {{인용|last1=Mačaj|first1=Martin|last2=Širáň|first2=Jozef|journal=[[Linear Algebra and Its Applications]]|pages=2381–2398|title=Search for properties of the missing Moore graph|volume=432|issue=9|year=2010|doi=10.1016/j.laa.2009.07.018|doi-access=free}}
*  {{인용|title=There is no irregular Moore graph|last=Singleton|first=Robert R.|journal=[[American Mathematical Monthly]]|volume=75|issue=1|pages=42–43|year=1968|mr=0225679|doi=10.2307/2315106|jstor=2315106}}

== 외부 링크 ==

* Brouwer, Haemers: [http://homepages.cwi.nl/~aeb/math/ipm/ipm.pdf Spectra of graphs]
* {{매스월드2|제목=Moore Graph|urlname=MooreGraph|제목2=Hoffman-Singleton Theorem|urlname2=Hoffman-SingletonTheorem}}

[[분류:정규 그래프]]
[[분류:그래프족]]