무어 그래프

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 차수 및 지름에 따른 꼭짓점 개수의 상한
3. 케이지로서의 무어 그래프
4. 예시
참조

1. 개요

무어 그래프는 주어진 차수와 지름을 갖는 그래프 중 최대 개수의 꼭짓점을 갖는 그래프로, 그래프 이론에서 중요한 개념이다. 최대 차수 d와 지름 k를 갖는 그래프의 꼭짓점 개수 상한을 만족하며, 호프만과 싱글턴에 의해 정의되었다. 무어 그래프는 지름 k, 둘레 2k+1을 만족하는 그래프와 동치이며, 케이지의 예시이기도 하다. 완전 그래프, 홀수 순환 그래프, 페테르센 그래프, 호프만-싱글턴 그래프 등이 무어 그래프의 예시이며, 차수가 57인 무어 그래프의 존재 여부는 미해결 문제로 남아있다.

더 읽어볼만한 페이지

정규 그래프 - 페일리 그래프
페일리 그래프는 유한체와 제곱수를 기반으로 구성되며, 강하게 정규적이고 자기 여 그래프이며 해밀턴 순환 그래프이다.
정규 그래프 - 완전 그래프
완전 그래프는 그래프 내 모든 꼭짓점 쌍이 변으로 연결된 그래프로, 꼭짓점 수 n에 따라 K_n으로 표기되며 n(n-1)/2개의 변을 가지고, 사회 연결망 분석 등 다양한 분야에 응용된다.
그래프족 - 척도 없는 네트워크
척도 없는 네트워크는 네트워크 과학에서 연결 정도 분포가 멱법칙을 따르는, 즉 일부 허브 노드가 압도적으로 많은 연결을 가지는 불균등한 연결 구조를 가진 네트워크를 의미하며, 바라바시-앨버트 모델로 설명된다.
그래프족 - 정규 그래프
정규 그래프는 그래프 이론에서 모든 꼭짓점의 차수가 동일한 그래프를 의미하며, 각 꼭짓점이 k개의 변에 잇닿아 있는 그래프를 k-정규 그래프라고 하고, 여러 성질 및 다양한 분야에 응용된다.

무어 그래프
정의
정의	모든 꼭짓점의 차수가 d인 정규 그래프 G에서, 임의의 두 꼭짓점 사이의 최단 경로 길이가 k 이하이다. 차수 d와 둘레 을 가질 때, 꼭짓점의 수 n은 (m – n + 1)}}를 만족한다. 여기서 m은 무어 경계이다. 이러한 그래프를 무어 그래프라고 한다.
성질
둘레	둘레가 지름의 두 배보다 큰 정규 그래프이다.
예시
알려진 무어 그래프	완전 그래프 피터슨 그래프 히그먼-심스 그래프
미해결 문제
무어 그래프의 존재 여부	둘레가 5이고 차수가 57인 무어 그래프가 존재하는가?

2. 차수 및 지름에 따른 꼭짓점 개수의 상한

최대 차수가 ''d''이고 지름이 ''k''인 그래프가 가질 수 있는 꼭짓점의 최대 개수에는 상한선이 존재한다. 이 상한은 그래프 내의 한 꼭짓점에서 시작하는 너비 우선 탐색(BFS)을 통해 유도될 수 있으며, BFS 트리의 각 깊이에 존재할 수 있는 최대 꼭짓점 수를 계산하여 합하는 방식으로 구해진다.

주어진 최대 차수 ''d''와 지름 ''k''를 갖는 그래프의 꼭짓점 개수 ''N''은 다음 부등식을 만족한다.

$N \le 1 + d \sum_{i=0}^{k-1} (d-1)^i$

이 수식은 주어진 조건을 만족하는 그래프가 가질 수 있는 꼭짓점 수의 이론적인 최댓값을 나타낸다. 호프만(A. J. Hoffman)과 싱글턴(R. R. Singleton)은 1960년에 바로 이 상한값을 정확히 만족하는 그래프, 즉 위 부등식에서 등호( $=$ )가 성립하는 그래프를 무어 그래프로 정의하였다. 따라서 무어 그래프는 정의에 따라, 동일한 최대 차수와 지름을 갖는 모든 그래프 중에서 가장 많은 꼭짓점을 가지는 그래프이다.

