Прочность графика

В теории графов прочность является мерой связности графа. Граф G называется t -жестким для заданного действительного числа t , если для каждого целого числа k > 1 граф G нельзя разбить на k различных связных компонентов путем удаления менее tk вершин. Например, граф является 1 -жестким, если число компонентов, образованных путем удаления набора вершин, всегда не больше числа удаленных вершин. Прочность графа — это максимальное t , для которого он является t -жестким; это конечное число для всех конечных графов, за исключением полных графов , которые по соглашению имеют бесконечную прочность.

Прочность графа была впервые введена Вацлавом Хваталом  (1973). С тех пор другие математики провели обширную работу по прочности; недавний обзор Бауэра, Броерсмы и Шмейхеля (2006) содержит 99 теорем и 162 статьи по этой теме.

Удаление k вершин из графа пути может разбить оставшийся граф на k + 1 связных компонентов. Максимальное отношение компонентов к удаленным вершинам достигается путем удаления одной вершины (изнутри пути) и разбиения ее на два компонента. Таким образом, пути ⁠1/2⁠ -жесткий. Напротив, удаление k вершин из графа цикла оставляет не более k оставшихся связных компонентов, а иногда оставляет ровно k связных компонентов, поэтому цикл является 1 -жестким.

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

Нерешенная задача по математике :

Существует ли число такое, что каждый -жёсткий граф является гамильтоновым?${\displaystyle т}$${\displaystyle т}$

(еще нерешенные проблемы по математике)

Chvátal (1973) заметил, что каждый цикл , и, следовательно, каждый гамильтонов граф , является 1 -жестким; то есть быть 1 -жестким является необходимым условием для того, чтобы граф был гамильтоновым. Он предположил, что связь между жесткостью и гамильтоновостью идет в обоих направлениях: что существует порог t такой, что каждый t -жесткий граф является гамильтоновым. Первоначальная гипотеза Chvátal о том, что t = 2 , доказала бы теорему Флейшнера , но была опровергнута Bauer, Broersma & Veldman (2000). Существование большего порога жесткости для гамильтоновости остается открытым и иногда называется гипотезой жесткости Chvátal .

Проверка графа на 1- жесткость является co-NP -полной. То есть, задача принятия решения , ответом на которую является «да» для графа, который не является 1-жестким, и «нет» для графа, который является 1-жестким, является NP-полной . То же самое верно для любого фиксированного положительного рационального числа q : проверка графа на q- жесткость является co-NP-полной (Bauer, Hakimi & Schmeichel 1990).

• Сила графа , аналогичная концепция для удаления ребер
• Формула Тутте–Берже , родственная характеристика размера максимального паросочетания в графе

• Бауэр, Дуглас; Броерсма, Хайо; Шмейхель, Эдвард (2006), «Прочность графов — обзор», Графы и комбинаторика , 22 (1): 1–35, doi :10.1007/s00373-006-0649-0, MR  2221006, S2CID  3237188.
• Бауэр, Д.; Броерсма, Х. Дж.; Вельдман, Х. Дж. (2000), «Не каждый 2-жесткий граф является гамильтоновым», Труды 5-го семинара в Твенте по графам и комбинаторной оптимизации (Энсхеде, 1997), Дискретная прикладная математика , 99 (1–3) (1-3-е изд.): 317–321, doi : 10.1016/S0166-218X(99)00141-9 , MR  1743840.
• Бауэр, Д.; Хакими, С.Л .; Шмейхель, Э. (1990), «Распознавание сложных графов — NP-трудная задача», Дискретная прикладная математика , 28 (3): 191–195, doi : 10.1016/0166-218X(90)90001-S , MR  1074858.
• Chvátal, Václav (1973), «Жесткие графы и гамильтоновы схемы», Discrete Mathematics , 5 (3): 215–228, doi : 10.1016/0012-365X(73)90138-6 , MR  0316301.