삼각분할된 그래프

위키백과 ― 우리 모두의 백과사전.

녹색 변은 검은색 변 5개로 구성된 회로의 현이다. 녹색 변을 지우게 되면 이 그래프는 삼각분할된 그래프가 아니게 된다.
녹색 변은 검은색 변 5개로 구성된 회로의 현이다. 녹색 변을 지우게 되면 이 그래프는 삼각분할된 그래프가 아니게 된다.

수학의 한 분야인 그래프 이론에서 삼각분할된 그래프(영어: chordal graph)란 변 4개 이상의 회로에는 반드시 (대각선 역할을 하는 변)이 있는 그래프이다. 회로의 이란, 회로 상에서 인접하지 않는 두 꼭지점을 잇는 변을 의미한다. 예를 들어 모든 완전 그래프트리는 삼각분할된 그래프이나, m>1, n>1인 경우 완전 이분 그래프 Km,n는 삼각분할된 그래프가 아니다.

어떤 그래프가 삼각분할된 그래프인지 판별하는 다항식 시간 알고리즘이 알려져 있다.

이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.
다른 언어