Graphe sommet-connexe
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En théorie des graphes, un graphe connexe « est dit k-sommet-connexe s'il possède au moins k + 1 sommets et s'il reste encore connexe après en avoir ôté k – 1[1]. »
Un graphe régulier de degré k est au plus k-sommet-connexe et k-arête-connexe. S'il est effectivement k-sommet-connexe et k-arête-connexe, il est dit optimalement connecté.
Exemples
- Pour tout n, le graphe complet Kn (régulier de degré n – 1) est optimalement connecté.
- Pour tout k > 2 et tout j > 1, le graphe moulin Wd(k, j) est 1-sommet-connexe. Pour le séparer en j composantes connexes, il suffit de supprimer son sommet de plus haut degré : son centre.
- Le graphe cycle Cn est 2-sommet-connexe pour tout n > 3.
- Le 110-graphe de Iofinova-Ivanov est 3-sommet-connexe
-
Le graphe de Biggs-Smith est 3-régulier, 3-sommet-connexe et 3-arête-connexe : il est optimalement connecté. -
Le graphe moulin Wd(5,4) devient déconnecté si l'on supprime son sommet central. Il est 1-sommet-connexe. -
Le graphe complet K6 est 5-sommet-connexe.
.svg)
Référence
- Jiří Matoušek et Jaroslav Nešetřil, Introduction aux mathématiques discrètes, Springer, (lire en ligne), p. 144.
