대칭 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

어떤 그래프 G에 대해, 변의 연결 상태를 보존하는 자기동형사상 f가 존재할 경우, 그 사상을 그래프의 대칭성이라고 정의한다. 여기에서 연결 상태를 보존한다는 의미는, 그래프 G에 속하는 변 (u, v), (u', v')에 대해, f(u) = u', f(v) = v'가 성립한다는 의미이다. 대칭성이 존재하는 그래프를 대칭 그래프(symmetric graph)라고 부른다.

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