마이너 (그래프 이론)

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

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

정의[편집]

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

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

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

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

[편집]

완전 그래프 K5

Complete graph K5.svg

페테르센 그래프

Petersen graph.svg

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

바깥 고리[편집]

같이 보기[편집]