엣지 커버

그래프 이론에서, 그래프의 가장자리 커버는 그래프의 모든 꼭지점이 세트의 적어도 하나의 가장자리와 충돌하는 가장자리 집합이다.컴퓨터 과학에서 최소 가장자리 커버 문제는 최소 크기의 가장자리 커버를 찾는 문제다.커버링 문제 등급에 속하며 다항 시간 내에 해결할 수 있는 최적화 문제다.

덮개/포장-문제 쌍
커버 문제 포장문제 최소 세트 커버 최대세트패킹 최소 에지 커버 최대 일치 최소 꼭지점 커버 최대 독립 집합 빈 커버 빈패킹 폴리곤 피복 직사각형 패킹
v t

정의

공식적으로 그래프 G의 가장자리 커버는 G의 각 꼭지점이 C의 적어도 하나의 가장자리와 충돌하도록 가장자리 C의 집합이다.세트 C는 G의 정점을 커버한다고 한다.다음 그림은 두 개의 그래프에서 가장자리 커버의 예를 보여준다.

최소 가장자리 커버는 가능한 최소 크기의 가장자리 커버입니다.가장자리 커버 번호 $\rho {\displaystyle (G}$) ${\displaystyle \rho(G)}$은 최소 가장자리 커버 크기입니다.다음 그림은 최소 에지 커버의 예를 보여준다.

오른쪽 그림은 엣지 커버뿐만 아니라 매칭이라는 점에 유의하십시오.특히 각 정점이 정확히 하나의 가장자리와 M에서 충돌하는 일치된 M이다.완벽한 일치(존재하는 경우)는 항상 최소 에지 커버가 된다.

예

• 모든 가장자리 세트는 도-0 정점이 없다고 가정하는 가장자리 커버다.
• 전체 초당적 그래프 K에는_m,n 최대(m, n)를 포함하는 가장자리가 있다.

알고리즘

가장 작은 가장자리 커버는 다항식 시간에 최대 일치점을 찾아 모든 꼭지점이 가려지도록 탐욕스럽게 확장함으로써 찾을 수 있다.^[1][2]다음 그림에서는 최대 일치가 빨간색으로 표시되며, 일치하지 않는 노드를 덮기 위해 추가된 추가 에지는 파란색으로 표시된다.(오른쪽 그림은 최대 일치가 완벽하게 일치하는 그래프를 보여준다. 따라서 이미 모든 정점을 커버하고 추가 에지가 필요하지 않다.)

반면에 가장 작은 꼭지점 커버를 찾는 것과 관련된 문제는 NP-하드 문제다.^[1]

참고 항목

• 꼭지점 커버
• 세트 커버 – 에지 커버 문제는 세트 커버 문제의 특별한 경우: 우주의 원소는 정점이며, 각 부분집합은 정확히 두 개의 원소를 커버한다.

메모들

참조

• Weisstein, Eric W. "Edge Cover". MathWorld.
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5.