Жорсткість графа міра зв язності графа граф G t жорсткий за деякого дійсного t якщо для будь якого цілого k gt 1 не можн

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

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

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

Приклади

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

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

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

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

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

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

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

Див. також

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

Примітки

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 // . — 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 // . — 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 // . — 1990. — Vol. 28, iss. 3. — DOI:10.1016/0166-218X(90)90001-S.
Václav Chvátal. Tough graphs and Hamiltonian circuits // . — 1973. — Vol. 5, iss. 3. — DOI:10.1016/0012-365X(73)90138-6.

[FOOTNOTEChvátal1973215–228-1] Chvátal, 1973, с. 215–228.

[FOOTNOTEBauer,_Broersma,_Schmeichel20061–35-2] Bauer, Broersma, Schmeichel, 2006, с. 1–35.

[FOOTNOTEBauer,_Broersma,_Veldman2000317–321-3] Bauer, Broersma, Veldman, 2000, с. 317–321.

[FOOTNOTEBauer,_Hakimi,_Schmeichel1990191–195-4] Bauer, Hakimi, Schmeichel, 1990, с. 191–195.