Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
343 views
in Technique[技术] by (71.8m points)

graph theory - Greedy algorithm by selecting vertices with least number of edges for maximum matching?

I'm learning Blossom Algorithm, but I am confused why you can't simply do this greedy approach that I thought of. Does anyone have a counterexample?

While no more vertices:
    Choose the vertex (V) with the least number of edges
    Considering vertices connected to that vertex V, choose one with the least number of edges.
    Create this edge and don't consider these two vertices anymore. 
    Reduce the count of edges on each vertex accordingly. Repeat
question from:https://stackoverflow.com/questions/65602840/greedy-algorithm-by-selecting-vertices-with-least-number-of-edges-for-maximum-ma

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)
E         G
|       /|
| A-B-C-D |
|/       |
F         H

If at the first step you choose BC, you lose, because you are left with 2 odd cycles and you cannot cover all the vertices. The optimal matching is AB CD EF GH.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...