대칭 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Petersen1 tiny.svg|섬네일|200px|[[페테르센 그래프]]는 대칭 그래프의 하나이다.]]
어떤 그래프 <math>G</math>에 대해, 변의 연결 상태를 보존하는 [[자기동형사상]] <math>f</math>가 존재할 경우, 그 사상을 그래프의 '''대칭성'''이라고 정의한다. 여기에서 연결 상태를 보존한다는 의미는, 그래프 <math>G</math>에 속하는 변 <math>(u, v)</math>, <math>(u', v')</math>에 대해, <math>f(u) = u', f(v) = v'</math>가 성립한다는 의미이다. 대칭성이 존재하는 그래프를 '''대칭 그래프'''(symmetric graph)라고 부른다.

정의를 확장해서, 어떤 그래프에 대해서 길이가 <math>k</math>인 호(arc)를 보존하지만 길이가 <math>k+1</math>인 호를 보존하지는 않는 자기동형사상이 있을 경우, 그 그래프는 <math>k</math>-arc-transitive라고 부른다. 변은 길이가 1인 호이므로, 대칭 그래프는 1-arc-transitive 그래프와 같은 의미이다.
== 같이 보기 ==
* [[대수적 그래프 이론]]

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