Жёсткость графа — мера связности графа: граф -жёсток при некотором вещественном , если для любого целого нельзя разбить граф на различных компонент связности путём удаления менее чем вершин. Например, граф -жёсток, если число компонент, образующихся при удалении вершин, всегда не превосходит числа удалённых вершин. Жёсткость графа — это максимальное , для которого он -жёсток. Жёсткость конечна для всех графов, кроме полных, которым по определению приписывается бесконечная жёсткость.
Жёсткость была введена Вацлавом Хваталом в 1973 году; впоследствии понятию было посвящено много обширных исследований других специалистов по теории графов, так, обзор 2006 года, целиком посвящённый жёсткости, насчитывает 99 теорем и 162 страницы.
Примеры Удаление вершин из графа-пути может разбить граф на связных компонент. Максимальное отношение компонент к числу удаляемых вершин достигается удалением одной вершины (внутри пути), что приводит к разбиению пути на две компоненты. Таким образом, пути являются -жёсткими. Для контраста удаление вершин из графа-цикла оставляет максимум связных компонент, а иногда оставляет ровно связных компонент, так что цикл является -жёстким.
Связь с вершинной связностью Если граф -жёсток, то получаем следствие (если положить k = 2), что любое множество из вершин может быть удалено, но граф при этом не распадается на две части. То есть любой -жёсткий граф является вершинно 2t-связным.
Связь с гамильтоновостью Хватал заметил, что любой цикл, а потому любой гамильтонов граф, является -жёстким. То есть -жёсткость является необходимым условием, чтобы он был гамильтоновым. Хватал высказал предположение, что связь между жёсткостью и гамильтоновостью действует в обоих направлениях, то есть существует порог , такой, что любой -жёсткий граф является гамильтоновым. Начальная гипотеза Хватала, что t = 2 доказывала бы теорему Фляйшнера, но гипотезу опровергли Бауэр, Брёрсма и Вельдман. Существование порога для гамильтоновости остаётся открытой проблемой.
Вычислительная сложность Проверка, является ли граф -жёстким, есть co-NP-полная задача. То есть задача разрешимости, для которой ответ «да» означает, что граф не 1-жёсток, а ответ «нет» означает, что граф 1-жёсток, является NP-полной задачей. То же самое верно для любого фиксированного положительного рационального числа — проверка, является ли граф -жёстким, есть co-NP-полная задача.
См. также Формула Татта — Бержа — связанная характеристика размера максимального паросочетания в графе.
Примечания
Литература
Категория:Связность графа Категория:Инварианты графов