Graphe arête-connexe

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

En théorie des graphes, un graphe k-arête-connexe est un graphe connexe qu'il est possible de déconnecter en supprimant k arêtes et tel que ce k soit minimal. Il existe donc un ou plusieurs ensembles de k arêtes dont la suppression rende le graphe déconnecté, mais la suppression de k-1 arêtes, quels qu'elles soient, le fait demeurer connexe.

Un graphe régulier de degré k est au plus k-arête-connexe et k-sommet-connexe. S'il est effectivement k-arête-connexe et k-sommet-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.
  • Le graphe biparti complet K(1,n) est 1-arête-connexe pour tout n.
  • Le graphe cycle Cn est 2-arête-connexe pour tout n>2.

Voir aussi[modifier | modifier le code]

Théorème de Robbins (en)