Trouver une correspondance maximale qui sature un ensemble de sommets donnés

Question

dans un graphique bipartite non ponctuel $ g= (x + y, e) $ , nous aimerions trouver une correspondance maximale, mais parmi toutes ces correspondances maximales, Nous aimerions en trouver un qui sature un sous-ensemble donné $ x_0 \ sous -éréq x $ .

Une condition nécessaire à l'existence d'une telle correspondance est que $ X_0 $ Satisfait la condition de mariage de la salle, c'est-à-dire pour chaque $ X '\ sous -éréq x_0 $ , le nombre de voisins de $ x' $ est au moins $ | X '| $ . Si cette condition est satisfaite, nous pouvons trouver une correspondance $ M $ qui sature tous les sommets de $ x_0 $ , mais $ M $ n'est pas nécessairement une correspondance maximale dans $ g $ .

.

est-il toujours possible d'étendre $ m $ dans une correspondance maximale? Alternativement, y a-t-il un moyen différent de trouver une correspondance maximale qui sature $ x_0 $ lorsque la condition nécessaire est satisfaite?

Answer 1

Après quelques recherches, j'ai découvert que ma question est une affaire particulière du problème de correspondant de priorité .Dans ce cas, il existe deux classes de priorité, $ x_0 $ et $ x_1:= v \ setminus x_0 $ .L'objectif est de trouver une correspondance qui optimise le nombre de sommets saturés dans $ x_0 $ , et sous réserve de cela, le nombre de sommets saturés dans $ x_1 $ .Il existe des algorithmes efficaces qui résolvent ce problème pour un nombre quelconque de classes prioritaires.On sait que toute correspondance prioritaire est également une correspondance maximale de cardinalité.