그래프 알고리즘, 근사 알고리즘

Question

임의의 그래프의 dfs 트리의 잎을 제거한 후에 왼쪽 가장자리의 수를 | S |라고 가정하면 해당 그래프의 일치가 | S |/2가 될 것이라고 증명할 수 있습니까?

Answer 1

여기에 증거가 있습니다.

정리 : T은 i 잎이있는 임의의 트리가되도록합시다. T에 일치하는 (|T|-i)/2이 있습니다.

증명 : 유도에 의한 것. T이 i 잎이있는 나무 인 경우 T에서 모든 잎을 제거 할 때 나타나는 나무가 T'이라고합시다. T'에는 j <= i 잎이 있습니다. 마찬가지로 을 T'에서 모든 잎을 제거 할 때 생기는 나무라고합시다. T''에는 k <= j 잎이 있습니다.

유도법에 의한 정리를 T''에 적용하면 (|T''|-k)/2 = (|T|-i-j-k)/2이 T''에 일치합니다. T-T'의 집합은 적어도 j 개의 가장자리를 가지며 의 각 가장자리에 하나의 인시던트 (T'의 각 리프에 하나의 인시던트를 선택 함)가 있으므로이 가장자리를 추가하여 의 T에 일치하도록 만듭니다. j >= k부터 적어도 (|T|-i)/2 가장자리입니다. QED.

나는/2를 사용하여 바닥/천장 문제를 살펴 봤지만, 당신이 포함 시키면 그 증거는 여전히 유효하다고 생각됩니다.