대수적 그래프 이론 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Petersen1_tiny.svg|섬네일|200x200픽셀| 고도로 대칭적인 그래프인 [[페테르센 그래프]]는 꼭지점 전이적, [[대칭 그래프|대칭]], 거리 전이적인 거리 정규 그래프이다. 페테르센 그래프의 [[지름]]은 2이다. 페테르센 그래프의 [[자기동형군]]에는 120개의 원소가 있으며, 실제로 이는 [[대칭군 (군론)|대칭군]] <math>S_5</math>이다.]]

'''대수적 그래프 이론'''({{llang|en|algebraic graph theory}})은 [[대수학|대수적]] 방법을 [[그래프 (수학)|그래프]]에 대한 문제에 적용하는 [[수학]]의 분야이다. 이것은 기하학적, [[조합론]]적 또는 [[그래프 이론|알고리즘]]적인 접근 방식과 대조된다. 대수적 그래프 이론에는 [[선형대수학]], [[군론]]의 응용 및 [[그래프 속성|그래프 불변량]] 연구 등 세 가지 주요 갈래가 있다.

== 대수적 그래프 이론의 갈래 ==

=== 선형대수학 응용 ===
대수 그래프 이론의 첫 번째 갈래는 [[선형대수학|선형대수]]와 관련된 그래프 연구에 관한 것이다. 특히 [[인접행렬]]의 [[고유값 분해|스펙트럼]] 또는 그래프의 [[그래프 라플라스 연산자|라플라시안 행렬]]을 연구한다. 이러한 대수적 그래프 이론의 부분을 스펙트럼 그래프 이론이라고도 한다. 예를 들어 [[페테르센 그래프]]의 경우 인접 행렬의 스펙트럼은 (−2, -2, -2, -2, 1, 1, 1, 1, 1, 3)이다. 몇 가지 정리는 스펙트럼의 성질을 다른 그래프 불변량과 연관시킨다. 예시로, [[거리 (그래프 이론)|지름]]이 ''D'' 인 [[연결성(그래프 이론)|연결 그래프]]는 적어도 ''D'' +1개의 서로 다른 스펙트럼 값을 갖는다.<ref name="biggs">{{인용 | 저자=Biggs, Norman | 제목=Algebraic Graph Theory | 판=2nd | 위치=Cambridge | 출판사=Cambridge University Press | 연도=1993 | isbn=0-521-45897-8 | postscript=<!--none-->}}</ref> 그래프 스펙트럼의 측면은 [[네트워크 이론|네트워크]]의 [[동기화]] 가능성을 분석하는 데 사용되었다.

=== 군론 응용 ===
대수 그래프 이론의 두 번째 갈래는 [[군론]], 특히 [[자기 동형 사상]] 및 [[기하군론]]과 관련된 그래프 연구에 관한 것이다. [[대칭]]을 기반으로 하는 다양한 그래프족(예: [[대칭 그래프]], 꼭짓점 전이 그래프, 변 전이 그래프, 거리 전이 그래프, 거리 정규 그래프 및 강한 정규 그래프)과, 그래프족 사이의 포함 관계에 초점을 둔다. 이러한 그래프 범주 중 일부는 목록을 작성할 수 있을 정도로 희소하다. Frucht의 정리에 따르면 모든 [[군 (수학)|군]]은 연결 그래프(실제로는 [[삼차 그래프|3차 그래프]])의 자기동형군으로 표현될 수 있다.<ref>[[R. Frucht]]. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949.</ref> 군론과의 또 다른 연결은, 그룹이 주어지면 [[케일리 그래프]]로 알려진 대칭 그래프가 생성될 수 있으며 군의 구조와 관련된 속성이 있다는 것이다.<ref name="biggs" />

