graph algorithm, approximation algorithm
After removing the leaves of the dfs tree of a random graph , suppose the number of edges left is |S|, can we prove that the matching for that grap开发者_如何学Pythonh will be |S|/2?
Here's a proof.
Theorem: Let T
be any tree with i
leaves. There is a (|T|-i)/2
matching in T
.
Proof: by induction. If T
is a tree with i
leaves, let T'
be the tree that results when removing all the leaves from T
. T'
has j <= i
leaves. Similarly, let T''
be the tree that results when removing all the leaves from T'
. T''
has k <= j
leaves.
Apply the theorem by induction to T''
, so there exists a matching of size (|T''|-k)/2 = (|T|-i-j-k)/2
in T''
. The set of edges T-T'
contains at least j
edges that are not incident to any edge in T''
or to each other (pick one incident to each leaf in T'
), so add those edges to make a matching in T
of size (|T|-i+j-k)/2
. Since j >= k
, this is at least (|T|-i)/2
edges. QED.
I've glossed over the floor/ceiling issues with the /2, but I suspect the proof would still work if you included them.
精彩评论