잔글편집 요약 없음 |
편집 요약 없음 |
||
| 1번째 줄: | 1번째 줄: | ||
자신의 [[여그래프]]와 동형인 [[그래프 (그래프 이론)| | 자신의 [[여그래프]]와 동형인 [[그래프 (그래프 이론)|단순그래프]]를 '''자기여그래프'''(self-complementary graph)라고 한다. 꼭짓점이 1, 2, | ||
...개인 자기여그래프의 수는 다음과 같다. | ...개인 자기여그래프의 수는 다음과 같다. | ||
| 5번째 줄: | 5번째 줄: | ||
== 예시 == | == 예시 == | ||
<gallery widths=200px heights=200px> | |||
File:Paley13_no_label.svg|꼭짓점의 수가 13인 [[팰리 그래프]] | |||
File:Rado_graph.svg|[[라도 그래프]] | |||
</gallery> | |||
== 성질 == | == 성질 == | ||
* 자기여그래프의 꼭짓점의 수는 법 4에 대해 0 또는 1과 [[모듈러산술|합동]]이다. 자기여그래프의 꼭짓점의 수를 <math>n</math>이라 하면 자기여그래프의 모서리의 수는 [[완전그래프]]의 절반인 <math>\frac{n(n-1)}{4}</math>이고 이 수가 [[정수]]여야 하기 때문이다. | * 자기여그래프의 꼭짓점의 수는 법 4에 대해 0 또는 1과 [[모듈러산술|합동]]이다. 자기여그래프의 꼭짓점의 수를 <math>n</math>이라 하면 자기여그래프의 모서리의 수는 [[완전그래프]]의 절반인 <math>\frac{n(n-1)}{4}</math>이고 이 수가 [[정수]]여야 하기 때문이다. | ||
[[분류:그래프 이론]] | [[분류:그래프 이론]] | ||
2018년 2월 7일 (수) 18:38 판
자신의 여그래프와 동형인 단순그래프를 자기여그래프(self-complementary graph)라고 한다. 꼭짓점이 1, 2, ...개인 자기여그래프의 수는 다음과 같다.
- 1, 0, 0, 1, 2, 0, 0, 10, 36, 0, 0, 720, 5600, 0, 0, 703760, 11220000, 0, 0, 9168331776, 293293716992, 0, 0, 1601371799340544, 102484848265030656, 0, 0, 3837878966366932639744, 491247277315343649710080, 0, 0, ... (oeis:A000171)
예시
꼭짓점의 수가 13인 팰리 그래프
