vignette|upright=1.2| Dans ce graphe, la suppression des quatre sommets rouges produit quatre composantes connexes (représentées dans quatre couleurs différentes). De plus, il n'y a pas d'ensemble de k sommets dont la suppression produit plus de k composantes. Par conséquent, la dureté est exactement égale à 1. En théorie des graphes, la dureté (« toughness » en anglais) est une mesure de la connexité d'un graphe.
Principe Un graphe est dit -dur pour un nombre réel donné si, pour tout entier , ne peut être divisé en composantes connexes par la suppression de moins de sommets. Par exemple, un graphe est 1-dur si le nombre de composantes connexes obtenues en supprimant un ensemble de sommets est toujours au moins aussi grand que le nombre de sommets supprimés. La dureté d'un graphe est le plus grand nombre maximum pour lequel il est -solide; c'est un nombre fini pour tous les graphes finis, à l'exception des graphes complets qui par convention ont une dureté infinie.
La notion de dureté du graphe a été introduite pour la première fois par Václav Chvátal en 1973.. Depuis lors, de nombreux travaux sur la dureté ont été publiés ; un article de synthèse de Bauer, Broersma & Schmeichel de 2006 répertorie 99 théorèmes et 162 articles sur le sujet.
Exemples La suppression de sommets d'un graphe chemin peut diviser le graphe restant en au plus composantes connexes. Le maximum du rapport entre le nombre de composantes et le nombre de sommets supprimés est obtenu en supprimant un sommet à l'intérieur du chemin ce qui le divise en deux composantes. Par conséquent, les chemins sont -durs. En revanche, la suppression de sommets d'un graphe cycle laisse au plus composantes connexes, et laisse parfois exactement composantes connexes, de sorte qu'un cycle est -dur.
Lien avec la connectivité des sommets Si un graphe est -dur, alors on obtient, en fixant est que tout ensemble de sommets peut être supprimé sans diviser le graphe en deux. Autrement dit, un graphe -dur est également -sommet-connexe .
Lien avec la hamiltonicité a observé que tout graphe cycle, et donc toute chaîne hamiltonienne, est -dur ; par conséquent, être -dur est une condition nécessaire pour qu'un graphe soit hamiltonien. Il a conjecturé qu'il existe un seuil tel que tout graphe -dur est hamiltonien. La conjecture originale de Chvátal avec aurait donné une démonstration du théorème de Fleischner mais a été réfutée par Bauer, Broersma & Veldman en 2000. L'existence d'un seuil de dureté plus grand pour les graphes hamiltonien est un problème ouvert.
Complexité de calcul Tester si un graphe est -dur est co-NP-complet. En d'autres termes, le problème de décision dont la réponse est "oui" pour un graphe qui n'est pas 1-solide, et "non" pour un graphe qui est 1-dur, est NP-complet. Il en est de même pour tout nombre rationnel positif fixe : tester si un graphe est -dur est co-NP-complet.
Notes et références
Annexes Bibliographie
. . . . .
Articles connexes
Force d'un graphe, un concept analogue pour les suppressions d'arêtes Formule de Tutte-Berge, une caractérisation liée à la taille d'un couplage maximal dans un graphe. Lexique de la théorie des graphes
Catégorie:Invariant de graphe