Жёсткость графа

Жёсткость графа — мера связности графа: граф G t-жёсток при некотором вещественном t, если для любого целого k > 1 нельзя разбить граф G на k различных компонент связности путём удаления менее чем tk вершин. Например, граф 1-жёсток, если число компонент, образующихся при удалении вершин, всегда не превосходит числа удалённых вершин. Жёсткость графа — это максимальное t, для которого он t-жёсток. Число является конечным числом для всех конечных графов, за исключением полных графов, которые, по соглашению, имеют бесконечную жёсткость.

В этом графе удаление четырёх красных вершин даёт четыре связные компоненты (отражены четырьмя различными цветами). Однако не существует множества из k вершин, удаление которого оставляет более k компонент. Таким образом, жёсткость графа равна в точности 1.

Жёсткость была введена Вацлавом Хваталом в 1973 году^[1]; впоследствии понятию было посвящено много обширных исследований других специалистов по теории графов, так, обзор 2006 года^[2], целиком посвящённый жёсткости, насчитывает 99 теорем и 162 страницы.

Примеры

Удаление k вершин из графа-пути может разбить граф на k + 1 связных компонент. Максимальное отношение компонент к числу удаляемых вершин достигается удалением одной вершины (внутри пути), что приводит к разбиению пути на две компоненты. Таким образом, пути являются 1⁄2-жёсткими. Для контраста удаление k вершин из графа-цикла оставляет максимум k связных компонент, а иногда оставляет ровно k связных компонент, так что цикл является 1-жёстким.

Связь с вершинной связностью

Если граф t-жёсток, то получаем следствие (если положить k = 2), что любое множество из 2t − 1 вершин может быть удалено, но граф при этом не распадается на две части. То есть любой t-жёсткий граф является вершинно 2t-связным.

Связь с гамильтоновостью

Хватал^[1] заметил, что любой цикл, а потому любой гамильтонов граф, является 1-жёстким. То есть 1-жёскость является необходимым условием, чтобы он был гамильтоновым. Хватал высказал предположение, что связь между жёсткостью и гамильтоновостью действует в обоих направлениях, то есть существует порог t, такой, что любой t-жёсткий граф является гамильтоновым. Начальная гипотеза Хватала, что t = 2 доказывала бы теорему Фляйшнера, но гипотезу опровергли Бауэр, Брёрсма и Вельдман^[3]. Существование порога для гамильтоновости остаётся открытой проблемой.

Вычислительная сложность

Проверка, является ли граф 1-жёстким, есть co-NP-полная задача. То есть задача разрешимости, для которой ответ «да» означает, что граф не 1-жёсток, а ответ «нет» означает, что граф 1-жёсток, является NP-полной задачей. То же самое верно для любого фиксированного положительного рационального числа q — проверка, является ли граф q-жёстким, есть co-NP-полная задача^[4].

См. также

• Формула Татта — Бержа — связанная характеристика размера максимального паросочетания в графе.