Domanda

Supponiamo $ G $ è un grafico connesso e $ S $ è una copertura vertice. Prova che $ S $ è anche un set dominante.

Posso ottenere aiuto nel dimostrare questo? So che un set dominante in un grafico non indirizzato $ G = (v, e) $ è un sottoinsieme $ S $ sottoinsieme di $ V $ in modo tale che ogni vertice sia in $ S $ o ha un vicino in $ S $.

So che una copertura del vertice sarà sempre un set dominante perché un set di copertura del vertice è tale che ogni bordo ha un vertice nel set, il che significa che un vertice non nel set (così sull'altra estremità del bordo) Deve avere un vicino nel set affinché tutti i bordi siano coperti ...

Semplicemente non so come scrivere questo come una prova.

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top