무변 그래프

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

6개의 꼭짓점을 갖는 무변 그래프 ${\displaystyle {\bar {K}}_{6}}$

정의

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

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

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

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

성질

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

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

분류

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

같이 보기

• 그래프 이론 용어
• 순환 그래프
• 경로 그래프

각주

1. Diestel, Reinhard (2000). 《Graph Theory》. Graduate Texts in Mahematics 2판. 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.