여 그래프

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

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

정의[편집]

그래프 G여 그래프 \bar G는 다음과 같다.

  • V(G)=V(\bar G)
  • uv\in E(\bar G)\iff uv\not\in E(G)

성질[편집]

여 그래프의 여 그래프는 원래 그래프이다.

G\cong\bar{\bar G}

그래프의 독립집합은 여 그래프의 클릭에 대응한다.

스스로의 여 그래프와 동형인 그래프를 자기 여 그래프(영어: self-complementary graph)라고 한다. n개의 꼭짓점을 갖는 자기 여 그래프의 수는 다음과 같다 (n=1,2,\dots).

1, 0, 0, 1, 2, 0, 0, 10, 36, 0, 0, 720, … (OEIS의 수열 A000171)

예를 들어, 다음과 같은 그래프들이 자기 여 그래프이다.

가능한 변의 수 n(n-1)/2가 짝수여야 하므로, 유한 자기 여 그래프의 꼭짓점의 수는 n\equiv0,1\pmod4이다.

바깥 고리[편집]