마이너 (그래프 이론)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

그래프 이론에서 어떤 그래프 G의 마이너(minor)란 G의 부분 그래프에서 여러 변을 축약(contraction)해서 얻을 수 있는 그래프를 뜻한다. 달리 표현하자면, 그래프 G에서 몇몇 변과 꼭지점을 지우거나 변을 축약해서 얻어진 그래프가 마이너이다. 어떤 변을 축약한다는 말은 그 변에 접한 두 꼭지점을 하나의 꼭지점으로 합치고 그 변을 지우는 것을 뜻한다.

예를 들어 K5 Complete graph K5.svg 는 다음 그래프 Petersen graph.svg 의 마이너이다. 바깥쪽 5개꼭지점과 안쪽 5개꼭지점을 잇는 5개 변을 축약하면 된다.