완전 그래프

완전 그래프(完全graph, complete graph)는 그래프 이론에서 임의의 두 정점이 정확히 하나의 간선으로 연결된 단순 그래프이다.

정의

완전 그래프는 정점 집합 내의 모든 쌍이 간선으로 직접 연결된 무방향 단순 그래프이다. 정점의 수가 n일 때, 이 완전 그래프는 Kn으로 표기하며, 총 간선 수는 n(n-1)/2개이다. 모든 정점이 서로 연결되어 있으므로 연결 그래프이며, 각 정점의 차수는 n-1이다.

성질

• Kn의 간선 수는 n(n-1)/2이다.
• Kn은 (n-1)-정규 그래프이다.
• Kn은 트리, 평면 그래프, 이분 그래프 등의 특성을 일반적으로 가지지 않는다.
• Kn은 n개의 정점을 가지는 그래프 중 가장 간선이 많은 그래프이다.
• Kn의 최소 색칠 수는 n으로, 색칠수가 최대인 예시이다.
• n ≥ 3일 때, Kn은 한붓그리기를 할 수 없다.

예시

• K1: 하나의 정점만 존재하며 간선이 없다.
• K2: 두 정점이 하나의 간선으로 연결됨.
• K3: 세 정점이 서로 연결되어 삼각형을 이룸.
• K4 이상: 정점 간 모든 연결이 이루어진 그래프로, 정점 수 증가에 따라 간선 수가 급격히 증가함.

응용

• 네트워크 설계: 모든 노드가 서로 직접 통신 가능한 구조 설계 시 참조됨.
• 그래프 이론의 경계 사례로 사용되어, 다른 그래프 특성을 시험하는 반례로 종종 등장함.
• 조합론, 알고리즘 분석 등에서 최악의 경우를 표현할 때 사용됨.

같이 보기

• 그래프 이론
• 그래프 색칠 문제
• 평면 그래프
• 정규 그래프
• 이분 그래프
• 색칠 문제

참고 문헌

• Bondy, J. A., & Murty, U. S. R. (2008). *Graph Theory*. Springer.