여 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Complement_graph_sample.png|섬네일|[[페테르센 그래프]](左)와 그 여 그래프(右)]]
[[그래프 이론]]에서 '''여 그래프'''(餘graph, {{llang|en|complement graph}})는 임의의 [[그래프]]에서 두 점이상의 경우 이들 사이에 변이 존재하면 변을 제거하고, 변이 없었으면 변이 추가되는 [[일대일 대응]]하는 그래프이다.

== 정의 ==
[[그래프]] <math>G</math>의 '''여 그래프''' <math>\bar G</math>는 다음과 같다.
* <math>V(G)=V(\bar G)</math>
* <math>uv\in E(\bar G)\iff uv\not\in E(G)</math>

== 성질 ==
여 그래프의 여 그래프는 원래 그래프이다.
:<math>G\cong\bar{\bar G}</math>
그래프의 [[독립집합]]은 여 그래프의 [[클릭 (그래프 이론)|클릭]]에 대응한다.

스스로의 여 그래프와 동형인 그래프를 '''자기 여 그래프'''({{llang|en|self-complementary graph}})라고 한다. <math>n</math>개의 꼭짓점을 갖는 자기 여 그래프의 수는 다음과 같다 (<math>n=1,2,\dots</math>).
:1, 0, 0, 1, 2, 0, 0, 10, 36, 0, 0, 720, … {{OEIS|A000171}}
예를 들어, 다음과 같은 그래프들이 자기 여 그래프이다.
* 자명 그래프 <math>K_1</math>
* [[경로 그래프]] <math>P_4</math>
* [[순환 그래프]] <math>C_5</math>
* [[라도 그래프]]
가능한 변의 수 <math>n(n-1)/2</math>가 짝수여야 하므로, 유한 자기 여 그래프의 꼭짓점의 수는 <math>n\equiv0,1\pmod4</math>이다.

== 외부 링크 ==
* {{매스월드|id=GraphComplement|title=Graph complement}}

{{전거 통제}}

[[분류:그래프 이론]]