완전 그래프 편집하기

완전 그래프(完全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.
==각주==
[[분류:그래프]]
[[분류:그래프 이론]]