고도로 대칭적인 그래프인 페테르센 그래프는 꼭지점 전이적, 대칭, 거리 전이적인 거리 정규 그래프이다. 페테르센 그래프의 지름은 2이다. 페테르센 그래프의 자기동형군에는 120개의 원소가 있으며, 실제로 이는 대칭군이다.
대수적 그래프 이론(영어: algebraic graph theory)은 대수적 방법을 그래프에 대한 문제에 적용하는 수학의 분야이다. 이것은 기하학적, 조합론적 또는 알고리즘적인 접근 방식과 대조된다. 대수적 그래프 이론에는 선형대수학, 군론의 응용 및 그래프 불변량 연구 등 세 가지 주요 갈래가 있다.
대수적 그래프 이론의 갈래
선형대수학 응용
대수 그래프 이론의 첫 번째 갈래는 선형대수와 관련된 그래프 연구에 관한 것이다. 특히 인접행렬의 스펙트럼 또는 그래프의 라플라시안 행렬을 연구한다. 이러한 대수적 그래프 이론의 부분을 스펙트럼 그래프 이론이라고도 한다. 예를 들어 페테르센 그래프의 경우 인접 행렬의 스펙트럼은 (−2, -2, -2, -2, 1, 1, 1, 1, 1, 3)이다. 몇 가지 정리는 스펙트럼의 성질을 다른 그래프 불변량과 연관시킨다. 예시로, 지름이 D 인 연결 그래프는 적어도 D +1개의 서로 다른 스펙트럼 값을 갖는다.[1] 그래프 스펙트럼의 측면은 네트워크의 동기화 가능성을 분석하는 데 사용되었다.
군론 응용
대수 그래프 이론의 두 번째 갈래는 군론, 특히 자기 동형 사상 및 기하군론과 관련된 그래프 연구에 관한 것이다. 대칭을 기반으로 하는 다양한 그래프족(예: 대칭 그래프, 꼭짓점 전이 그래프, 변 전이 그래프, 거리 전이 그래프, 거리 정규 그래프 및 강한 정규 그래프)과, 그래프족 사이의 포함 관계에 초점을 둔다. 이러한 그래프 범주 중 일부는 목록을 작성할 수 있을 정도로 희소하다. Frucht의 정리에 따르면 모든 군은 연결 그래프(실제로는 3차 그래프)의 자기동형군으로 표현될 수 있다.[2] 군론과의 또 다른 연결은, 그룹이 주어지면 케일리 그래프로 알려진 대칭 그래프가 생성될 수 있으며 군의 구조와 관련된 속성이 있다는 것이다.[1]
교대군A4 에 대한 케일리 그래프는 3차원에서 깎은 정사면체를 형성한다. 모든 케일리 그래프는 꼭짓점 전이적이지만, 페테르센 그래프 등 일부 꼭짓점 전이적 그래프는 케일리 그래프가 아니다.페테르센 그래프의 색칠수인 세 가지 색을 사용한 그래프 색칠. 색칠 다항식에 따르면 3가지 색을 사용한 서로 다른 120가지 색칠이 존재한다.
대수 그래프 이론의 두 번째 갈래는 그래프의 대칭 성질이 스펙트럼에 반영되기 때문에 첫 번째 갈래와 관련이 있다. 특히 페테르센 그래프와 같이 고도로 대칭적인 그래프의 스펙트럼은 고유값이 많지 않다.[1] 실제로, 페테르센 그래프는 직경이 주어졌을 때 스펙트럼 고유값의 종류로 가능한 최소값인 3을 갖는다. 케일리 그래프의 경우 스펙트럼은 군의 구조, 특히 기약 지표와 직접적인 관련이 있다.[1][3]
그래프 불변량 연구
마지막으로 대수 그래프 이론의 세 번째 갈래는 그래프 불변량의 대수적 성질, 특히 색칠 다항식, 텃 다항식 및 매듭 불변량에 관한 것이다. 예를 들어, 그래프의 색칠 다항식은 그래프 색칠의 개수를 계산한다. 페테르센 그래프의 경우 색칠 다항식은이다.[1] 이를 통해 페테르센 그래프가 한 가지 또는 두 가지 색으로는 색칠될 수 없지만 세 가지 색을 사용하면 색칠 다항식에 t = 3을 대입한 값인 120가지의 서로 다른 방식으로 색칠될 수 있음을 알 수 있다. 대수적 그래프 이론의 이 영역에서는 4색 정리를 증명하려는 시도가 많은 작업에 동기를 부여하였다. 그러나, 동일한 색 다항식을 갖는 그래프의 특성화 및 어떤 다항식이 색칠 다항식인지 결정하는 것과 같은 미해결 문제가 여전히 많다.
