Graphe sommet-connexe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, un graphe k-sommet-connexe (ou graphe k-connexe) est un graphe connexe qu'il est possible de déconnecter (rendre non connexe) en supprimant k sommets et tel que ce k soit minimal. Il existe donc un ou plusieurs ensembles de k sommets dont la suppression rende le graphe non connexe, mais la suppression de k-1 sommets, quels qu'ils soient, le fait demeurer connexe. Par convention, le graphe complet à k sommets est k-1 connexe.

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 qualifié de graphe optimalement connecté.

Exemples[modifier | modifier le code]

  • Pour tout n, le graphe complet Kn est optimalement connecté. Il est (n-1)-sommet-connexe, (n-1)-arête-connexe et (n-1)-régulier.
  • Pour tout k>2 et tout l>1, le graphe moulin Wd(k,l) est 1-sommet-connexe. Pour le séparer en l 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.

Article connexe[modifier | modifier le code]