Вечное доминирующее множествоВ теории графов вечное или бессмертное доминирующее множество для графа G = (V, E) — это подмножество D вершин V, такое, что D является доминирующим множеством, на котором располагается мобильная охрана первоначально (не более одного охранника может находиться в одной вершине). Множество D должно быть таким, что для любой бесконечной последовательности атак на вершины множество D может быть модифицировано путём передвижения охранника со смежной вершины на атакуемую вершину, если атакуемая вершина не была занята охранником во время атаки. Конфигурация охранников должна, после каждой атаки и движения охранника, образовывать доминирующее множество. Вечное доминирующее число, γ∞(G), — это минимальное число вершин во всех таких множествах D. Например, вечное доминирующее число цикла из пяти вершин равно трём. Задача о вечном доминирующем множестве, известная также как задача о вечном доминировании, может быть представлена как комбинаторная игра[англ.] между двумя игроками, делающими ходы поочерёдно — защищающаяся сторона выбирает, начальное доминирующее множество D и посылает охранника в атакуемую вершину, если в ней не было охранника. Атакующая же сторона в свой ход выбирает, какую вершину она будет атаковать. Атакующая сторона выигрывает, если она может атаковать вершину, рядом с которой нет охранников. Другими словами, атакующая сторона выигрывает игру, если после нескольких атак она сможет атаковать незащищённую вершину. Как заметили Клостермейер и Минхардт[1], вечное доминирующее множество связано с задачей о k официантах. ИсторияМотивом для понятия послужили древние задачи военной защиты, описанные в серии статей (Арквилла, Фредриксон, РеВелле, Россинг, Стьюарт[2][3][4][5]). Задача о вечном доминировании была впервые описана в 2004 в статье Бюргера, Кокейна и Грудлингха[6]. Затем последовала публикация статьи о вечном доминировании В. Годдарда, С. М. Хедетними и С. Т. Хедетними[7], в которой был изложен вариант задачи, названный m-вечным доминированием. В этой задаче все охранники, если они хотят, могут двигаться за один ход на соседние вершины в ответ на атаку, как только один охранник передвигается на атакуемую вершину (предполагается, что на атакуемой вершине нет охранника, в противном случае охранники не передвигаются). После статьи В. Годдарда, С. М. Хедетними и С. Т. Хедетними появился ряд статей других авторов. В этой последовательности статей были предложены некоторые другие варианты задачи вечного доминирования, включая задачи вечного покрытия вершин, вечного независимого множества, вечных тотально доминирующих множеств, вечных связных доминирующих множеств и вечных доминирующих множеств в модели изгнания (в этой модели требуется, чтобы при атаке занятой охранником вершины тот должен переместиться на соседнюю свободную вершину, если такая есть). Обзорная статья с описанием многих других результатов по задачам о вечном доминировании и многих вариаций задачи можно найти у Клостермейера и Минхардта[1]. ГраницыПусть G — граф с n ≥ 1 вершинами. Вечное доминирующее число не меньше доминирующего числа γ(G) (тривиальный факт). Годдард и Хедетмини в своей статье доказали, что вечное доминирующее число не меньше числа независимости графа G и не больше минимального размера кликового покрытия графа G (минимальный размер кликового покрытия графа G равен хроматическому числу дополнения графа G). Таким образом, согласно теореме о совершенных графах, вечное доминирующее число графа G равно минимальному размеру кликового покрытия графа G для всех совершенных графов. Было показано, что вечное доминирующее число графа G равно минимальному размеру кликового покрытия графа G для некоторых других классов графов, таких как графы дуг окружности (как показал Реган[8]) и параллельно-последовательные графы (как показали Андерсон, Барриентос и Хедетними[9]). В. Годдарда, С. М. Хедетними и С. Т. Хедетними также продемонстрировали граф, у которого вечное доминирующее множество графа меньше минимального размера кликового покрытия. Клочтермейер и МакГилливрей доказали[10], что вечное доминирующее число графа с числом независимости α не превосходит α(α + 1)/2. Голдвассер и Клостермейер[11] доказали, что существует бесконечно много графов, у которых вечное доминирующее множество в точности равно α(α + 1)/2. Границы m-вечного доминантного множестваГоддард и Хедетмини доказали, что m-вечное доминирующее число, обозначаемое γm∞(G), не превосходит числа независимости графа G. Следовательно, параметры вечного доминирования хорошо укладываются в знаменитую цепочку параметров доминирования[12]:
где θ(G) означает минимальный размер кликового покрытия графа G, а γ∞(G) — вечное доминирующее число. Верхняя граница ⌈n/2⌉ параметра γm∞(G) для графов с n вершинами была доказана в статье Чамберса, Киннерсли и Принца[13]. См. также статью Клостермейера и Минхардта[1]. В решётке m-вечное доминирующее число получило повышенное внимание, вызванное вниманием к доминирующим числам решёток (см. статью Хайнеса, Хедетмини и Слейтера[12] и статью Гонсалвеса, Пинлоу и Рао[14]). В решётках m-вечное доминирующее число первыми изучали Голдвассер, Клостермейер и Минхардт[15], где они показали, что
и
Последнее неравенство улучшили Финбоу, Мессинджер и ван Боммель[16] до
где n ≥ 11. Эта граница была затем слегка улучшена для некоторых случаев в статье Мессинджера и Делани[17]. Случаи решёток 4 на n и 5 на n рассматриваются в статье Битона, Финбоу и МакДональда[18] и в статье Мартина ван Боммеля и Христофера ван Боммеля[19] соответственно. Брага, де Соуза и Ли[20] доказали, что γm∞ = α для всех корректных интервальных графов и те же авторы также доказали[21], что существует граф Кэли, для которого m-вечное доминирующее число не равно доминирующему множеству, вопреки утверждению в статье В. Годдарда, С. М. Хедетними и С. Т. Хедетними[7]. Открытые вопросыСогласно Клостермейеру и Минхардту[1], одним из главных нерешённых вопросов является следующий: Существует ли граф G, такой, что γ(G) равен вечному доминирующему числу графа G и γ(G) меньше минимального размера кликового покрытия графа G? Клостермейер и Минхардт показали [22], что любой такой граф должен содержать треугольники и максимальная степень вершин графа должна быть не меньше четырёх. Для доминирующих множеств неизвестно, верно ли для всех графов G и H неравенство (по аналогии с гипотезой Визинга) Известно, что аналогичное неравенство выполняется не для всех графов G and H в случае задачи о m-вечном доминировании, что показали Клостермейер и Минхардт[22]. Два фундаментальных открытых вопроса о вечном доминировании указаны Дугласом Вестом на сайте Eternal Domination Number. А именно, равно ли γ∞(G) минимальному размеру кликового покрытия для всех планарных графов G и ограничено ли γ∞(G) снизу числом Ловаса, известным также как тэта-функция Ловаса. Некоторое число открытых вопросов перечислено в статье Клостермейера и Минхардта[1], включая упомянутые выше вопросы о вариантах вечных доминирующих множеств. Примечания
Литература
|
Portal di Ensiklopedia Dunia
