Question

Supposer $ G $ est un graphique connecté et $ S $ est une couverture de sommet. Prouve-le $ S $ est également un ensemble dominant.

Puis-je obtenir de l'aide pour prouver cela? Je sais qu'un ensemble dominant dans un graphique non dirigé $ G = (v, e) $ est un sous-ensemble $ S $ sous-ensemble de $ V $ tel que chaque sommet est soit dans $ S $ ou a un voisin $ S $.

Je sais qu'une couverture de sommet sera toujours un ensemble dominant car un ensemble de couvertures de sommets est tel que chaque bord a un sommet dans l'ensemble, ce qui signifie qu'un sommet pas dans l'ensemble (donc à l'autre extrémité du bord) Doit avoir un voisin dans l'ensemble pour que tous les bords soient couverts ...

Je ne sais tout simplement pas comment écrire ceci comme preuve.

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top