대칭 그래프

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

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

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