minimum vs sommet minimal couvre

Question

Je suis en train d'étudier pour un examen et l'un des exemples de questions est la suivante:

couverture Vertex: une couverture de sommet dans un graphe est un ensemble de sommets de sorte que chaque bord a au moins un de ses deux extrémités dans cet ensemble.

Couverture de sommet minimale: une couverture de sommet MINIMUM dans un graphique est une couverture de sommet qui possède le plus petit nombre de sommets parmi toutes les couvertures de sommets possibles.

sommet minimal couvre une couverture de sommet MINIMAL dans un graphique est une couverture de sommet qui ne contient pas une autre couverture de sommet (suppression tout sommet de l'ensemble créerait un ensemble de sommets qui ne sont pas une couverture de sommet)

Question : Une couverture de sommet minimale n'est pas toujours une couverture de sommet minimum. Démontrer cela avec un exemple simple.

Quelqu'un peut-il se faire à ce sujet? Je ne vois pas la distinction entre les deux. Plus important encore, j'ai du mal à le visualiser.

J'espère sérieusement qu'il ne posera pas de questions bizarres comme celle-ci sur l'examen!

Answer 1

Considérons le graphe

A --- B --- C 

B est la couverture de sommet minimum.

A, C est une couverture de sommet minimale. Retirez A ou C, vous n'êtes pas à gauche avec une couverture de sommet.

Answer 2

Considérons le graphe non orienté suivant:

L'ensemble des sommets {2,4,5} est une couverture minimale de sommet du graphe. Pourquoi? parce que c'est une couverture de sommet (tous les bords sont couverts) et il n'y a pas d'autre couverture de sommet avec moins de sommets.

L'ensemble des sommets {2,3,5,6,7} est une couverture de sommet minimal. Pourquoi? parce que c'est une couverture de vertex et tout sous-ensemble non-trivial de {2,3,5,6,7} n'est pas une couverture de vertex. Essayez de retirer n'importe quel sommet de {2,3,5,6,7} et voyez que vous laissez un bord non couvert. Ce qui rend une couverture de sommet minimale est une incapacité à la réduire. Vous ne pouvez pas rendre l'ensemble plus petit qu'il ne l'est déjà et obtenir une couverture de sommet (sans insérer de sommets). De toute évidence, la couverture de sommet minimale donnée n'est pas une couverture de sommet minimale, car une couverture de sommet minimum a trois sommets et notre couverture de sommets minimale a 5 sommets. Par conséquent, toutes les couvertures de sommets minimales ne sont pas non plus une couverture de sommet minimum.

Chaque couverture de sommet minimum est également une couverture de sommet minimale car la suppression des sommets d'une couverture de sommet minimum se traduira par un ensemble de sommets d'une taille plus petite que la couverture minimale. Ainsi, tout sous-ensemble non trivial d'une couverture de sommet minimum n'est pas une couverture de sommet, et donc une couverture de sommet minimum est également minimale.