무변 그래프

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

 정의 
그래프 에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 그래프를 무변 그래프라고 한다.
 이다. 즉, 변을 갖지 않는다.
 의 (CW 복합체로서의) 위상은 이산 공간이다.
 의 변 색칠수는 0이다.
 의 여 그래프는 완전 그래프이다.
 모든 경로의 길이는 0이다.
 모든 연결 성분은 하나의 꼭짓점을 갖는다.
 0-정규 그래프이다.

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

특히, 꼭짓점이 0개인 무변 그래프 는 공 그래프(空graph, )라고 한다. 은 한원소 그래프()이다.

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

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

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

 같이 보기 
 그래프 이론 용어
 순환 그래프
 경로 그래프
 각주 



 외부 링크 





분류:그래프족
분류:무 (철학)
분류:정규 그래프