У цьому графі видалення чотирьох червоних вершин дає чотири зв'язні компоненти (зображені чотирма різними кольорами). Однак немає множини з k вершин, видалення якої залишає більше k компонент. Таким чином, жорсткість графа дорівнює 1.
Жорсткість графа — міра зв'язності графа: граф Gt-жорсткий за деякого дійсногоt, якщо для будь-якого цілогоk > 1 не можна розбити граф G на k різних компонент зв'язності, видаливши менше ніж tk вершин. Наприклад, граф 1-жорсткий, якщо число компонент, які утворюються при видаленні вершин, завжди не перевищує числа видалених вершин. Жорсткість графа — це найбільше t, для якого він t-жорсткий. Число є скінченним числом для всіх скінченних графів, за винятком повних графів, які, за згодою, мають нескінченну жорсткість.
Жорсткість увів Вацлав Хватал 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].
Див. також
Формула Татта — Бержа — пов'язана характеристика розміру найбільшого парування в графі.
