현 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Chordal-graph.svg|섬네일|220px|녹색 변은 검은색 변 5개로 구성된 회로의 현이다. 녹색 변을 지우게 되면 이 그래프는 현 그래프가 아니게 된다.]]
[[그래프 이론]]에서 '''현 그래프'''(弦graph, {{llang|en|chordal graph}})는 큰 "구멍"이 나 있지 않는 [[그래프]]이다.

== 정의 ==
그래프 <math>\Gamma</math>의 [[순환 (그래프 이론)|순환]] <math>C\subset\Gamma</math>의 '''현'''(弦, {{llang|en|chord}}) <math>e\in E(\Gamma)</math>은 <math>C</math>의 두 꼭짓점 사이에 있지만, <math>C</math>에 포함되지 않는 <math>\Gamma</math>의 변이다.

[[그래프]] <math>\Gamma</math>에 대하여 다음 두 조건이 서로 [[동치]]이며, 이를 만족시키는 그래프를 '''현 그래프'''라고 한다.
* <math>\Gamma</math>의 크기가 4 이상인 임의의 [[순환 (그래프 이론)|순환]]은 현을 갖는다.
* <math>\Gamma</math>의 모든 [[완벽 그래프|전부분 순환]]은 크기가 3 이하이다.

== 성질 ==
어떤 그래프가 현 그래프인지 여부는 다항식 시간 [[알고리즘]]으로 판별할 수 있다.

== 예 ==
모든 [[완전 그래프]]나 [[나무 (그래프 이론)|나무]]는 현 그래프이다. 그러나 m>1, n>1인 경우 [[완전 이분 그래프]] <math>K_{m,n}</math>는 현 그래프가 아니다.

== 외부 링크 ==
* {{매스월드|id=ChordalGraph|title=Chordal graph}}

{{토막글|수학}}

[[분류:그래프족]]
[[분류:완벽 그래프]]