그래프 마이너

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

정의

(단순) 그래프 $G$에서, 변 $uv\in E(G)$를 축약(영어: contraction)하여 얻는 그래프 $G/uv$는 다음과 같다.

• $V(G/uv)=V/{\sim }_{uv}$. 여기서 $\sim _{e}$는 동치류가 $\{w_{i}\}$ ($w_{i}\neq u,v$) 및 $\{u,v\}$인 동치 관계이다.
• $[w_{1}][w_{2}]\in E(G/e)\iff [w_{1}]\neq [w_{2}]\land \exists w_{1}\in [w_{1}],w_{2}\in [w_{2}]\colon w_{1}w_{2}\in E(G)$

즉, 한 변 $uv$를 없애고, $uv$의 양끝의 꼭짓점을 하나의 꼭짓점으로 합친다.

(무향) 그래프 $G$의 마이너는 $G$에 다음의 연산들을 가하여 얻을 수 있는 그래프이다.

• 변의 축약 $G\mapsto G/uv$
• 변의 삭제 $G\mapsto G-uv$
• 인접하는 변이 없는 꼭짓점의 삭제 $G\mapsto G\setminus \{v\}$

예

완전 그래프 K₅

는 페테르센 그래프

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

외부 링크

• “Minor of a graph”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Graph minor”. 《Wolfram MathWorld》 (영어). Wolfram Research. 

같이 보기

• 부분 그래프