현 그래프

위키백과, 우리 모두의 백과사전.
(삼각분할된 그래프에서 넘어옴)
이동: 둘러보기, 검색
녹색 변은 검은색 변 5개로 구성된 회로의 현이다. 녹색 변을 지우게 되면 이 그래프는 현 그래프가 아니게 된다.

그래프 이론에서, 현 그래프(弦graph, 영어: chordal graph)는 큰 "구멍"이 나 있지 않는 그래프이다.

정의[편집]

그래프 \Gamma순환 C\subset\Gamma(弦, 영어: chord) e\in E(\Gamma)C의 두 꼭짓점 사이에 있지만, C에 포함되지 않는 \Gamma의 변이다.

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

  • \Gamma의 크기가 4 이상인 임의의 순환은 현을 갖는다.
  • \Gamma의 모든 전부분 순환은 크기가 3 이하이다.

성질[편집]

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

[편집]

모든 완전 그래프나무는 현 그래프이다. 그러나 m>1, n>1인 경우 완전 이분 그래프 K_{m,n}는 현 그래프가 아니다.

바깥 고리[편집]