무변 그래프

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
6개의 꼭짓점을 갖는 무변 그래프

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

정의[편집]

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

꼭짓점이 개인 무변 그래프는 완전 그래프 여 그래프이므로, 으로 표기될 수 있다.

특히, 꼭짓점이 0개인 무변 그래프 공 그래프(空graph, 영어: empty graph)라고 한다. 한원소 그래프(영어: singleton graph)이다.

성질[편집]

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

완전 그래프인 무변 그래프는 밖에 없다.

분류[편집]

무변 그래프는 그 꼭짓점의 수에 따라 분류된다. 즉, 각 기수 에 대하여, 개의 꼭짓점을 갖는 무변 그래프 가 존재한다.

참고 문헌[편집]

  • 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. ISBN 978-3-540-06854-9. Zbl 0293.05101. doi:10.1007/BFb0066433. 

외부 링크[편집]