2. 1. 너비 우선 탐색을 통한 상한 계산

페테르센 그래프는 차수 3, 지름 2인 무어 그래프이다. 이 그래프에서 임의의 꼭짓점에서 시작하는 너비 우선 탐색 트리는 각 깊이 ''i'' ≥ 1 에 ''d''(''d'' − 1)^''i''−1 개의 꼭짓점을 가진다.

최대 차수 ''d''와 지름 ''k''를 갖는 임의의 그래프 ''G''를 가정해 보자. 어떤 꼭짓점 ''v''에서 시작하는 너비 우선 탐색(BFS)으로 생성되는 나무 구조를 생각할 수 있다.

이 BFS 트리는 다음과 같은 구조를 가진다.

깊이 0: 꼭짓점 ''v'' 자기 자신, 1개의 꼭짓점만 존재한다.
깊이 1: ''v''의 이웃들. 최대 ''d''개의 꼭짓점이 존재한다. (''v''의 차수가 최대 ''d''이므로)
깊이 2: 깊이 1에 있는 각 꼭짓점의 새로운 이웃들. 깊이 1의 꼭짓점들은 이미 ''v''와 연결되어 있으므로, 각각 최대 ''d''-1개의 새로운 이웃(깊이 2의 꼭짓점)을 가질 수 있다. 따라서 깊이 2에는 최대 ''d''(''d''-1)개의 꼭짓점이 존재한다.
깊이 ''i'' (1 ≤ ''i'' ≤ ''k''): 유사한 논리로, 깊이 ''i''-1의 각 꼭짓점은 이미 깊이 ''i''-2의 꼭짓점과 연결되어 있으므로, 최대 ''d''-1개의 새로운 이웃(깊이 ''i''의 꼭짓점)을 가질 수 있다. 따라서 깊이 ''i''에는 최대 ''d''(''d''-1)^''i''-1개의 꼭짓점이 존재한다.

BFS 트리는 지름 ''k''까지 확장되므로, 그래프 ''G''의 전체 꼭짓점 개수 ''N''은 각 깊이에 있는 꼭짓점 수의 상한을 모두 더한 값보다 작거나 같아야 한다. 이를 수식으로 표현하면 다음과 같다.

N \le 1 + \sum_{i=1}^{k} d(d-1)^{i-1} = 1 + d \sum_{j=0}^{k-1} (d-1)^j

호프만(Hoffman)과 싱글턴(Singleton)은 1960년 논문에서 무어 그래프를 바로 이 상한값을 정확히 만족하는 그래프, 즉 꼭짓점의 개수가

1 + d \sum_{j=0}^{k-1} (d-1)^j

개인 그래프로 정의했다. 따라서 무어 그래프의 정의에 따라, 주어진 최대 차수 ''d''와 지름 ''k''를 갖는 모든 그래프 중에서 가장 많은 꼭짓점을 가진다.

이후 싱글턴은 1968년에 무어 그래프가 지름 ''k''와 둘레 2''k''+1을 갖는 정규 그래프와 동등한 정의임을 보였다. 지름과 둘레에 대한 이 조건은 그래프가 반드시 ''d''-정규 그래프(모든 꼭짓점의 차수가 ''d''로 동일한 그래프)여야 함을 내포하며, 위에서 유도된 꼭짓점 수 상한 공식을 만족하게 한다.

2. 2. 무어 그래프의 정의

