그래프 마이너 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''마이너'''({{llang|en|minor}})는 어떤 그래프의 변들을 축약시켜 얻는 그래프이다.

== 정의 ==
(단순) [[그래프]] <math>G</math>에서, 변 <math>uv\in E(G)</math>를 '''축약'''({{llang|en|contraction}})하여 얻는 그래프 <math>G/uv</math>는 다음과 같다.
* <math>V(G/uv)=V/{\sim}_{uv}</math>. 여기서 <math>\sim_e</math>는 [[동치류]]가 <math>\{w_i\}</math> (<math>w_i\ne u,v</math>) 및 <math>\{u,v\}</math>인 [[동치 관계]]이다.
* <math>[w_1][w_2]\in E(G/e)\iff[w_1]\ne[w_2]\land \exists w_1\in[w_1],w_2\in[w_2]\colon w_1w_2\in E(G)</math>
즉, 한 변 <math>uv</math>를 없애고, <math>uv</math>의 양끝의 꼭짓점을 하나의 꼭짓점으로 합친다.

(무향) 그래프 <math>G</math>의 '''마이너'''는 <math>G</math>에 다음의 연산들을 가하여 얻을 수 있는 그래프이다.
* 변의 축약 <math>G\mapsto G/uv</math>
* 변의 삭제 <math>G\mapsto G-uv</math>
* 인접하는 변이 없는 [[꼭짓점]]의 삭제 <math>G\mapsto G\setminus\{v\}</math>

== 예 ==
[[완전 그래프]] K<sub>5</sub>
:[[파일:Complete graph K5.svg|100px]]
는 [[페테르센 그래프]]
:[[파일:Petersen graph.svg|100px]]
의 마이너이다. 바깥쪽 5개의 꼭짓점과 안쪽 5개의 꼭짓점들을 잇는 5개의 변을 축약하면 된다.

== 외부 링크 ==
* {{eom|title=Minor of a graph}}
* {{매스월드|id=GraphMinor|title=Graph minor}}

== 같이 보기 ==
* [[부분 그래프]]

{{전거 통제}}

[[분류:그래프 이론]]