В теории графов прочность является мерой связности графа. Граф G называется t -жестким для заданного действительного числа t , если для каждого целого числа k > 1 граф G нельзя разбить на k различных связных компонентов путем удаления менее tk вершин. Например, граф является 1 -жестким, если число компонентов, образованных путем удаления набора вершин, всегда не больше числа удаленных вершин. Прочность графа — это максимальное t , для которого он является t -жестким; это конечное число для всех конечных графов, за исключением полных графов , которые по соглашению имеют бесконечную прочность.
Прочность графа была впервые введена Вацлавом Хваталом (1973). С тех пор другие математики провели обширную работу по прочности; недавний обзор Бауэра, Броерсмы и Шмейхеля (2006) содержит 99 теорем и 162 статьи по этой теме.
Удаление k вершин из графа пути может разбить оставшийся граф на k + 1 связных компонентов. Максимальное отношение компонентов к удаленным вершинам достигается путем удаления одной вершины (изнутри пути) и разбиения ее на два компонента. Таким образом, пути 1/2 -жесткий. Напротив, удаление k вершин из графа цикла оставляет не более k оставшихся связных компонентов, а иногда оставляет ровно k связных компонентов, поэтому цикл является 1 -жестким.
Если граф является t -жестким, то одно следствие (полученное путем установки k = 2 ) состоит в том, что любой набор из 2 t − 1 узлов может быть удален без разделения графа на две части. То есть, каждый t -жесткий граф также является 2 t -вершинно-связным .
Chvátal (1973) заметил, что каждый цикл , и, следовательно, каждый гамильтонов граф , является 1 -жестким; то есть быть 1 -жестким является необходимым условием для того, чтобы граф был гамильтоновым. Он предположил, что связь между жесткостью и гамильтоновостью идет в обоих направлениях: что существует порог t такой, что каждый t -жесткий граф является гамильтоновым. Первоначальная гипотеза Chvátal о том, что t = 2 , доказала бы теорему Флейшнера , но была опровергнута Bauer, Broersma & Veldman (2000). Существование большего порога жесткости для гамильтоновости остается открытым и иногда называется гипотезой жесткости Chvátal .
Проверка графа на 1- жесткость является co-NP -полной. То есть, задача принятия решения , ответом на которую является «да» для графа, который не является 1-жестким, и «нет» для графа, который является 1-жестким, является NP-полной . То же самое верно для любого фиксированного положительного рационального числа q : проверка графа на q- жесткость является co-NP-полной (Bauer, Hakimi & Schmeichel 1990).