최대 차수가 ''d''이고 지름이 ''k''인 임의의 그래프 ''G''를 생각해보자. 어떤 꼭짓점 ''v''에서 시작하는 너비 우선 탐색(BFS)으로 형성된 트리를 고려할 수 있다. 이 트리는 깊이 0에는 ''v'' 자신, 즉 1개의 꼭짓점만을 가진다. 깊이 1에는 ''v''의 이웃들이 오는데, 최대 ''d''개까지 있을 수 있다. 다음 깊이인 깊이 2에는 최대 ''d''(''d'' − 1)개의 꼭짓점이 올 수 있다. 이는 깊이 1의 각 꼭짓점이 이미 ''v''와 연결되어 있으므로, 나머지 최대 ''d'' − 1개의 이웃만이 깊이 2에 속할 수 있기 때문이다. 일반적으로 이러한 논리를 확장하면, 깊이 ''i'' (1 ≤ ''i'' ≤ ''k'')에는 최대 ''d''(''d'' − 1)^''i''−1개의 꼭짓점이 존재함을 알 수 있다. 따라서 그래프 ''G''가 가질 수 있는 꼭짓점 개수의 상한(최댓값)은 모든 깊이의 꼭짓점 수를 합한 다음과 같다.

:

1+d\sum_{i=0}^{k-1}(d-1)^i

호프만(Hoffman)과 싱글턴(Singleton)은 1960년에 무어 그래프를 바로 이 꼭짓점 개수 상한을 정확히 만족시키는 그래프로 정의하였다. 따라서 무어 그래프는 주어진 최대 차수 ''d''와 지름 ''k''를 갖는 모든 그래프 중에서 가능한 가장 많은 수의 꼭짓점을 가진다.

이후 싱글턴은 1968년에 무어 그래프를 '지름이 ''k''이고 둘레가 2''k'' + 1인 그래프'로 정의하는 것이 원래 정의와 동등함을 보였다. 이 두 가지 조건(지름 ''k'', 둘레 2''k'' + 1)을 만족하는 그래프는 필연적으로 어떤 ''d''에 대해 ''d''-정규 그래프가 되며, 위에서 유도한 꼭짓점 개수 공식 또한 만족하게 된다.

2. 3. 다른 정의

무어 그래프는 원래 호프만(A. J. Hoffman)과 싱글턴(R. R. Singleton)이 1960년에 최대 차수

d

와 지름

k

를 가지는 그래프의 정점 수 상한인

:

1+d\sum_{i=0}^{k-1}(d-1)^i

을 정확히 만족하는 그래프로 정의하였다. 이 정의에 따르면, 무어 그래프는 주어진 최대 차수와 지름에 대해 가능한 가장 많은 정점을 가지는 그래프이다.

이후 싱글턴은 1968년에 무어 그래프를 다르게 정의할 수도 있음을 보였다. 그의 연구에 따르면, 무어 그래프는 지름 $k$ 와 둘레(girth) $2k+1$ 을 가지는 그래프와 동등하다. 이 두 가지 조건(지름

k

, 둘레

2k+1

)을 동시에 만족하는 그래프는 필연적으로 어떤 차수

d

에 대해

d

-정규 그래프가 되며, 위에서 언급된 정점 수 상한 공식을 만족하게 된다. 즉, 이 두 정의는 서로 동치이다.

3. 케이지로서의 무어 그래프

무어 그래프는 최대 차수와 지름이라는 조건 외에도, 그래프의 최소 차수 ''d''와 안둘레 ''g''(그래프 내 가장 짧은 순환의 길이)라는 조건을 통해서도 중요한 성질을 갖는다. 주어진 최소 차수와 안둘레에 대해, 그래프가 가질 수 있는 꼭짓점의 개수에는 특정 하한선이 존재한다. 이 하한은 너비 우선 탐색과 같은 방법을 통해 유도될 수 있다.

특히, 그래프의 최소 차수가 ''d''이고 안둘레가 홀수인 2''k'' + 1일 경우, 꼭짓점 수의 이론적인 최솟값, 즉 하한은 다음 수식으로 주어진다.

$1 + d \sum_{i=0}^{k-1} (d-1)^i$

