Graphe sommet-connexe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
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[modifier | modifier le code]

  • 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 (en) 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

Référence[modifier | modifier le code]

  1. Jiří Matoušek et Jaroslav Nešetřil (en), Introduction aux mathématiques discrètes, Springer, (lire en ligne), p. 144.

Article connexe[modifier | modifier le code]

Lexique de la théorie des graphes