대수 그래프 이론

대수 그래프 이론은 수학의 한 분야로, 그래프에 관한 문제에 대수법을 적용하는 것이다. 이것은 기하학적, 조합적 또는 알고리즘적 접근법과 대조적이다. 대수 그래프 이론에는 세 가지 주요 분기가 있는데, 여기에는 선형대수의 사용, 집단 이론의 사용, 그래프 불변성의 연구가 포함된다.

대수 그래프 이론의 분과

선형대수법 사용

대수 그래프 이론의 첫 번째 분기는 선형대수와 관련된 그래프의 연구를 포함한다. 특히 인접행렬의 스펙트럼, 즉 그래프의 라플라시안 행렬(대수 그래프 이론의 이 부분을 스펙트럼 그래프 이론이라고도 한다)을 연구한다. 예를 들어 Petersen 그래프의 경우 인접 행렬의 스펙트럼은 (-2, -2, -2, -2, 1, 1, 1, 3)이다. 몇 가지 이론은 스펙트럼의 속성을 다른 그래프 속성과 연관시킨다. 간단한 예로서 직경 D의 연결된 그래프는 그 스펙트럼에서 D+1 이상의 구별되는 값을 가질 것이다.^[1] 그래프의 스펙트럼 측면은 네트워크의 동기화성을 분석하는 데 사용되었다.

집단이론 사용

자동화에 의해 정의된 그래프 패밀리
거리 변환의	→	거리 규칙의	←	매우 규칙적인.
↓
대칭(대칭 변환)	←	t-변환, t ≥ 2		꼬불꼬불한
↓
(연결된 경우) 정점 및 에지 변환	→	가장자리-변환적이고 규칙적인	→	가장자리-변환성
↓		↓		↓
정점 변환의	→	정칙의	→	(양립할 경우) 복엽의
↑
케이리 그래프	←	무궤도적		비대칭의

대수 그래프 이론의 두 번째 분기는 그룹 이론, 특히 자동형 그룹과 기하학적 그룹 이론과 관련하여 그래프의 연구를 포함한다. 대칭(대칭 그래프, 정점-변환 그래프, 에지-변환 그래프, 거리-변환 그래프, 거리-정규 그래프, 강력 정규 그래프 등)에 기반한 다양한 그래프 패밀리와 이들 패밀리 간의 포함 관계에 초점을 맞춘다. 이러한 그래프 범주의 일부는 그래프 목록을 작성할 수 있을 정도로 희소하다. Frucht의 정리로는, 모든 집단을 연결된 그래프(실제, 입방 그래프의 자동형 집단)로 나타낼 수 있다.^[2] 그룹 이론과의 또 다른 연결은 어떤 그룹이든 Cayley graph로 알려진 대칭 그래프가 생성될 수 있으며, 이러한 그래프는 그룹의 구조와 관련된 속성을 가지고 있다는 것이다.^[1]

이 대수 그래프 이론의 두 번째 분기는 그래프의 대칭 특성이 스펙트럼에 반영되기 때문에 첫 번째 분기와 관련이 있다. 특히 피터슨 그래프와 같이 대칭성이 높은 그래프의 스펙트럼에는 뚜렷한 값이^[1] 거의 없다(피터슨 그래프에는 직경을 고려할 때 가능한 최소값인 3이 있다). Cayley 그래프의 경우, 스펙트럼은 그룹의 구조, 특히 수정할 수 없는 문자와 직접 관련될 수 있다.^[1][3]

그래프 불변성 연구

마지막으로 대수 그래프 이론의 제3분기는 그래프 불변성, 특히 색도 다항성, 투테 다항성 및 매듭 불변성의 대수적 특성에 관한 것이다. 예를 들어, 그래프의 색도 다항식은 적절한 정점 색상의 수를 카운트한다. For the Petersen graph, this polynomial is ${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$.^[1] In particular, this means that the Petersen graph cannot be properly colored with one or two 색상은 3가지 색상으로 120가지 방법으로 색칠할 수 있다. 대수 그래프 이론의 이 영역에서의 많은 작업은 4색 정리를 증명하려는 시도에 의해 동기 부여되었다. 그러나 동일한 색도 다항식을 갖는 그래프의 특성화, 색도인 다항식을 결정하는 등 아직 해결되지 않은 문제가 많다.

참고 항목

• 스펙트럼 그래프 이론
• 대수적 결합론
• 대수연결성
• 둘마지-멘델손 분해
• 그래프 속성
• 인접 행렬

참조

외부 링크

• 위키미디어 커먼스의 대수 그래프 이론과 관련된 매체