Жорсткість графа
Жорсткість графа — міра зв'язності графа: граф G t-жорсткий за деякого дійсного 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].
- Формула Татта — Бержа — пов'язана характеристика розміру найбільшого парування в графі.
- ↑ а б Chvátal, 1973, с. 215–228.
- ↑ Bauer, Broersma, Schmeichel, 2006, с. 1–35.
- ↑ Bauer, Broersma, Veldman, 2000, с. 317–321.
- ↑ Bauer, Hakimi, Schmeichel, 1990, с. 191–195.
- Douglas Bauer, Hajo Broersma, Edward Schmeichel. Toughness in graphs—a survey // Graphs and Combinatorics. — 2006. — Vol. 22, iss. 1. — DOI:.
- 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:.
- D. Bauer, S. L. Hakimi, E. Schmeichel. Recognizing tough graphs is NP-hard // Discrete Applied Mathematics. — 1990. — Vol. 28, iss. 3. — DOI:.
- Václav Chvátal. Tough graphs and Hamiltonian circuits // Discrete Mathematics. — 1973. — Vol. 5, iss. 3. — DOI:.