Couverture d'un graphe

On considère un graphe (non orienté), par exemple le graphe de Moser :

Un ensemble de sommet couvre le graphe si chaque arête du graphe est adjacente à au moins un des sommets. Un exemple simple est celui consistant à poser des pions sur tous les sommets :

Mais le but du jeu est d'en placer le moins possible. En enlevant un pion superflu, on conserve un ensemble couvrant :

Mais on peut faire mieux :

Le graphe de Moser peut donc être couvert par seulement 5 pions. Peut-on le couvrir avec moins de 5 pions ?

Sur ce graphe, quelle est la taille du plus petit ensemble couvrant ?

Cet ensemble de 8 sommets est couvrant :

Peut-on faire mieux ?

Quelle est la taille minimale d'un ensemble couvrant sur le graphe de Herschel ?

5 pions suffisent :

Montrer qu'on ne peut pas faire mieux.

Exercice Python

Écrire une fonction Python qui accepte en entrée un graphe et une liste de sommets du graphe, et qui renvoie un booléen disant si l'ensemble de ces sommets est couvrant.

Quelle est la taille du plus petit ensemble couvrant sur ce graphe ?