Graphe arĂȘte-connexe
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, quelles 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
- 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.
- Le 110-graphe de Iofinova-Ivanov est 3-arĂȘte-connexe.
- Un graphe 2-arĂȘte-connexe est un graphe connexe sans isthme.
Le graphe de Gray est 3-rĂ©gulier, 3-sommet-connexe et 3-arĂȘte-connexe : il est optimalement connectĂ©.
Le graphe complet K5 est 4-arĂȘte-connexe.
Le graphe biparti complet K(1,7) est 1-arĂȘte-connexe.
Voir aussi
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent sâappliquer aux fichiers multimĂ©dias.