그래프 마이너

그래프 이론에서 마이너()는 어떤 그래프의 변들을 축약시켜 얻는 그래프이다.

정의 
(단순) 그래프 에서, 변 를 축약()하여 얻는 그래프 는 다음과 같다.
 . 여기서 는 동치류가  () 및 인 동치 관계이다.
 
즉, 한 변 를 없애고, 의 양끝의 꼭짓점을 하나의 꼭짓점으로 합친다.

(무향) 그래프 의 마이너는 에 다음의 연산들을 가하여 얻을 수 있는 그래프이다.
 변의 축약 
 변의 삭제 
 인접하는 변이 없는 꼭짓점의 삭제

예 
완전 그래프 K5

는 페테르센 그래프

의 마이너이다. 바깥쪽 5개의 꼭짓점과 안쪽 5개의 꼭짓점들을 잇는 5개의 변을 축약하면 된다.

외부 링크

같이 보기 
 부분 그래프

그래프 이론