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

У цьому графі видалення чотирьох червоних вершин дає чотири зв'язні компоненти (зображені чотирма різними кольорами). Однак немає множини з k вершин, видалення якої залишає більше k компонент. Таким чином, жорсткість графа дорівнює 1.

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

Жорсткість увів Вацлав Хватал 1973 року; згодом поняттю було присвячено багато великих досліджень інших фахівців з теорії графів, так, огляд 2006 року, цілком присвячений жорсткості, налічує 99 теорем і 162 сторінки.

Приклади

Вилучення k вершин із графа-шляху може розбити граф на k + 1 зв'язну компоненту. Найбільше відношення числа компонент до числа видалених вершин досягається видаленням однієї вершини (всередині шляху), що призводить до розбиття шляху на дві компоненти. Таким чином, шляхи є ¹⁄₂-жорсткими. Натомість, видалення k вершин із графа-циклу залишає не більше k зв'язних компонент, а іноді залишає рівно k зв'язних компонент, так що цикл є 1-жорстким.

Зв'язок із вершинною зв'язністю

Якщо граф t-жорсткий, то отримуємо наслідок (якщо покласти k = 2), що будь-яку множину з 2t − 1 вершин можна вилучити, але граф при цьому не розпадається на дві частини. Тобто будь-який t-жорсткий граф є вершинно 2t-зв'язним.

Зв'язок із гамільтоновістю

Хватал помітив, що будь-який цикл, а тому будь-який гамільтонів граф, є 1-жорстким. Тобто 1 -жорсткість є необхідною умовою, щоб він був гамільтоновим. Хватал висловив припущення, що зв'язок між жорсткістю та гамільтоновістю діє в обох напрямках, тобто існує поріг t такий, що будь-який t-жорсткий граф є гамільтоновим. Початкова гіпотеза Хватала, що t = 2 доводила б теорему Фляйшнера, але гіпотезу спростували Бауер, Брерсма і Вельдман. Існування порога для гамільтоновості залишається відкритою проблемою.

Обчислювальна складність

Перевірка, чи є граф 1-жорстким, є co-NP-повною задачею. Тобто задача розв'язності, для якої відповідь «так» означає, що граф не 1-жорсткий, а відповідь «ні» означає, що граф 1-жорсткий, є NP-повною задачею. Те саме виконується для будь-якого фіксованого додатного раціонального числа q — перевірка, чи є граф q-жорстким, є co-NP-повною задачею.

Див. також

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

Література

• Douglas Bauer, Hajo Broersma, Edward Schmeichel. Toughness in graphs—a survey // Graphs and Combinatorics. — 2006. — Vol. 22, iss. 1. — DOI:10.1007/s00373-006-0649-0.
• D. Bauer, H. J. Broersma, H. J. Veldman. Not every 2-tough graph is Hamiltonian // Discrete Applied Mathematics. — 2000. — Vol. 99, iss. 1—3. — DOI:10.1016/S0166-218X(99)00141-9.
• D. Bauer, S. L. Hakimi, E. Schmeichel. Recognizing tough graphs is NP-hard // Discrete Applied Mathematics. — 1990. — Vol. 28, iss. 3. — DOI:10.1016/0166-218X(90)90001-S.
• Václav Chvátal. Tough graphs and Hamiltonian circuits // Discrete Mathematics. — 1973. — Vol. 5, iss. 3. — DOI:10.1016/0012-365X(73)90138-6.