В теории графов , Коп выигрыша граф является неориентированный граф , на котором преследователь (Коп) всегда может выиграть преследования-уклонения игра , в которой он преследует грабителя, игроки поочередно двигая вдоль края графа или оставаться на месте, пока коп приземляется на макушку грабителя. [1] Конечные графы-победители также называются демонтируемыми графами или конструктивными графами , потому что они могут быть разобраны, многократно удаляя доминируемую вершину (ту, чья замкнутая окрестность является подмножеством окрестности другой вершины) или построены путем многократного добавления такой вершины. Графы Cop-Win можно распознать за полиномиальное время.с помощью жадного алгоритма , который строит порядок демонтажа. К ним относятся хордовые графы и графы, содержащие универсальную вершину .
Определения
Преследование-уклонение
Графы выигрыша-копа (и дополнительный класс графов, графы-победителя) были введены Новаковски и Винклером (1983) в контексте следующей игры преследования-уклонения, изобретение которой они приписывают Г. Габору и А. Квиллиоту. Два игрока, полицейский и грабитель, находятся в разных начальных вершинах данного графа. Играют по очереди; в свой ход каждый игрок может либо переместиться в соседнюю вершину, либо остаться на месте. Игра заканчивается, и коп выигрывает, если полицейский может закончить свой ход в той же вершине, что и грабитель. Грабитель побеждает, бесконечно уклоняясь от полицейского. Граф выигрыш-полицейский - это граф, обладающий тем свойством, что, независимо от того, где двое игроков начинают, полицейский всегда может добиться победы. [2]
Разборка
Замкнутая окрестность N [ v ] из вершины V в данной графе есть множество вершин , состоящие из V самих и всех других вершин , смежных с V . Говорят, что в вершине v преобладает другая вершина w, если N [ v ] ⊂ N [ w ] . То есть v и w смежны, и каждый другой сосед v также является соседом w . [3] Новаковски и Винклер (1983) называют вершину, в которой доминирует другая вершина, неприводимой вершиной . [2]
Демонтажа порядок или доминирование устранение упорядочения данного графика является упорядочение вершин таких , что, если вершины удаляются один за другим в этом порядке, каждая вершина (кроме последней) доминирует. Граф является разборным тогда и только тогда, когда он имеет приказ на демонтаж. [2] [3]
Свойства закрытия
а | б | c | d | е | ж | грамм | час | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
а | б | c | d | е | ж | грамм | час |
Семейство графов Cop-Win замкнуто относительно сильных произведений графов . Полицейский может выиграть в сильном продукте графов выигрыш копов, играя, чтобы выиграть один из факторов продукта, и после этого играя в оставшиеся факторы таким же образом, продолжая оставаться в той же вершине, что и грабитель в уже выигранный фактор. [2] Например, граф короля , сильное произведение двух графов путей , беспроигрышен. Стратегия фактора для белого короля состоит в том, чтобы сначала переместиться в тот же ряд, что и черный король, а затем двигаться к черному королю, оставаясь в том же ряду, что и черный король. [4]
Неверно, что каждый индуцированный подграф графа с выигрышем по копам является беспроигрышным. Однако некоторые специальные индуцированные подграфы остаются беспроигрышными. Новаковски и Винклер (1983) определяют ретракцию графа G на один из его индуцированных подграфов H как отображение вершин графа G в вершины графа H, которое отображает каждую вершину графа H в себя, и которое отображает каждые две соседние вершины из G либо к одной и той же вершины , как друг к другу или к паре смежных вершин в H . Затем, как они утверждают, семейство графов Cop-Win замыкается при ретракции. Ибо, полицейский может выиграть в H , имитируя игру в G . Всякий раз , когда выигрышная стратегия в G призовет к полицейскому оставаться на месте, или следовать за край, конечные точки отображаются в одной и той же вершины Н , КС остается помещенным в H . И во всех других случаях, КС следует за край в H , который является образом при втягивании выигрышных краев в G . [2]
Эквивалентность выигрыша и разборности
Каждый демонтируемый граф беспроигрышен. Выигрышная стратегия для полицейского - найти доминируемую вершину v и следовать (по индукции) оптимальной стратегии на графе, образованном удалением v , делая вид, что грабитель находится в вершине, которая доминирует над v, когда он на самом деле находится на v . Это приведет либо к фактической победе в игре, либо к позиции, в которой грабитель находится на v, а полицейский - на доминирующей вершине, из чего полицейский может выиграть еще одним ходом. [2] Эта стратегия может быть использована в качестве основы для доказательства путем индукции того факта, что в графе с n вершинами полицейский может добиться победы не более чем за n - 4 хода. [5] [6]
И наоборот, каждый граф выигрыша-копа имеет доминируемую вершину. Ибо, если грабитель играет оптимально, чтобы игра длилась как можно дольше, и последняя позиция в игре перед победой полицейского имеет полицейского в вершине c и грабителя в вершине r , тогда в r должен доминировать c , иначе грабитель мог продлить игру хотя бы на один ход. Функция, которая отображает r на c и оставляет все остальные вершины на месте, является ретракцией, поэтому граф, образованный удалением доминируемой вершины, должен оставаться копирующим. По индукции отсюда следует, что любой граф co-win демонтируем. [2] Тот же аргумент показывает, что в графе без доминируемых вершин грабитель никогда не может проиграть: всегда есть ход в вершину, не смежную с копом. В произвольном графе, который не является полноправным, грабитель может выиграть, удалив все доминируемые вершины и играя в оставшемся подграфе, который должен быть непустым, иначе граф будет разобран.
Алгоритмы распознавания и семейство всех заказов на демонтаж
Порядок разборки можно найти с помощью простого жадного алгоритма, который многократно находит и удаляет любую доминируемую вершину. Процесс успешен тогда и только тогда, когда граф является беспроигрышным, поэтому, помимо предоставления алгоритма для поиска распоряжений на демонтаж, этот метод предоставляет алгоритм для проверки того, является ли данный граф беспроигрышным. Один из способов найти каждую последующую вершину для удаления - выполнить следующие шаги:
- Найдите все треугольники на графике и подсчитайте количество треугольников, в которых участвует каждое ребро.
- Неоднократно найдите вершину v, которая является конечной точкой ребра, участвующего в количестве треугольников, равном степени v минус один, удалите v и уменьшите количество треугольников на ребро каждого оставшегося ребра, образующего треугольник с v .
В графе с n вершинами, m ребрами и вырождением d этот процесс может быть выполнен за время O ( dm ) . [7]
Альтернативный и более сложный алгоритм Спинрада (2004) включает поддержание числа, называемого дефицитом для каждой смежной пары вершин ( x , y ) , которое подсчитывает количество соседей x , которые не являются соседями y . Он создает и поддерживает набор фактического дефицита (соседи x , которые не являются соседями y ) только тогда, когда дефицит невелик. Для ускорения вычислений он использует деревья решений, которые классифицируют вершины в соответствии с их смежностью с небольшими блоками из log 2 n вершин. Он выполняет следующие шаги:
- Сгруппируйте вершины в блоки, постройте дерево решений для каждого блока и классифицируйте все вершины по их наборам соседей в каждом блоке.
- Используйте эту классификацию, чтобы вычислить дефицит для всех смежных пар вершин за время O ( n / log n ) на пару.
- Повторите следующие шаги n / log n раз, пока все вершины не будут удалены:
- Постройте набор дефицита для всех соседних пар, которые имеют дефицит не более log n и которые еще не построили этот набор, используя начальный набор деревьев решений, за время O ( n / log n ) для каждой пары.
- Повторите следующие шаги, войдите n раз:
- Найдите пару ( x , y ) с построенным, но пустым дефицитным множеством.
- Удалить вершину x
- Удалите x из всех построенных наборов дефицита, которым он принадлежит.
- Постройте дерево решений для журнала n удаленных вершин и классифицируйте все вершины по их соседям в этом наборе.
- Используйте дерево решений, чтобы обновить дефициты для всех ребер за постоянное время для каждого ребра.
Время для этой процедуры составляет O ( n 2 + mn / log n ) . [8]
Связанные семейства графов
Каждый конечный хордовый граф является демонтируемым графом, и любой порядок исключения хордального графа (порядок вершин, в котором последующие соседи каждой вершины образуют клику ) является допустимым порядком разборки. Однако существуют бесконечные хордовые графы, которые не являются беспроигрышными. [9]
Каждый граф, имеющий универсальную вершину, является разобранным, поскольку в любой другой вершине преобладает универсальная вершина, и любой порядок вершин, который помещает универсальную вершину последней, является допустимым порядком разборки. И наоборот, почти все демонтируемые графы имеют универсальную вершину в том смысле, что среди всех демонтируемых графов с n вершинами доля этих графов, имеющих универсальную вершину, стремится к единице в пределе, когда n стремится к бесконечности. [10]
В наследственно копа выигрыша графики являются графы , в которых каждый изометрический подграф Коп выигрыша. Это не верно для всех графов выигрыш полицейских; например, граф колеса с пятью вершинами является выигрышным по совокупности, но содержит изометрический 4-цикл, который не является выигрышным по совокупности, поэтому этот граф колеса не является наследственно выигрышным по наследству. Графы с наследственным выигрышем - такие же, как и мостовые графы, графы, в которых каждый цикл длины четыре или более имеет ярлык, пара вершин в графе ближе, чем в цикле. [11] Граф с выигрышами по наследству является наследственно выигрышным тогда и только тогда, когда в нем нет ни 4-циклов, ни 5-циклов как индуцированных циклов. Для наследственного графа с общим выигрышем обращение любого обхода в ширину является допустимым порядком разборки, из которого следует, что любая вершина может быть выбрана в качестве последней вершины порядка разборки. [12]
Подобную игру с большим количеством полицейских можно использовать для определения числа полицейских на графике, наименьшего количества полицейских, необходимого для победы в игре. Графы полицейских-выигрышей - это в точности графики с числом полицейских, равным единице. [13]
Рекомендации
- ^ Бонато, Энтони; Новаковский, Ричард Дж (2011), Игра Полицейские и воры на графах , студенческой математической библиотеки, 61 , Providence, RI: Американского математического общества, DOI : 10,1090 / stml / 061 , ISBN 978-0-8218-5347-4, Руководство по ремонту 2830217.
- ^ Б с д е е г Новаковски, Ричард; Winkler, Питер (1983), "стремление Vertex к вершине в графе", Дискретная математика , 43 (2-3): 235-239, DOI : 10.1016 / 0012-365X (83) 90160-7 , MR 0685631.
- ^ а б Чепа, Виктор (1998), "О дистанционных сохраняющей и ликвидации господства порядков", SIAM журнал по дискретной математике , 11 (3): 414-436, DOI : 10,1137 / S0895480195291230 , MR 1628110.
- ^ Относительно того факта, что сильное произведение путей является выигрышным для полицейских, см. Nowakowski & Winkler (1983) . О том, что граф короля является сильным произведением путей, см. Беренд, Дэниел; Корах, Ефрем; Цукер, Шира (2005), «Два антикрашивания плоских и связанных графов» (PDF) , Международная конференция 2005 года по анализу алгоритмов , дискретной математике и трудностям теоретической информатики, Нэнси: Ассоциация дискретной математики и теоретической информатики, стр. 335–341, MR 2193130.
- ^ Bonato, A .; Головач, П .; Hahn, G .; Kratochvíl, J. (2009), "Время захвата графа", дискретная математика , 309 (18): 5588-5595, DOI : 10.1016 / j.disc.2008.04.004 , МР 2567962.
- ^ Gavenčiak, Томаш (2010), "Cop-выиграть графики с максимальным захватом времени", Дискретная математика , 310 (10-11): 1557-1563, DOI : 10.1016 / j.disc.2010.01.015 , MR 2601265.
- ^ Линь, Мин Чжи; Сулиньяк, Франсиско Дж .; Szwarcfiter, Jayme L. (2012), "Arboricity, ч -index, и динамические алгоритмы", Теоретическая информатика , 426/427: 75-90, Arxiv : 1005,2211 , DOI : 10.1016 / j.tcs.2011.12.006 , MR 2891574.
- ^ Спинрад, Джереми П. (2004), "Распознавание квазитриангулированных графов", Дискретная прикладная математика , 138 (1-2): 203-213, DOI : 10.1016 / S0166-218X (03) 00295-6 , MR 2057611. Spinrad дает более простой, но менее точный анализ времени O ( n 3 / log n ) . Общее время, потраченное на шаге, который удаляет x из наборов дефицита, составляет O ( m log n ) , с преобладанием других членов во временном ограничении.
- ^ Хан, Гена; Лавиолетт, Франсуа; Зауэр, Норберт; Вудро Роберт Е. (2002), "О КС выиграть графики", Дискретная математика , 258 (1-3): 27-41, DOI : 10.1016 / S0012-365X (02) 00260-1 , MR 2002070.
- ^ Бонато, Энтони; Кемкес, Грэм; Prałat, Paweł (2012), "Почти все отговорка выиграть графики содержат универсальную вершину", Дискретная математика , 312 (10): 1652-1657, DOI : 10.1016 / j.disc.2012.02.018 , MR 2901161.
- ^ Anstee, RP; Фарбер, М. (1988), «О мостовых графах и графах с выигрышем», Журнал комбинаторной теории , серия B, 44 (1): 22–28, DOI : 10.1016 / 0095-8956 (88) 90093-7 , Руководство по ремонту 0923263.
- ^ Чепа, Виктор (1997), "Мостиковые графы копа выигрыша графа: алгоритмическое доказательство", Журнал комбинаторной теории , серии B, 69 (1): 97-100, DOI : 10,1006 / jctb.1996.1726 , MR 1426753.
- ^ Aigner, M .; Фромме, М. (1984), «Игра полицейских и грабителей», Дискретная прикладная математика , 8 (1): 1–11, DOI : 10.1016 / 0166-218X (84) 90073-8 , MR 0739593
Внешние ссылки
- Демонтируемые графы , информационная система по классам графов и их включениям