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