지름이 ''k''인 무어 그래프는 안둘레가 정확히 2''k'' + 1이며, 위에서 제시된 꼭짓점 수의 하한을 정확하게 만족시킨다. 그래프 이론에서, 주어진 최소 차수와 안둘레를 가지면서 꼭짓점 수가 이론적으로 가능한 가장 적은 그래프를 케이지(cage)라고 부른다. 따라서 정의상 모든 (홀수 안둘레) 무어 그래프는 케이지의 한 종류가 된다.

비슷하게, 안둘레가 짝수인 2''k''인 경우에도 꼭짓점 수의 하한이 존재하며, 이는 $2 \sum_{i=0}^{k-1} (d-1)^i$ 로 주어진다. 때때로 무어 그래프의 정의를 확장하여 이 짝수 안둘레 경우의 하한을 정확히 만족하는 그래프까지 포함하기도 하는데, 이렇게 확장된 정의에 따른 무어 그래프 역시 케이지이다.

3. 1. 너비 우선 탐색을 통한 하한 계산

그래프의 최대 차수와 지름을 이용해 꼭짓점 개수의 상한을 구하는 것과 비슷하게, 최소 차수와 안둘레를 이용하여 꼭짓점 개수의 하한을 계산할 수 있다.

그래프 ''G''의 최소 차수가 ''d''이고 안둘레가 홀수인 2''k'' + 1이라고 가정하자. 임의의 시작 꼭짓점 ''v''를 선택하고, ''v''를 루트(뿌리)로 하는 너비 우선 탐색(BFS) 트리를 만든다.

깊이 0에는 루트 꼭짓점 ''v'' 하나만 존재한다. (1개)
깊이 1에는 ''v''의 이웃들이며, 최소 ''d''개의 꼭짓점이 존재한다.
깊이 2에는 최소 ''d''(''d'' − 1)개의 꼭짓점이 존재한다. 만약 깊이 1의 서로 다른 두 꼭짓점이 깊이 2에서 같은 이웃을 공유하거나 서로 인접한다면, 그래프의 안둘레가 2''k'' + 1보다 작아지므로, 안둘레 제약 조건에 따라 이는 불가능하다. 따라서 깊이 1의 각 꼭짓점은 자신과 루트 ''v''를 제외하고 최소 ''d''-1개의 새로운 이웃을 깊이 2에서 가져야 한다.
일반적으로, 깊이 ''i'' (1 ≤ ''i'' ≤ ''k'')에는 최소 ''d''(''d'' − 1)^''i''-1개의 꼭짓점이 존재한다.

이러한 각 깊이(계층)의 꼭짓점 수를 모두 더하면, 그래프 ''G''의 총 꼭짓점 수에 대한 하한은 다음과 같다.

1 + d\sum_{i=0}^{k-1}(d-1)^i

무어 그래프는 이 하한을 정확히 만족시킨다. 지름이 ''k''인 무어 그래프의 안둘레는 정확히 2''k'' + 1이다. 만약 안둘레가 이보다 길다면 더 많은 꼭짓점이 필요하게 되고, 만약 더 짧은 주기가 존재한다면 너비 우선 탐색 트리의 처음 ''k''개 깊이 중 일부에서 꼭짓점 수가 부족하게 되어 위에서 계산한 하한을 만족시킬 수 없다. 따라서 모든 무어 그래프는 주어진 최소 차수 ''d''와 안둘레 2''k'' + 1을 갖는 그래프 중에서 꼭짓점 수가 가장 적으며, 이는 케이지의 정의와 일치한다.

안둘레가 짝수인 2''k''인 경우에도 유사한 논의가 가능하다. 이 경우, 너비 우선 탐색 트리를 단일 꼭짓점이 아닌, 임의의 한 변(모서리)의 중간점에서 시작하여 구성한다. 최소 차수가 ''d''이고 안둘레가 2''k''인 그래프의 꼭짓점 수 하한은 다음과 같다.

2\sum_{i=0}^{k-1}(d-1)^i

이 식은 다음과 같이 표현되기도 한다.

1+(d-1)^{k-1}+d\sum_{i=0}^{k-2}(d-1)^i

