Graphe sommet-connexe — Wikipédia
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b3/4-connected_graph.svg/220px-4-connected_graph.svg.png)
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] ».
Définitions
[modifier | modifier le code]Un graphe autre qu'un graphe complet est de degré de sommet-connexité k s'il est k-sommet-connexe sans être k+1-sommet-connexe, donc si k est la taille du plus petit sous-ensemble de sommets dont la suppression déconnecte le graphe[2]. Les graphes complets ne sont pas inclus dans cette version de la définition car ils ne peuvent pas être déconnectés en supprimant des sommets. Le graphe complet à n sommets est de degré de connexité n-1.
Une définition équivalente est qu'un graphe avec au moins deux sommets est k-sommet-connexe, pour chaque paire de ses sommets, il existe est k chaînes indépendantes reliant ces sommets ; c'est le théorème de Menger[3]. Cette définition produit la même réponse n − 1, pour la connexité du graphe complet Kn[2].
Un graphe 1-sommet-connexe est appelé un graphe connexe ; un graphe 2-sommet-connexe est appelé un graphe biconnexe. Un graphe 3-connexe est aussi appelé triconnexe.
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 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) n'est plus connexe si l'on supprime son sommet central: il est 1-sommet-connexe.
- Le graphe complet K6 est 5-sommet-connexe.
Nombre de graphes selon leur sommet-connexité
[modifier | modifier le code]Nombre de graphes simples -sommet-connexes à sommets pour de 1 à 9, avec la référence à OEIS :
\ 1 2 3 4 5 6 7 8 9 OEIS total 1 2 4 11 34 156 1044 12346 274668 A000088 1 1 1 2 6 21 112 853 11117 261080 A001349 2 0 1 1 3 10 56 468 7123 194066 A002218 3 0 0 1 1 3 17 136 2388 80890 A006290 4 0 0 0 1 1 4 25 384 14480 A086216 5 0 0 0 0 1 1 4 39 1051 A086217 6 0 0 0 0 0 1 1 5 59 7 0 0 0 0 0 0 1 1 5
Nombre de graphes simples exactement -sommet-connexes à sommets:
\ 1 2 3 4 5 6 7 8 9 OEIS 0 0 1 2 5 13 44 191 1229 13588 1 1 0 1 3 11 56 385 3994 67014 A052442 2 0 1 0 2 7 39 332 4735 113176 A052443 3 0 0 1 0 2 13 111 2004 66410 A052444 4 0 0 0 1 0 3 21 345 13429 A052445 5 0 0 0 0 1 0 3 34 992 6 0 0 0 0 0 1 0 4 54
Références
[modifier | modifier le code]- Matoušek Nešetřil, p. 144.
- Schrijver 2003.
- Diestel 2016.
Bibliographie
[modifier | modifier le code]- Jiří Matoušek et Jaroslav Nešetřil, Introduction aux mathématiques discrètes, Springer, (lire en ligne)
- Reinhard Diestel, Graph Theory, Springer-Verlag, coll. « Graduate Texts in Mathematics, Volume 173 », , 5e éd., 447 p. (ISBN 978-3-662-53621-6 et 978-3-96134-005-7, lire en ligne)
- Lutz Volkmann, Fundamente der Graphentheorie, Springer, (ISBN 3-211-82774-9, lire en ligne).
- Alexander Schrijver, Combinatorial optimization : Polyhedra and efficiency, Berlin, Springer, , 1881 (3 volumes) (ISBN 978-3-540-44389-6)
Liens externes
[modifier | modifier le code]- (en) Eric W. Weisstein, « k-Connected Graph », sur MathWorld