Un problème avec l'approche gourmand pour trouver une correspondance maximale

Question

Supposons que j'ai un graphique non dirigé avec quatre sommets $ a, b, c, d $ qui sont connectés comme dans un chemin simple de $ a $ à $ d $, c'est-à-dire l'ensemble de bords $ {(a, b), (b, c), (c, d) } $. Ensuite, j'ai vu le proposé suivant comme un algorithme gourmand pour trouver une correspondance maximale ici (page 2, milieu de la page)

Maximal Matching (G, V, E):
M = []
While (no more edges can be added)
     Select an edge which does not have any vertex in common with edges in M
     M.append(e)
end while
return M

Il semble que cet algorithme dépend entièrement de l'ordre choisi pour lequel le bord est choisi en premier. Par exemple dans mon exemple si vous choisissez Edge $ (b, c) $ Tout d'abord, alors vous aurez une correspondance qui se compose uniquement de $ (b, c) $.

Alors que si vous choisissez $ (a, b) $ Comme le bord de départ, alors le bord suivant choisi sera $ (c, d) $ Et vous avez une correspondance de Cardinalité 2.

Est-ce que je manque quelque chose, car cela semble mal? J'ai également vu cela décrit comme un algorithme pour trouver une correspondance maximale dans le contexte de prouver que l'algorithme d'approximation de la couverture de sommet sélectionne une couverture de sommet en choisissant les bords en fonction d'une correspondance maximale. Toutes les idées appréciées.