(이 두 번째 식은 단일 정점에서 시작하는 너비 우선 탐색 트리의 꼭짓점 수를 계산하되, 트리 마지막 레벨의 꼭짓점이 이전 레벨의 ''d''개 꼭짓점과 인접할 가능성을 고려한 결과이다.)

무어 그래프의 정의를 확장하여 이 짝수 안둘레 경우의 하한을 정확히 만족하는 그래프를 포함시키기도 하는데, 이 경우에도 해당 그래프는 케이지가 된다.

3. 2. 케이지의 정의

그래프의 최대 차수와 지름을 사용하여 꼭짓점 개수의 상한을 구하는 것과 달리, 최소 차수와 안둘레(girth)를 사용하여 꼭짓점 개수의 하한을 구할 수 있다.

최소 차수가 ''d''이고 안둘레가 홀수인 2''k'' + 1인 그래프 ''G''를 생각해보자. 임의의 꼭짓점 ''v''를 선택하여 이를 루트로 하는 너비 우선 탐색(BFS) 트리를 구성하면, 각 깊이(레벨)별 꼭짓점 수를 다음과 같이 추정할 수 있다.

깊이 0에는 루트 꼭짓점 ''v'' 하나만 존재한다. (1개)
깊이 1에는 ''v''에 직접 연결된 이웃 꼭짓점들이 있으며, 최소 차수 조건에 따라 최소 ''d''개가 존재한다.
깊이 2 이상 (''k'' > 1인 경우)을 살펴보자. 만약 깊이 ''i'' (1 ≤ ''i'' ≤ ''k'')의 어떤 꼭짓점이 깊이 ''i''-1의 꼭짓점 두 개 이상과 연결되거나, 같은 깊이의 두 꼭짓점이 서로 연결된다면, 그래프의 안둘레가 2''k''+1보다 작아지게 된다. 이는 가정에 어긋난다. 따라서 깊이 1의 각 꼭짓점은 자신과 루트 ''v''를 제외하고 최소 ''d''-1개의 새로운 이웃을 깊이 2에 가져야 하며, 이들은 서로 겹치지 않는다. 그러므로 깊이 2에는 최소 ''d''(''d''-1)개의 꼭짓점이 존재한다.
같은 논리로, 깊이 ''i'' (1 ≤ ''i'' ≤ ''k'')에는 최소한 ''d''(''d''-1)^''i''-1개의 꼭짓점이 존재해야 한다.

따라서 그래프 ''G''의 전체 꼭짓점 개수는 각 깊이에 있는 최소 꼭짓점 수의 합보다 크거나 같아야 하며, 그 하한은 다음과 같이 계산된다.

N \ge 1 + d + d(d-1) + \dots + d(d-1)^{k-1} = 1 + d \sum_{i=0}^{k-1} (d-1)^i

무어 그래프는 꼭짓점 개수가 정확히 이 하한과 일치하는 그래프이다. 또한, 무어 그래프의 안둘레는 정확히 2''k''+1이다. 만약 안둘레가 2''k''+1보다 크다면 더 많은 꼭짓점이 필요하게 되고, 만약 2''k''+1보다 짧은 순환이 존재한다면 BFS 트리의 처음 ''k''개 깊이 중 일부에서 꼭짓점 수가 부족하게 되어 위에서 구한 하한을 만족시킬 수 없게 된다.

결론적으로, 최소 차수가 ''d''이고 안둘레가 2''k''+1인 모든 그래프 중에서 무어 그래프는 꼭짓점 수가 가장 적다. 이렇게 주어진 최소 차수와 안둘레를 가지면서 꼭짓점 수가 가장 적은 그래프를 케이지라고 부른다. 따라서 모든 (홀수 안둘레) 무어 그래프는 케이지이다.

안둘레가 짝수인 2''k''인 경우에도 비슷한 논의를 적용할 수 있다. 최소 차수가 ''d''이고 안둘레가 2''k''인 그래프의 꼭짓점 개수 하한은 다음과 같다.

