Vertex Couverture du graphique bipartite

Question

Un couvercle de sommet est un ensemble de sommets tels que chaque bord du graphique est incident à au moins un sommet de l'ensemble. Un couvercle de sommet minimum est un couvercle de sommet avec une cardinalité minimale.

De forme de code,

Le couvercle du sommet minimum doit contenir exactement un sommet pour chaque bord dans la correspondance maximale $ M $. Alors attribuons une variable booléenne pour chaque avantage dans $ M $, dire, $ x_i = 0 $ si la $ i $-th Edge ajoute son extrémité gauche au couvercle du sommet. On peut construire toutes les dépendances sur ces variables. Par exemple, s'il existe des bords $ (u, v) in m $ et $ (u, w) notin m $, tandis que $ w $ n'est pas saturé par $ M $, nous devons définir $ x_i $ égal à 0, car il n'y a pas d'autre moyen de couvrir le bord $ (u, w) $. Tous les autres cas sont traités trivialement.

En conséquence, nous obtenons un système complet de restrictions pour l'ensemble des variables. Trouver une affectation valide arbitraire est un problème classique à 2-SAT. Nous avons donc essentiellement réduit le problème de couverture du sommet minimum à 2-SAT sans trop réfléchir.

Je ne comprends pas les variables. J'ai un bord à partir de correspondance maximale, puis je pourrais avoir les deux points de terminaison de ce bord dans le couvercle du sommet. Mais ce schéma ne permet pas cela.

C'est le graphique que j'ai (2k_2 $) Deux bords dans la correspondance maximale:

Pour le premier bord, j'ai pris le sommet gauche dans la couverture$ x_1 = 0 $ (Selon le blog du lien) pour le deuxième bord, j'ai pris le sommet droit dans la couverture $ x_2 = 1 $.

Des questions:

1. Dans quelle mesure le 2-SAT sera-t-il vrai?
2. Quelqu'un peut-il expliquer quelle sera la relation entre $ x_1 $ et $ x_2 $?