[그래프 이론] Matching과 Vertex Cover 간단 정리

Matching

그래프 $ G = (V,E) $ 에서 Matching(매칭) 이란,
간선들의 부분집합 $ M \subseteq E $ 가 모든 간선이 서로 정점을 공유하지 않는 경우에, $ M $ 을 Matching 이라고 한다.

그래프에서 겹치지 않는 간선들의 부분집합을 고르는 것.
즉, 어떤 정점도 두 개 이상의 매칭 간선을 가질 수 없음.

예를 들어, 소개팅 시켜줄 때, 한 명이 여러명과 연결되면 안 됨. 즉, 1:1 짝을 짓는 것이 Matching

Maximal Matching : 더 이상 간선을 추가할 수 없는 매칭
Maximum Matching : 가장 많은 정점을 포함하는 매칭
Perfect Matching : 모든 정점이 매칭에 포함된 경우

그래프 $ G = (V,E) $ 에서 Vertex Cover는
그래프의 모든 간선을 최소한 하나 이상 포함하는 정점(노드)들의 집합이다.

즉, 모든 간선이 최소한 하나의 선택된 정점에 연결되도록 특정 정점들을 선택하는 것.

선택된 정점 집합 $ U $ 를 제거하면 그래프에 간선이 하나도 남지 않아야 함.
모든 간선이 Vertex Cover에 포함된 정점 중 하나와 연결되어 있어야 함.

쉽게 말해, 도로망에서 모든 길목을 감시할 수 있는 최소한의 CCTV 위치를 찾는 것이다.

Minumum Vertex Cover : 가장 적은 수의 정점으로 모든 간선을 덮는 집합