무어 그래프

무어 그래프는 그래프 이론에서 주어진 차수(degree) d와 지름(diameter) k에 대해 정점의 수가 이론적으로 가능한 최대인 그래프를 말한다. 즉, 정점의 수에 대한 무어 경계를 만족하는 그래프이다. 무어 그래프는 네트워크 디자인, 오류 정정 코드 등 다양한 분야에서 활용된다.

구체적으로, 차수가 d이고 지름이 k인 그래프에서 각 정점은 최대 d개의 이웃을 가질 수 있고, 그 이웃의 이웃은 최대 d-1개 (자기 자신과 이미 연결된 정점을 제외)의 새로운 이웃을 가질 수 있다는 점을 이용하여 그래프의 최대 정점 수를 계산할 수 있다. 이 최대 정점 수를 무어 경계라고 한다.

무어 경계 (Moore Bound)는 다음과 같이 표현된다:

• n ≤ 1 + d Σ_i=0^k-1 (d - 1)ⁱ = 1 + d(d - 1)^k - 1 / (d - 2) (단, d > 2)
• n ≤ 2k + 1 (단, d = 2)

여기서 n은 정점의 수, d는 차수, k는 지름을 의미한다.

무어 경계를 만족하는 그래프를 무어 그래프라고 부르지만, 모든 d와 k에 대해 무어 그래프가 존재하는 것은 아니다. 특히, d = 2인 경우는 순환 그래프(cycle graph)가 무어 그래프가 되며, k = 1인 경우는 완전 그래프(complete graph)가 무어 그래프가 된다. d = 3, k = 2인 경우는 페테르센 그래프(Petersen graph)가 무어 그래프의 예시이다.

무어 그래프의 존재성은 미해결 문제로 남아있는 경우가 많으며, 특정 차수와 지름에 대해 무어 그래프가 존재하지 않음이 증명되기도 했다. 무어 그래프의 존재성을 연구하는 것은 그래프 이론의 중요한 분야 중 하나이다.