N \ge 2 \sum_{i=0}^{k-1} (d-1)^i

이 하한은 때때로 다음과 같은 형태로 표현되기도 한다.

N \ge 1 + (d-1)^{k-1} + d \sum_{i=0}^{k-2} (d-1)^i

(이 두 번째 식은 단일 꼭짓점에서 시작하는 BFS 트리를 고려하여, 트리의 마지막 레벨 ''k''의 꼭짓점이 레벨 ''k''-1의 꼭짓점 ''d''개와 연결될 수 있는 가능성을 반영하여 유도된 것이다.)

무어 그래프의 정의를 확장하여, 짝수 안둘레의 경우에도 이 하한을 정확히 만족하는 그래프를 포함시키기도 한다. 이 경우에도 이러한 그래프들은 정의상 케이지가 된다.

3. 3. 무어 그래프와 케이지의 관계

그래프의 최대 차수와 지름으로 꼭짓점 수의 상한을 구하는 것과 비슷하게, 그래프의 최소 차수와 안둘레(girth, 가장 짧은 순환의 길이)를 이용하면 꼭짓점 수의 하한을 구할 수 있다.

어떤 그래프 ''G''의 최소 차수가 ''d''이고 안둘레가 2''k'' + 1이라고 가정해보자. 임의의 꼭짓점 ''v''를 시작점으로 하여 너비 우선 탐색(BFS) 트리를 만들 수 있다. 이 트리에서 깊이 0에는 시작점 ''v'' 하나만 있고, 깊이 1에는 ''v''와 직접 연결된 꼭짓점들이 최소 ''d''개 존재한다. 만약 ''k'' > 1이라면, 깊이 2에 있는 꼭짓점들은 깊이 1에 있는 꼭짓점과 연결되는데, 안둘레 제약 조건 때문에 깊이 2의 한 꼭짓점이 깊이 1의 두 개 이상의 꼭짓점과 연결될 수 없다. 만약 그렇다면 안둘레 2''k''+1보다 짧은 순환(cycle)이 생기기 때문이다. 따라서 깊이 2에는 최소 ''d''(''d'' − 1)개의 꼭짓점이 존재한다. 깊이 1의 각 꼭짓점은 자신과 시작점 ''v''를 제외하고 최소 ''d''-1개의 다른 이웃을 가져야 하며, 이 이웃들은 깊이 2에 위치하게 된다. 또한 안둘레 조건 때문에 깊이 1의 서로 다른 두 꼭짓점이 깊이 2의 같은 꼭짓점과 연결될 수 없다.

같은 방식으로, 깊이 ''i'' (1 ≤ ''i'' ≤ ''k'')에는 최소 ''d''(''d'' − 1)^''i''-1개의 꼭짓점이 존재해야 한다. 따라서 깊이 0부터 ''k''까지 모든 꼭짓점 수를 합하면, 그래프 ''G''의 총 꼭짓점 수 ''n''은 다음 하한을 만족해야 한다:

n \ge 1 + d \sum_{i=0}^{k-1} (d-1)^i = 1 + d + d(d-1) + \dots + d(d-1)^{k-1}

무어 그래프는 정의상 지름이 ''k''이고 최대 차수가 ''d''일 때 꼭짓점 수가 최대인 그래프인데, 흥미롭게도 위에서 유도한 꼭짓점 수의 하한을 정확히 만족한다. 지름이 ''k''인 무어 그래프의 안둘레는 정확히 2''k'' + 1이다. 만약 안둘레가 이보다 길다면 더 많은 꼭짓점이 필요하게 되고, 반대로 더 짧은 순환이 존재한다면 BFS 트리 구성 시 특정 깊이에서 필요한 최소 꼭짓점 수를 채우지 못하게 되어 하한을 만족시킬 수 없다.

