График прочности

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

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

Примеры

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

Соединение с вершинной связностью

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

Связь с гамильтоновством

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

Есть ли номер

t

такой, что каждый

t

-жесткий график является гамильтоновым?

(еще нерешенные задачи по математике)

Хватал (1973) заметил, что каждый цикл и, следовательно, каждый граф гамильтонов $1$ -жестки; то есть $1$ -жесткость является необходимым условием того, чтобы граф был гамильтоновым. Он предположил, что связь между жесткостью и гамильтоновостью идет в обоих направлениях: существует порог $t$ такой, что каждый $t$ -жесткий граф является гамильтоновым. Первоначальная гипотеза Хватала о том, что $t = 2,$ доказала бы теорему Флейшнера , но была опровергнута Бауэром, Броерсмой и Вельдманом (2000) . Существование большего порога жесткости гамильтоновости остается открытым и иногда называется гипотезой жесткости Хватала .

Вычислительная сложность

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

См. также

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

Ссылки

Бауэр, Дуглас; Броерсма, Хаджо; Шмейхель, Эдвард (2006), «Надежность графов — обзор», Graphs and Combinatorics , 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-сложно», Discrete Applied Mathematics , 28 (3): 191–195, doi : 10.1016/0166-218X(90)90001-S , MR 1074858 .
Хватал, Вацлав (1973), «Жесткие графы и гамильтоновы схемы», Discrete Mathematics , 5 (3): 215–228, doi : 10.1016/0012-365X(73)90138-6 , MR 0316301 .