En théorie des graphes, un graphe connexe .
Définitions
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.. 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.. Cette définition produit la même réponse n − 1, pour la connexité du graphe complet Kn.
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 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.
Nombre de graphes selon leur sommet-connexité
Nombre de graphes simples -sommet-connexes à sommets pour de 1 à 9, avec la référence à OEIS :
{| class="wikitable" |- ! \ !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! OEIS |- ! scope="row" | total | 1 || 2 || 4 || 11 || 34 || 156 || 1044 || 12346 || 274668 || A000088 |- ! scope="row" | 1 | 1 || 1 || 2 || 6 || 21 || 112 || 853 || 11117 || 261080 || A001349 |- ! scope="row" | 2 | 0 || 1 || 1 || 3 || 10 || 56 || 468 || 7123 || 194066 || A002218 |- ! scope="row" | 3 | 0 || 0 || 1 || 1 || 3 || 17 || 136 || 2388 || 80890 || A006290 |- ! scope="row" | 4 | 0 || 0 || 0 || 1 || 1 || 4 || 25 || 384 || 14480 || A086216 |- ! scope="row" | 5 | 0 || 0 || 0 || 0 || 1 || 1 || 4 || 39 || 1051 || A086217 |- ! scope="row" | 6 | 0 || 0 || 0 || 0 || 0 || 1 || 1 || 5 || 59 || |- ! scope="row" | 7 | 0 || 0 || 0 || 0 || 0 || 0 || 1 || 1 || 5 ||
Nombre de graphes simples exactement -sommet-connexes à sommets:
{| class="wikitable" |- ! \ !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! OEIS |- ! scope="row" | 0 | 0 || 1 || 2 || 5 || 13 || 44 || 191 || 1229 || 13588 || |- ! scope="row" | 1 | 1 || 0 || 1 || 3 || 11 || 56 || 385 || 3994 || 67014 || A052442 |- ! scope="row" | 2 | 0 || 1 || 0 || 2 || 7 || 39 || 332 || 4735 || 113176 || A052443 |- ! scope="row" | 3 | 0 || 0 || 1 || 0 || 2 || 13 || 111 || 2004 || 66410 || A052444 |- ! scope="row" | 4 | 0 || 0 || 0 || 1 || 0 || 3 || 21 || 345 || 13429 || A052445 |- ! scope="row" | 5 | 0 || 0 || 0 || 0 || 1 || 0 || 3 || 34 || 992 || |- ! scope="row" | 6 | 0 || 0 || 0 || 0 || 0 || 1 || 0 || 4 || 54 ||
Références
Bibliographie
.
Liens externes
Article connexe Graphe arête-connexe Lexique de la théorie des graphes
Catégorie:Concept en théorie des graphes