현 그래프
그래프 이론에서 현 그래프(弦graph, 영어: chordal graph)는 큰 "구멍"이 나 있지 않는 그래프이다.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Chordal-graph.svg/220px-Chordal-graph.svg.png)
정의
편집그래프 의 순환 의 현(弦, 영어: chord) 은 의 두 꼭짓점 사이에 있지만, 에 포함되지 않는 의 변이다.
성질
편집어떤 그래프가 현 그래프인지 여부는 다항식 시간 알고리즘으로 판별할 수 있다.
예
편집모든 완전 그래프나 나무는 현 그래프이다. 그러나 m>1, n>1인 경우 완전 이분 그래프 는 현 그래프가 아니다.
외부 링크
편집- Weisstein, Eric Wolfgang. “Chordal graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
이 글은 수학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다. |