무변 그래프

6개의 꼭짓점을 갖는 무변 그래프

{\bar{K}}_{6}

그래프 이론에서 무변 그래프(無邊graph, 영어: edgeless graph)는 꼭짓점을 가질 수 있지만, 변을 가지지 않는 그래프이다.

정의

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

$E (Γ) = \emptyset$ 이다. 즉, 변을 갖지 않는다.
$Γ$ 의 (CW 복합체로서의) 위상은 이산 공간이다.
$Γ$ 의 변 색칠수는 0이다.
$Γ$ 의 여 그래프는 완전 그래프이다.
모든 경로의 길이는 0이다.
모든 연결 성분은 하나의 꼭짓점을 갖는다.
0-정규 그래프이다.

꼭짓점이 $n$ 개인 무변 그래프는 완전 그래프 $K_{n}$ 의 여 그래프이므로, ${\bar{K}}_{n}$ 으로 표기될 수 있다.

특히, 꼭짓점이 0개인 무변 그래프 ${\bar{K}}_{0} = K_{0}$ 는 공 그래프(空graph, 영어: empty graph)라고 한다.^[1] ${\bar{K}}_{1} = K_{1}$ 은 한원소 그래프(영어: singleton graph)이다.

성질

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

완전 그래프가 무변 그래프인 경우는 $K_{0}$ 및 $K_{1}$ 밖에 없다.

분류

무변 그래프는 그 꼭짓점의 수에 따라 분류된다. 즉, 각 기수 $κ$ 에 대하여, $κ$ 개의 꼭짓점을 갖는 무변 그래프 ${\bar{K}}_{κ}$ 가 존재하며, 동형 아래 유일하다.

같이 보기

각주

↑ Diestel, Reinhard (2000). 《Graph Theory》 2판. Graduate Texts in Mahematics. New York: Springer-Verlag. ISBN 0-387-98976-5.

Harary, Frank; Read, R. (1973). 〈Is the null graph a pointless concept?〉 (영어). Bari, R. A.; Harary, Frank (편집). 《Graphs and combinatorics. Proceedings of the Capital Conference on graph theory and combinatorics at the George Washington University, June 18–22, 1973》. Lecture Notes in Mathematics 406. Springer-Verlag. doi:10.1007/BFb0066433. ISBN 978-3-540-06854-9. Zbl 0293.05101.

외부 링크

Weisstein, Eric Wolfgang. “Empty graph” (영어). 《Wolfram MathWorld》. Wolfram Research.
Weisstein, Eric Wolfgang. “Null graph” (영어). 《Wolfram MathWorld》. Wolfram Research.
Weisstein, Eric Wolfgang. “Singleton graph” (영어). 《Wolfram MathWorld》. Wolfram Research.
“Notation for a graph without any edges?” (영어). Math Overflow.

[1] Diestel, Reinhard (2000). 《Graph Theory》 2판. Graduate Texts in Mahematics. New York: Springer-Verlag. ISBN 0-387-98976-5.

[1]