В теории графов , ударная вязкость является мерой связности графа. Граф G называется т -tough для данного вещественного числа т , если для любого целого числа к > 1 , G не может быть разделена на K различных компонент связности удалением меньше Tk вершин. Например, граф является 1- трудным, если количество компонентов, образованных путем удаления набора вершин, всегда не больше, чем количество удаленных вершин. Стойкость графика - это максимум tдля которых т -tough; это конечное число для всех конечных графов, кроме полных графов , которые по соглашению имеют бесконечную прочность.
Графическая стойкость была впервые представлена Вацлавом Хваталем ( 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 -вершинно-связных .
Связь с гамильтонностью [ править ]
Существует ли такое число , что любой -жильный граф является гамильтоновым?
Хватал (1973) заметил, что каждый цикл и, следовательно, каждый гамильтонов граф является 1- трудным; то есть 1- жесткость - необходимое условие гамильтоновости графа. Он предположил, что связь между стойкостью и гамильтоничностью идет в обоих направлениях: существует такой порог t , что любой t- жесткий граф является гамильтоновым. Первоначальная гипотеза Хватала о том, что t = 2 доказала бы теорему Флейшнера, была опровергнута Бауэром, Броерсма и Велдманом (2000).. Существование большего порога стойкости для гамильтоничности остается открытым и иногда называется гипотезой стойкости Хватала .
Вычислительная сложность [ править ]
Проверка того, является ли граф 1- сложным, является co-NP- полным. То есть проблема решения , на которую ответ «да» для графа, который не является 1-жестким, и «нет» для графа, который является 1-жестким, является NP-полной . То же самое верно для любого фиксированного положительного рационального числа q : проверка того, является ли граф q- трудным, является ко-NP-полным ( Bauer, Hakimi & Schmeichel, 1990 ).
См. Также [ править ]
- Сила графа , аналогичная концепция для удаления ребер
- Формула Тутте – Берже , связанная характеристика размера максимального соответствия в графике
Ссылки [ править ]
- Бауэр, Дуглас; Broersma, Hajo; Шмейхель, Эдвард (2006), «Стойкость в графах - обзор», Графики и комбинаторика , 22 (1): 1–35, DOI : 10.1007 / s00373-006-0649-0 , MR 2221006 , S2CID 3237188.
- Bauer, D .; Broersma, HJ; Велдман, HJ (2000), "Не каждый 2-жесткий граф является гамильтоновым" , Труды 5-го семинара Twente по графам и комбинаторной оптимизации (Enschede, 1997), Дискретная прикладная математика (1-3 изд.), 99 (1– 3): 317-321, DOI : 10.1016 / S0166-218X (99) 00141-9 , MR 1743840.
- Bauer, D .; Хакими, SL ; Шмейхель, Е. (1990), "Признание жестких график является NP-трудным", Дискретная прикладная математика , 28 (3): 191-195, DOI : 10.1016 / 0166-218X (90) 90001-С , МР 1074858.
- Chvátal, Вацлав (1973), "Жесткие графики и схемы Гамильтон", дискретная математика , 5 (3): 215-228, DOI : 10.1016 / 0012-365X (73) 90138-6 , МР 0316301.
