여 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
페테르센 그래프(왼쪽)와 그의 여 그래프(오른쪽)

여 그래프, 보 그래프(complement graph)는 원래 그래프에서 두 점 사이에 변이 존재하면 변을 제거하고, 변이 없었으면 변을 추가하는 방식으로 만들어지는 그래프이다.

수학적으로는, 단순 그래프 G = G(V, E)가 있을 때, V로 만들 수 있는 모든 변의 집합 K에 대해서 G(V, K - E)G의 여 그래프로 정의한다.