무변 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:0-regular graph.svg|섬네일|오른쪽|6개의 꼭짓점을 갖는 무변 그래프 <math>\bar K_6</math>]]
[[그래프 이론]]에서 '''무변 그래프'''(無邊graph, {{llang|en|edgeless graph}})는 꼭짓점을 가질 수 있지만, 변을 가지지 않는 [[그래프]]이다.

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

꼭짓점이 <math>n</math>개인 무변 그래프는 [[완전 그래프]] <Math>K_n</math>의 [[여 그래프]]이므로, <math>\bar K_n</math>으로 표기될 수 있다.

특히, 꼭짓점이 0개인 무변 그래프 <math>\bar K_0=K_0</math>는 '''공 그래프'''(空graph, {{llang|en|empty graph}})라고 한다.<ref>{{서적 인용|성=Diestel|이름=Reinhard|제목=Graph Theory|판=2|총서=Graduate Texts in Mahematics|출판사=Springer-Verlag|위치=New York|날짜=2000|isbn=0-387-98976-5}}</ref> <math>\bar K_1=K_1</math>은 '''한원소 그래프'''({{llang|en|singleton graph}})이다.

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

[[완전 그래프]]가 무변 그래프인 경우는 <math>K_0</math> 및 <math>K_1</math> 밖에 없다.

== 분류 ==
무변 그래프는 그 꼭짓점의 수에 따라 분류된다. 즉, 각 [[기수 (수학)|기수]] <math>\kappa</math>에 대하여, <math>\kappa</math>개의 꼭짓점을 갖는 무변 그래프 <math>\bar K_\kappa</math>가 존재하며, 동형 아래 유일하다.

== 같이 보기 ==
* [[그래프 이론 용어]]
* [[순환 그래프]]
* [[경로 그래프]]
== 각주 ==
{{각주}}
* {{서적 인용|이름=Frank|성=Harary|성2=Read|이름2=R.|날짜=1973|장=Is the null graph a pointless concept?|제목=Graphs and combinatorics. Proceedings of the Capital Conference on graph theory and combinatorics at the George Washington University, June 18–22, 1973|출판사=Springer-Verlag|doi= 10.1007/BFb0066433|zbl=0293.05101|총서= Lecture Notes in Mathematics|권=406|editor1-last=Bari|editor1-first=R. A.|editor2-last=Harary|editor2-first=Frank |isbn= 978-3-540-06854-9 | 언어=en}}

== 외부 링크 ==
* {{매스월드|id=EmptyGraph|title=Empty graph}}
* {{매스월드|id=NullGraph|title=Null graph}}
* {{매스월드|id=SingletonGraph|title=Singleton graph}}
* {{웹 인용|url=https://mathoverflow.net/questions/36714/notation-for-a-graph-without-any-edges|제목=Notation for a graph without any edges?|출판사=Math Overflow|언어=en}}

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