정규 그래프편집자 확인

정규 그래프는 그래프 이론에서 모든 꼭짓점이 동일한 수의 이웃을 가지는 그래프이다. 즉, 그래프 내의 모든 꼭짓점이 같은 차수를 가진다. 이러한 특성은 그래프의 구조를 분석하고 분류하는 데 중요한 기준이 된다.

수학적으로는 자연수 k에 대해 모든 꼭짓점의 차수가 k인 그래프를 k-정규 그래프라고 부른다. 특히 3-정규 그래프는 '삼차 그래프' 또는 '큐빅 그래프'라는 별칭으로도 불린다. n개의 꼭짓점을 가진 k-정규 그래프가 존재하기 위해서는 n이 k+1 이상이어야 하며, n과 k의 곱이 짝수여야 한다는 필요충분조건이 있다.

대표적인 예로는 n개의 꼭짓점을 가진 완전 그래프 Kₙ이 있으며, 이는 (n-1)-정규 그래프에 해당한다. 또한, 페테르센 그래프와 완전 이분 그래프 K₃,₃는 모두 3-정규 그래프의 예시이다. 이러한 정규 그래프는 네트워크 설계, 코딩 이론, 화학 그래프 이론 등 다양한 분야에서 응용된다.

정규 그래프는 그래프 이론에서 모든 꼭짓점이 동일한 수의 이웃, 즉 같은 차수를 가지는 그래프를 말한다. 자연수 k에 대해, 모든 꼭짓점의 차수가 정확히 k인 그래프를 k-정규 그래프라고 부른다. 특히 3-정규 그래프는 삼차 그래프 또는 큐빅 그래프라는 특별한 명칭으로도 불린다.

n개의 꼭짓점을 가진 k-정규 그래프가 존재하기 위한 필요충분조건은 n이 k+1 이상이고, n과 k의 곱(nk)이 짝수라는 것이다. 이 조건은 핸드셰이킹 보조정리에 의해 유도된다. 대표적인 예로, n개의 꼭짓점을 가진 완전 그래프 Kₙ은 모든 꼭짓점의 차수가 n-1이므로 (n-1)-정규 그래프이다. 또한 페테르센 그래프와 완전 이분 그래프 K₃,₃는 모두 3-정규 그래프에 해당한다.

정규 그래프의 대표적인 예로는 완전 그래프, 페테르센 그래프, 그리고 완전 이분 그래프가 있다. 완전 그래프 Kₙ은 n개의 꼭짓점을 가지며, 각 꼭짓점은 나머지 모든 꼭짓점과 연결되어 있다. 따라서 모든 꼭짓점의 차수는 n-1로 동일하며, 이는 (n-1)-정규 그래프의 정의를 정확히 만족시킨다.

차수가 3인 그래프, 즉 3-정규 그래프는 특별히 삼차 그래프 또는 큐빅 그래프라고 불린다. 페테르센 그래프는 가장 잘 알려진 삼차 그래프의 예시 중 하나로, 10개의 꼭짓점을 가지며 복잡한 대칭 구조를 가지고 있다. 또한 완전 이분 그래프 K₃,₃ 역시 각 꼭짓점이 정확히 세 개의 변과 연결된 3-정규 그래프에 해당한다.

차수에 따른 다른 기본적인 예시들도 있다. 0-정규 그래프는 변이 하나도 없는 무변 그래프이며, 1-정규 그래프는 연결 성분이 모두 두 개의 꼭짓점을 연결하는 변, 즉 경로 그래프 K₂로 이루어져 있다. 2-정규 그래프의 각 연결 성분은 순환 그래프 또는 무한한 길이의 경로 그래프 형태를 띤다.

정규 그래프에 대한 연구는 19세기 말부터 본격적으로 시작되었다. 1880년에 피터 거스리 테이트는 모든 삼차 그래프(3-정규 그래프)가 해밀턴 경로를 가진다는 유명한 추측을 제시했다. 이는 그래프 이론의 중요한 난제 중 하나가 되었으며, 약 60년 이상 해결되지 않은 채로 남아 있었다.

이 추측은 1946년에 윌리엄 토머스 텃에 의해 반증되었다. 그는 46개의 꼭짓점을 가진 삼차 그래프이면서 해밀턴 경로를 갖지 않는 반례를 구성해냈다. 이후 텃은 1971년에 모든 이분 삼차 그래프는 해밀턴 회로를 가질 것이라는 또 다른 추측을 내놓았지만, 조지프 호턴이 96개 꼭짓점의 반례를 발견하며 이 역시 거짓임이 증명되었다.

한편, 정규 그래프의 구조에 대한 중요한 정리도 증명되었다. 크리스핀 내시윌리엄스는 2k+1개의 꼭짓점을 가진 k-정규 그래프는 항상 해밀턴 순환을 가진다는 내시윌리엄스 정리를 제시했다. 이 결과는 정규 그래프의 순환적 성질을 규명하는 데 기여했다.

• 위키백과 - 정규 그래프

• Wolfram MathWorld - Regular Graph

• Wolfram MathWorld - Cubic Graph

• Wolfram MathWorld - Strongly Regular Graph

• 위키백과 - 완전 그래프

• 위키백과 - 순환 그래프

• 위키백과 - 해밀턴 경로

• 위키백과 - 무어 그래프

• ko.wikipedia.org