결론적으로, 모든 무어 그래프는 주어진 최소 차수 ''d''와 안둘레 2''k'' + 1을 갖는 그래프 중에서 꼭짓점 수가 가장 적은 그래프이다. 이러한 성질을 만족하는 그래프를 케이지(cage)라고 부르므로, 모든 무어 그래프는 케이지의 한 종류이다.

비슷한 방식으로 짝수 안둘레 2''k''를 갖는 그래프에 대해서도 꼭짓점 수의 하한을 유도할 수 있다. 이 경우 최소 차수가 ''d''인 그래프의 꼭짓점 수 ''n''은 다음 하한을 만족한다:

n \ge 2 \sum_{i=0}^{k-1} (d-1)^i = 2(1 + (d-1) + \dots + (d-1)^{k-1})

때로는 무어 그래프의 정의를 확장하여, 이 짝수 안둘레 경우의 하한을 정확히 만족하는 그래프까지 포함하기도 한다. 이렇게 확장된 정의에 따른 무어 그래프 역시 케이지가 된다.

4. 예시

호프만-싱글턴 정리에 따르면, 둘레가 5인 무어 그래프는 차수가 2, 3, 7 또는 57이어야 한다. 알려진 무어 그래프의 예시는 다음과 같다.

$n > 2$ 인 완전 그래프 $K_n$ (지름 1, 둘레 3, 차수 $n-1$ )
홀수 순환 그래프 $C_{2n+1}$ (지름 $n$ , 둘레 $2n+1$ , 차수 2)
페테르센 그래프 (지름 2, 둘레 5, 차수 3)
호프만-싱글턴 그래프 (지름 2, 둘레 5, 차수 7)
존재 여부가 아직 밝혀지지 않은, 지름 2, 둘레 5, 차수 57의 가상 그래프. 이러한 그래프의 존재는 그래프 이론의 중요한 미해결 문제 중 하나이다.

알려진 모든 무어 그래프(차수 57 그래프 제외)는 정점 추이 그래프이다. 만약 차수 57의 무어 그래프가 존재한다면, 이 그래프는 정점 추이 그래프가 될 수 없다는 것이 증명되었다.

무어 그래프의 정의를 짝수 둘레까지 허용하도록 일반화하면, 다음과 같은 예시들이 포함된다. 이들은 일반화 다각형의 인시던스 그래프에 해당하기도 한다.

짝수 순환 그래프 $C_{2n}$
완전 이분 그래프 $K_{n,n}$ (둘레 4)
히우드 그래프 (차수 3, 둘레 6)
투트-콕서터 그래프 (차수 3, 둘레 8)

일반적으로, 위에 나열된 그래프 외의 모든 무어 그래프는 둘레가 5, 6, 8 또는 12여야 한다.^[2] 짝수 둘레의 경우, 이는 일반화된

n

각형에 대한

n

의 가능한 값에 관한 Feit-Higman 정리와도 관련이 있다.

4. 1. 완전 그래프

호프만-싱글턴 정리에서 다루는 둘레가 5인 경우 외에도 무어 그래프의 예시가 존재한다. 그중 하나는

n > 2

인 완전 그래프

K_n

이다. 이 그래프는 지름 1, 둘레 3, 차수

n-1

,

n

개의 꼭짓점을 가진다.

4. 2. 홀수 순환 그래프

홀수 개의 꼭짓점을 가지는 순환 그래프 ''C''_2''n''+1는 무어 그래프의 한 예이다. 이 그래프는 지름이 ''n'', 둘레가 2''n'' + 1, 차수가 2이며, 꼭짓점의 개수는 2''n'' + 1개이다.

4. 3. 페테르센 그래프

페테르센 그래프는 무어 그래프의 한 종류이다. 호프만-싱글턴 정리에 따르면, 둘레가 5인 무어 그래프는 차수가 2, 3, 7 또는 57 중 하나여야 한다. 페테르센 그래프는 이 조건 중 차수가 3인 경우에 해당하며, 무어 그래프의 정의를 만족시킨다.

페테르센 그래프는 다음과 같은 구체적인 특징을 가진다.

지름: 2
둘레: 5
차수: 3
꼭짓점 개수: 10