[[파일:TruncatedTetrahedron.gif|왼쪽|섬네일|220x220픽셀| [[교대군]] ''A''<sub>4</sub> 에 대한 [[케일리 그래프]]는 3차원에서 [[깎은 정사면체]]를 형성한다. 모든 케일리 그래프는 꼭짓점 전이적이지만, [[페테르센 그래프]] 등 일부 꼭짓점 전이적 그래프는 케일리 그래프가 아니다.]]
[[파일:Petersen_graph_3-coloring.svg|오른쪽|섬네일|200x200픽셀| [[페테르센 그래프]]의 색칠수인 세 가지 색을 사용한 [[그래프 색칠]]. 색칠 다항식에 따르면 3가지 색을 사용한 서로 다른 120가지 색칠이 존재한다.]]

대수 그래프 이론의 두 번째 갈래는 그래프의 대칭 성질이 스펙트럼에 반영되기 때문에 첫 번째 갈래와 관련이 있다. 특히 페테르센 그래프와 같이 고도로 대칭적인 그래프의 스펙트럼은 고유값이 많지 않다.<ref name="biggs" /> 실제로, 페테르센 그래프는 직경이 주어졌을 때 스펙트럼 고유값의 종류로 가능한 최소값인 3을 갖는다. 케일리 그래프의 경우 스펙트럼은 군의 구조, 특히 [[군 표현의 지표|기약 지표]]와 직접적인 관련이 있다.<ref name="biggs" /><ref name="babai">{{인용 | first = L | last = Babai | editor-last = Graham | editor-first = R | editor2-last = Grötschel | editor2-first = M | editor2-link = Martin Grötschel | editor3-last = Lovász | editor3-first = L | title = Handbook of Combinatorics | contribution = Automorphism groups, isomorphism, reconstruction | contribution-url = http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps | year = 1996 | publisher = Elsevier | postscript = <!--none--> | access-date = 2009-03-27 | archive-date = 2010-06-11 | archive-url = https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps | url-status = dead }}</ref>

=== 그래프 불변량 연구 ===
마지막으로 대수 그래프 이론의 세 번째 갈래는 그래프 불변량의 대수적 성질, 특히 [[그래프 색칠|색칠 다항식]], [[텃 다항식]] 및 [[매듭불변량|매듭 불변량]]에 관한 것이다. 예를 들어, 그래프의 색칠 다항식은 [[그래프 색칠]]의 개수를 계산한다. 페테르센 그래프의 경우 색칠 다항식은<math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math>이다.<ref name="biggs" /> 이를 통해 페테르센 그래프가 한 가지 또는 두 가지 색으로는 색칠될 수 없지만 세 가지 색을 사용하면 색칠 다항식에 ''t'' = 3을 대입한 값인 120가지의 서로 다른 방식으로 색칠될 수 있음을 알 수 있다. 대수적 그래프 이론의 이 영역에서는 [[4색 정리]]를 증명하려는 시도가 많은 작업에 동기를 부여하였다. 그러나, 동일한 색 다항식을 갖는 그래프의 특성화 및 어떤 다항식이 색칠 다항식인지 결정하는 것과 같은 [[그래프 색칠|미해결 문제]]가 여전히 많다.

== 같이 보기 ==
* [[스펙트럼 그래프 이론]]
* [[대수적 조합론]]
* [[대수적 연결성]]
* [[덜마지-멘델스존 분해]]
* [[그래프 속성]]
* [[인접행렬]]

== 각주 ==
{{각주}}
{{참고 자료 시작}}
*{{인용|first1=Chris|last1=Godsil|authorlink1=Chris Godsil|first2=Gordon|last2=Royle|authorlink2=Gordon Royle|title=Algebraic Graph Theory|series=Graduate Texts in Mathematics|volume=207|publisher=Springer-Verlag|location=New York|year=2001|postscript=<!--none-->}}.
{{참고 자료 끝}}

== 외부 링크 ==

* {{위키공용분류-줄}}
{{전거 통제}}

[[분류:대수적 그래프 이론]]