강한 정규 그래프

강한 정규 그래프 (Strongly Regular Graph)는 그래프 이론에서 다루는 특수한 종류의 정규 그래프이다. 정규 그래프란 모든 정점이 같은 수의 이웃을 가지는 그래프를 의미하며, 강한 정규 그래프는 정규 그래프의 조건을 만족하면서 추가적인 성질을 가진다.

정확히 말하면, 강한 정규 그래프는 네 개의 매개변수 (n, k, λ, μ)로 정의된다. 여기서:

• n은 그래프의 정점의 수
• k는 각 정점의 차수 (degree), 즉 각 정점이 가지는 이웃의 수
• λ (람다)는 인접한 두 정점이 공유하는 이웃의 수
• μ (뮤)는 인접하지 않은 두 정점이 공유하는 이웃의 수

즉, 그래프 내의 모든 정점은 정확히 k개의 이웃을 가지고, 인접한 두 정점은 정확히 λ개의 공통 이웃을 가지며, 인접하지 않은 두 정점은 정확히 μ개의 공통 이웃을 가져야 한다.

자명한 경우를 피하기 위해 다음과 같은 조건을 추가하기도 한다.

• 그래프는 완전 그래프나 공 그래프가 아니어야 한다. 즉, 0 < k < n - 1 이어야 한다.
• λ ≠ μ 이어야 한다.

강한 정규 그래프는 조합론, 코딩 이론, 그룹 이론 등 다양한 분야에서 응용되며, 그래프의 구조를 분석하고 특정 조건을 만족하는 그래프를 구성하는 데 중요한 역할을 한다. 예를 들어, 페일리 그래프(Paley graph)는 강한 정규 그래프의 한 예시이다. 강한 정규 그래프의 존재성과 관련된 문제는 여전히 활발하게 연구되고 있다.