4. 4. 호프만-싱글턴 그래프

호프만-싱글턴 정리에 따르면, 둘레(girth)가 5인 무어 그래프는 반드시 차수가 2, 3, 7 또는 57 중 하나여야 한다. 현재까지 알려진 둘레 5의 무어 그래프는 다음과 같다.

홀수 순환 그래프 ''C''_2''n''+1 (지름 ''n'', 둘레 2''n'' + 1, 차수 2, 꼭짓점 2''n'' + 1. 예를 들어 ''n''=2일 때 ''C''₅는 지름 2, 둘레 5, 차수 2, 꼭짓점 5)
페테르센 그래프 (지름 2, 둘레 5, 차수 3, 꼭짓점 10)
'''호프만-싱글턴 그래프''' (지름 2, 둘레 5, 차수 7, 꼭짓점 50)
존재 여부가 알려지지 않은 가상의 그래프 (지름 2, 둘레 5, 차수 57, 꼭짓점 3250). 이러한 그래프가 실제로 존재하는지는 그래프 이론 분야의 중요한 미해결 문제 중 하나다.

'''호프만-싱글턴 그래프'''는 지름이 2이고 둘레가 5이며, 모든 꼭짓점의 차수가 7인 조건을 만족하는 무어 그래프다. 이 그래프는 총 50개의 꼭짓점을 가지고 있으며, 페테르센 그래프와 더불어 둘레 5인 무어 그래프의 대표적인 예시로 연구되고 있다.

현재까지 알려진 다른 무어 그래프들(아직 존재가 증명되지 않은 차수 57 그래프는 제외)과 마찬가지로, 호프만-싱글턴 그래프는 정점 전이 그래프다. 이는 그래프 내의 모든 꼭짓점이 구조적으로 서로 동등한 위치에 있다는 것을 의미한다. 참고로, 만약 차수 57의 무어 그래프가 존재한다고 가정할 경우, 이 그래프는 정점 전이 그래프가 될 수 없다는 것이 증명되어 있다.

4. 5. 차수 57의 무어 그래프

호프만-싱글턴 정리에 따르면, 내주가 5인 무어 그래프는 차수가 2, 3, 7 또는 57이어야 한다. 이 중 차수가 57인 무어 그래프는 지름 2, 내주 5, 정점 3250개를 가질 것으로 예상되는 가상의 그래프이다.^[2]

이러한 그래프가 실제로 존재하는지는 아직 밝혀지지 않았으며, 이는 그래프 이론 분야의 유명한 미해결 문제 중 하나이다. 만약 차수 57의 무어 그래프가 존재한다면, 다른 알려진 무어 그래프(페테르센 그래프, 호프만-싱글턴 그래프 등)와는 달리 정점 전이 그래프가 될 수 없다는 점이 Higman에 의해 증명되었다. 이는 해당 그래프의 자기 동형군의 위수가 최대 375로, 그래프의 정점 개수인 3250개보다 작기 때문이다.

4. 6. 짝수 내주를 갖는 무어 그래프

무어 그래프의 정의를 짝수 내주(girth)까지 허용하도록 일반화하면, 짝수 내주를 갖는 무어 그래프는 일반화 다각형의 (퇴화 가능성이 있는) 인시던스 그래프에 해당한다.^[2] 이러한 그래프의 예시는 다음과 같다.

짝수 순환 그래프 $C_{2n}$
내주가 4인 완전 이분 그래프 $K_{n,n}$
차수가 3이고 내주가 6인 히우드 그래프
차수가 3이고 내주가 8인 투트-콕서터 그래프

더 일반적으로, 알려진 무어 그래프 중 앞서 언급되지 않은 것들은 내주가 5, 6, 8 또는 12여야 한다.^[2] 짝수 내주의 경우, 이는 일반화된 ''n''각형에 대한 ''n''의 가능한 값에 관한 Feit-Higman 정리와도 관련이 있다.

참조

_[1] 논문
_[2] 논문

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com