무변 그래프

1. 개요

무변 그래프는 변을 갖지 않는 그래프이다. 무변 그래프의 위상은 이산 공간이며, 변 색칠수는 0이다. 무변 그래프의 여 그래프는 완전 그래프이고, 모든 경로는 길이가 0이며, 모든 연결 성분은 하나의 꼭짓점을 갖는다. 또한 0-정규 그래프이다. 무변 그래프의 여 그래프는 완전 그래프이며, 완전 그래프가 무변 그래프인 경우는 K₀와 K₁ 뿐이다. 무변 그래프는 꼭짓점의 수에 따라 분류된다.

2. 정의

그래프 Γ에 대하여 다음 조건들을 만족시키는 그래프를 무변 그래프라고 하며, 이 조건들은 서로 동치이다.

* 꼭짓점이 $n$개인 무변 그래프는 완전 그래프 $K\_n$의 여 그래프이므로, $\backslash bar\; K\_n$으로 표기할 수 있다.
* 특히, 꼭짓점이 0개인 무변 그래프 $\backslash bar\; K\_0=K\_0$는 공 그래프(空graph, empty graph^영어)라고 한다.
* $\backslash bar\; K\_1=K\_1$은 한원소 그래프(singleton graph^영어)이다.

2.1. 동치 조건

그래프 Γ에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 그래프를 무변 그래프라고 한다.

2.2. 표기법

꼭짓점이 n개인 무변 그래프는 완전 그래프 Kₙ의 여 그래프이므로, \bar K_n으로 표기할 수 있다.

2.3. 특수 케이스

꼭짓점이 0개인 무변 그래프 $\backslash bar\; K\_0=K\_0$는 공 그래프(空graph, empty graph^영어)라고 한다. $\backslash bar\; K\_1=K\_1$은 한원소 그래프(singleton graph^영어)이다.

3. 성질

무변 그래프의 여 그래프는 (같은 수의 꼭짓점을 갖는) 완전 그래프이다.

완전 그래프가 무변 그래프인 경우는 K₀ 및 K₁ 밖에 없다.

4. 분류

무변 그래프는 그 꼭짓점의 수에 따라 분류된다. 즉, 각 기수 κ에 대하여, κ개의 꼭짓점을 갖는 무변 그래프 $\backslash bar\; K\_\backslash kappa$가 존재한다.