Вечное доминирующее множество

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В теории графов вечное или бессмертное доминирующее множество для графа G = (V, E) — это подмножество D вершин V, такое, что D является доминирующим множеством, на котором располагается мобильная охрана первоначально (не более одного охранника может находиться в одной вершине). Множество D должно быть таким, что для любой бесконечной последовательности атак на вершины множество D может быть модифицировано путём передвижения охранника со смежной вершины на атакуемую вершину, если атакуемая вершина не была занята охранником во время атаки. Конфигурация охранников должна после каждой атаки и движения охранника образовывать доминирующее множество. Вечное доминирующее число, γ∞(G), — это минимальное число вершин во всех таких множествах D. Например, вечное доминирующее число цикла из пяти вершин равно трём.

Задача о вечном доминирующем множестве, известная также как задача о вечном доминировании, может быть представлена как комбинаторная игра[en] между двумя игроками, делающими ходы поочерёдно — защищающаяся сторона выбирает начальное доминирующее множество 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) ≤ γm∞(G) ≤ α(G) ≤ γ∞(G) ≤ θ(G),

где θ(G) означает минимальный размер кликового покрытия графа G, а γ∞(G) — вечное доминирующее число.

Верхняя граница ⌈n/2⌉ параметра γm∞(G) для графов с n вершинами была доказана в статье Чамберса, Киннерсли и Принца[13]. См. также статью Клостермейера и Минхардта[1].

В решётке m-вечное доминирующее число получило повышенное внимание, вызванное вниманием к доминирующим числам решёток (см. статью Хайнеса, Хедетмини и Слейтера[12] и статью Гонсалвеса, Пинлоу и Рао[14]). В решётках m-вечное доминирующее число первыми изучали Голдвассер, Клостермейер и Минхардт[15], где они показали, что

γm∞ = ⌈2n/3⌉ для решёток 2 на n с n ≥ 2

и

γm∞ ≤ ⌈8n/9⌉ для решёток 3 на n.

Последнее неравенство улучшили Финбоу, Мессинджер и ван Боммель[16] до

1 + ⌈4n/5⌉ ≤ γm∞ ≤ 2 + ⌈4n/5⌉

где 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], включая упомянутые выше вопросы о вариантах вечных доминирующих множеств.

Примечания[править | править код]

  1. ↑ 1 2 3 4 5 Klostermeyer, Mynhardt, 2015b.
  2. ↑ Arquilla, Frederickson, 1995.
  3. ↑ ReVelle, 1997.
  4. ↑ ReVelle, Rosing, 2000.
  5. ↑ Stewart, 1999.
  6. ↑ Burger, Cockayne, Grundlingh, 2004.
  7. ↑ 1 2 Goddard, Hedetniemi, Hedetniemi, 2005.
  8. ↑ Regan, 2007.
  9. ↑ Anderson, Barrientos, Brigham, 2007.
  10. ↑ Klostermeyer, MacGillivray, 2007.
  11. ↑ Goldwasser, Klostermeyer, 2008.
  12. ↑ 1 2 Haynes, Hedetniemi, Slater, 1998a.
  13. ↑ Chambers, Kinnersly, Prince, 2006.
  14. ↑ Goncalves, Pinlou, Rao, 2011.
  15. ↑ Goldwasser, Klostermeyer, Mynhardt, 2013.
  16. ↑ Finbow, Messinger, van Bommel, 2015.
  17. ↑ Messinger, Delaney, 2015.
  18. ↑ Beaton, Finbow, MacDonald, 2013.
  19. ↑ van Bommels, 2015.
  20. ↑ Braga, de Souza, Lee, 2015a.
  21. ↑ Braga, de Souza, Lee, 2015b.
  22. ↑ 1 2 Klostermeyer, Mynhardt, 2015a.

