간선을 겹치지 않게 고른다
A—B—C—D라는 경로에서 AB와 CD를 고르면 매칭이다. AB와 BC는 B를 공유하므로 동시에 선택할 수 없다. 선택 집합의 간선 개수를 매칭의 크기로 센다.
극대와 최대
가운데 간선 BC만 선택하면 다른 간선을 추가할 수 없어 극대 매칭이다. 하지만 AB와 CD를 선택하면 두 간선이 되므로 BC 하나는 최대 매칭이 아니다. 더 추가하지 못한다는 조건과 가장 많은 간선이라는 조건을 구별한다.
완전 매칭
모든 정점이 선택된 간선에 정확히 한 번 닿으면 완전 매칭이라고 한다. 유한 그래프의 완전 매칭은 정점을 둘씩 묶으므로 정점 수가 짝수여야 한다. 짝수라는 조건만으로 완전 매칭이 보장되지는 않는다.
가중치가 있는 문제
가장 많은 간선을 고르는 문제와 가중치 합이 가장 큰 매칭을 고르는 문제는 목표가 다르다. 간선 수와 비용을 함께 제한할 수도 있으므로 무엇을 최적화하는지 먼저 정한다.
관련 문서
정점 덮개 / 이분 그래프 / 가중 그래프 / 경로 그래프 / 정점 (그래프 이론) / 간선 (그래프 이론) / 짝수