Литература[править | править код]

  • Wayne Goddard, Sandra M. Hedetniemi, Stephen T. Hedetniem. Eternal Security in Graphs // J. Combin. Math.. — 2005. — Т. 52. — С. 169–180..
  • M. Anderson, C. Barrientos, R. Brigham, J. Carrington, R. Vitray, J. Yellen. Maximum demand graphs for eternal security // J. Combin. Math. Combin. Comput. — 2007. — Т. 61. — С. 111–128.
  • H. Arquilla, H. Frederickson. Graphing an optimal grand strategy // Military Operations Research. — 1995. — Т. 1. — С. 3–17. — doi:10.5711/morj.1.3.3.
  • I. Beaton, S. Finbow, J. MacDonald. Eternal domniation set problem of grids // J. Combin. Math. Combin. Comput. — 2013. — Т. 85. — С. 33–38.
  • A. Braga, C. de Souza, O. Lee. The eternal domniating set problem for proper interval graphs // Information Processing Letters. — 2015a. — С. 582–587. — doi:10.1016/j.ipl.2015.02.004.
  • A. Braga, C. de Souza, O. Lee. A note on the paper "Eternal security in graphs" by Goddard, Hedetniemi, and Hedetniemi (2005). — 2015b.
  • A.P. Burger, E.J. Cockayne, W.R. Grundlingh, C.M. Mynhardt, J. van Vuuren, W. Winterbach. Infinite order domination in graphs // J. Combin. Math. Combin. Comput. — 2004. — Т. 50. — С. 179–194.
  • E. Chambers, B. Kinnersly, N. Prince. Mobile eternal security in graphs // Unpublished manuscript. — 2006. Архивировано 30 сентября 2015 года.
  • S. Finbow, M-E. Messinger, M. van Bommel. Eternal domination in 3 x n grids // Australas. J. Combin.. — 2015. — Т. 61. — С. 156–174.
  • J. Goldwasser, W. Klostermeyer. Tight bounds for eternal dominating sets in graphs // Discrete Math.. — 2008. — Т. 308. — С. 2589–2593. — doi:10.1016/j.disc.2007.06.005.
  • J. Goldwasser, W. Klostermeyer, C. Mynhardt. Eternal protection in grid graphs // Utilitas Math.. — 2013. — Т. 91. — С. 47–64.
  • D. Goncalves, A. Pinlou, M. Rao, S. Thomasse. The domination number of grids // SIAM Journal of Discrete Mathematics. — 2011. — Т. 25. — С. 1443–1453. — doi:10.1137/11082574.
  • Teresa W. Haynes, Stephen Hedetniemi, Peter Slater. Fundamentals of Domination in Graphs. — 1998a. — ISBN 0-8247-0033-3.
  • W. Klostermeyer, G. MacGillivray. Eternal security in graphs of fixed independence number // J. Combin. Math. Combin. Comput. — 2007. — Т. 63. — С. 97–101.
  • W. Klostermeyer, C. Mynhardt. Domination, Eternal Domination, and Clique Covering // Discuss. Math. Graph Theory. — 2015a. — С. 283. — doi:10.7151/dmgt.1799.
  • W. Klostermeyer, C. Mynhardt. Protecting a graph with mobile guards. — 2015b. — С. 21. — doi:10.2298/aadm151109021k. — arXiv:1407.5228.
  • M-E. Messinger, A. Delaney. Closing the gap: Eternal domination on 3 x n grids. — 2015.
  • F. Regan. Dynamic variants of domination and independence in graphs // graduate thesis, Rheinischen Friedrich-Wilhlems University, Bonn, Germany. — 2007.
  • C. ReVelle. Can you protect the Roman Empire? // Johns Hopkins Magazine. — 1997. — Т. 2.
  • C. ReVelle, K. Rosing. Defendens Imperium Romanum: A classical problem in military strategy // Amer. Math. Monthly. — 2000. — Т. 107. — С. 585–594. — doi:10.2307/2589113.
  • I. Stewart. Defend the Roman Empire! // Scientific American. — 1999. — Т. 281. — С. 136–138. — doi:10.1038/scientificamerican1299-136.
  • C. van Bommel, M. van Bommel. Eternal domination number of 5 x n grids // J. Combin. Math. Combin. Comput. — 2015.
Источник — https://ru.wikipedia.org/w/index.php?title=Вечное_доминирующее_множество&oldid=133507683