Проблема связности в некоторых задачах поиска на графах

Ржевская Екатерина Эдуардовна

Проблема связности в некоторых задачах поиска на графах

Ржевская Екатерина Эдуардовна. Проблема связности в некоторых задачах поиска на графах. Научный руководитель: Абрамовская Татьяна Викторовна. Направление математика, механика, кафедра исследования операций. В работе рассматривается задача поиска на графах с дискретным временем. На основе стандартного, смешанного и связного поисков вводится новый блочный поиск для специального класса графов, описанного в данной работе, — графов блочной структуры. Для некоторых таких графов найдены точные значения поисковых чисел указанных поисков, описаны свойства путевой декомпозиции. Количество использованных источников: 8. Ржевская, Е. Э. Проблема связности в некоторых задачах поиска на графах: бакалаврская работа / Ржевская Екатерина Эдуардовна. – СПб., 2016. – 55 с. – Библиогр.: с. 55.

Математика

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36395f1be77c40d589d2

UUID: e1540c84-0e0d-4e3d-b053-46e979ef692c

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 20

Ржевская Екатерина Эдуардовна

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 486759 bytes

Поделиться работой

Санкт-Петербургский государственный университет Прикладная математика и информатика Исследование операций и принятие решений в задачах оптимизации, управления и экономики Ржевская Екатерина Эдуардовна Проблема связности в некоторых задачах поиска на графах Бакалаврская работа Научный руководитель: к. ф.-м. н., старший преподаватель Т. В. Абрамовская Рецензент: к. ф.-м. н., доцент Н. И. Наумова Санкт-Петербург 2016

Saint Petersburg State University Applied Mathematics and Computer Science Operation Research and Decision Making in Optimisation, Control and Economics Problems Rzhevskaia Ekaterina Eduardovna Problem of connectivity in some search problems on graphs Bachelor’s Thesis Scientific Supervisor: Senior Lecturer T. V. Abramovskaia Reviewer: Associate Professor N. I. Naumova Saint Petersburg 2016

3 Содержание 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Блоки и графы блочной структуры . . . . . . . . . . . . . . 9 3. Горизонтальная склейка блоков по одной из частей границы 11 4. Поисковые числа графов, получающихся в результате склей ки двух блоков . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1. Склейка двух блоков с отождествлением угловых вер шин . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2. 15 15 Склейка двух блоков без отождествления угловых вершин . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5. Блочный граф «крест» . . . . . . . . . . . . . . . . . . . . . 20 6. Связный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . 23 7. Удаление блока . . . . . . . . . . . . . . . . . . . . . . . . . 30 8. Путевая ширина графа . . . . . . . . . . . . . . . . . . . . . 38 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Приложение А . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Приложение B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4 1. Введение В данной работе рассматривается задача поиска с дискретным време нем мобильного объекта на графе. На связном неориентированном графе 𝐺 находится невидимый объект, перемещения которого невозможно предска зать. К его поимке стремится множество игроков 𝑆, которые также могут передвигаться на 𝐺. Условия, при которых искомый объект пойман игро ками, а также некоторые другие параметры задачи, задают вид поиска. Тем не менее, в каждой задаче гарантированного поиска требуется найти минимальное количество игроков, которые ловят объект независимо от его действий — эта величина называется поисковое число графа 𝐺. В обзоре [1] Т. В. Абрамовской и Н. Н. Петрова приводится следую щая интерпретация задачи поиска на графах. Пусть в пещере, состоящей из лазов и ходов, потерялся спелеолог. У спасателей есть карта пещеры в виде графа, но перемещения исследователя непредсказуемы, а передвигать ся он может с любой скоростью. Более того, следует предположить, что он действует себе во вред и самостоятельно не может выбраться из пещеры. Таким образом, спелеолог никак не может помочь спасателям, которым нужен алгоритм действий, гарантирующий, что хоть один из команды спа сателей наткнётся на блуждающего спелеолога. П. А. Головач показал в [2], что задача о поиске спелеолога сводится к дискретной задаче поиска на графе. Часто дискретную задачу поиска удобно формулировать как задачу очищения графа. Будем говорить, что ребро очищено, если на нём гаранти рованно нет объекта, иначе ребро загрязнено. Считается, что изначально все рёбра графа загрязнены, а игроки стремятся обеспечить момент, когда все рёбра графа единовременно очищены. Далее в работе будем придержи ваться именно такой терминологии. Для описания возможных действий игроков введём следующие шаги

5 поиска: 1. поставить игрока в вершину графа; 2. игрок скользит вдоль ребра из одного из концов, где он ранее нахо дился; 3. снять игрока с вершины. Очищенное ребро 𝑒 = (𝑢, 𝑣) защищено от загрязнения в данный мо мент, если для каждой из вершин 𝑢, 𝑣 верно, что в вершине стоит игрок или все рёбра, инцидентные ей, очищены. Иными словами, ребро повторно загрязняется, если в вершинах на пути от него до загрязнённого ребра нет ни одного игрока. Можно считать, что в начальный момент на графе нет ни одного игрока, а дальше выполняется последовательность шагов поиска, которая называется стратегией поиска. Стратегию называют монотонной (monotone), если при её использовании не допускается повторное загрязне ние рёбер. Если на каждом шаге множество очищенных рёбер индуциру ет связный подграф, то такая стратегия является связной. Использование связной стратегии моделирует ситуацию, когда игрокам необходимо под держивать безопасный канал связи. Например, спасатели в пещере могут посылать сообщения друг другу и быть уверенными, что сообщение не бу дет перехвачено спелеологом. Существуют несколько видов поиска, которые различаются условия ми очищения рёбер и множеством допустимых стратегий. В стандартном поиске разрешены все шаги поиска, перечисленные выше, а чтобы очи стить ребро 𝑒 = (𝑢, 𝑣), игроку необходимо проскользить вдоль ребра 𝑒 от одного его конца к другому. Стандартный поиск был впервые поставлен в [3] Н.Н. Петровым и в [4] Т.Д. Парсонсом. Поисковое число стандартного поиска обозначается 𝑠(𝐺). Если потребовать, чтобы все стратегии в таком поиске были связными, то получим связный поиск (connected search), поис

6 ковое число которого обозначается 𝑐𝑠(𝐺). Поиск, в котором запрещён шаг 2, а ребро 𝑒 = (𝑢, 𝑣) считается очи щенным, если для в вершинах 𝑢, 𝑣 стоят игроки, называется вершинным поиском (node search), тогда 𝑛𝑠(𝐺) – поисковое число в данном случае. Вершинный поиск был поставлен в [5] Кироусисом и Пападимитриу, там же была показана связь с «игрой в камни». В смешанном поиске (mixed search), сформулированном Такахаши, Уено и Каджитани в [6], разрешены все шаги поиска, а ребро считается очищенным, если оно очищено по условиям вершинного или стандартного поисков, 𝑚𝑖𝑥𝑠(𝐺) — поисковое число смешанного поиска. В случае, когда множество очищенных вершин смешанного поиска индуцирует связный подграф на каждом шаге, говорят, что поиск связ ный смешанный (connected mixed search), а его поисковое число обознача ют 𝑐𝑚𝑖𝑥𝑠(𝐺). Для каждого поиска можно определить монотонную страте гию и поисковые числа 𝑚𝑚𝑖𝑥𝑠(𝐺), 𝑚𝑛𝑠(𝐺), 𝑚𝑐𝑚𝑖𝑥𝑠(𝐺). Нас интересуют стандратный, смешанный (mixed) и связный смешанный (connected mixed search) поиски. В следующей главе будет введён блочный поиск для спе циального класса графов, сформированного на основе примера в статье [7], среди авторов которой — Д.М. Тиликос и Н. Санторо. Для некоторых классов блочных графов будут найдены поисковые числа интересующих нас поисков и построены оптимальные стратегии. Для любого связного графа между поисковыми числами известны сле дующие соотношения, описанные в [8] Б.Йангом: 1. 𝑛𝑠(𝐺) − 1 6 𝑠(𝐺) 6 𝑛𝑠(𝐺) + 1; 2. 𝑚𝑖𝑥𝑠(𝐺) − 1 6 𝑠(𝐺) 6 𝑚𝑖𝑥𝑠(𝐺) + 1; 3. 𝑚𝑖𝑥𝑠(𝐺) − 1 6 𝑛𝑠(𝐺) 6 𝑚𝑖𝑥𝑠(𝐺) + 1; Соотношения (1)–(3) показывают связь между стандартным, вершинным

7 и смешанным поиском. 4. 𝑚𝑖𝑥𝑠(𝐺) 6 𝑐𝑚𝑖𝑥𝑠(𝐺) 6 𝑐𝑠(𝐺); 5. Если 𝐺0 — минор 𝐺, то 𝑠(𝐺) > 𝑠(𝐺0 ), 𝑛𝑠(𝐺) > 𝑛𝑠(𝐺0 ), 𝑚𝑖𝑥𝑠(𝐺) > 𝑚𝑖𝑥𝑠(𝐺0 ); 6. Если граф 𝑇 — дерево, то 𝑠(𝑇 ) = 𝑚𝑠(𝑇 ) 6 𝑐𝑠(𝑇 ) = 𝑚𝑐𝑠(𝑇 ) 6 2𝑠(𝑇 )− 2; Неравенства 4, 6 объясняют, как можно получить оценку для поискового числа связного поиска. 7. 𝑚𝑖𝑥𝑠(𝐺) − 1 6 𝑝𝑤(𝐺) 6 𝑚𝑖𝑥𝑠(𝐺); 8. 𝑠(𝐺) = 𝑚𝑠(𝐺), 𝑛𝑠(𝐺) = 𝑚𝑛𝑠(𝐺), 𝑚𝑖𝑥𝑠(𝐺) = 𝑚𝑚𝑖𝑥𝑠(𝐺); 9. 𝑠(𝐺) 6 𝑐𝑠(𝐺) 6 𝑚𝑐𝑠(𝐺); 10. 𝑚𝑖𝑥𝑠(𝐺) 6 𝑐𝑚𝑖𝑥𝑠(𝐺) 6 𝑚𝑐𝑚𝑖𝑥𝑠(𝐺). Соотношение (7) демонстрирует связь поискового числа с путевой ши риной — важным инвариантом графа, о чём более подробно рассказано в главе 8. Равенство (8) позволяет рассматривать только монотонные стра тегии для нахождения поисковых чисел стандартного, смешанного и вер шинного поисков, а пункты 9,10 показывают, что для связных поисков это неверно. Особого внимания заслуживает соотношение (5). Минором графа 𝐺 называется граф 𝐺0 , полученный из графа 𝐺 с помощью последователь ного удаления некоторых ребёр, вершин и стягивания некоторых ребёр. Теория миноров началась с цикла статей Робертсона и Сеймура. На ри сункаx 2 показаны примеры графов, которые являются или не являются минорами для исходного графа, изображённого на 1. Сам граф тоже яв ляется своим минором, как и граф, содержащий только одну вершину. В

8 главе 7 проиллюстрирован пример, в котором для нахождения интересую щих нас поисковых чисел достаточно удачно взять минор исходного графа, для которого искомые величины уже сосчитаны, а далее воспользоваться соотношением (5). Оказывается, что класс таких графов 𝐺, что 𝑠(𝐺) 6 𝑘, замкнут относительно операции взятия минора. То же самое можно ска зать про смешанный и вершинный поиски. В главе 6 доказывается, что связный поиск таким свойством не обладает. F A C D E B I Рис. 1. Граф 𝐺 F A BC F D A BC F D A C D B I I I Рис. 2. Графы 𝐺0 , 𝐺1 , 𝐺2 На рисунке 2 граф 𝐺1 — минор 𝐺, полученный удалением вершины 𝐸, удалением ребра (𝐴, 𝐹 ) и стягиванием ребра (𝐵, 𝐶), а граф 𝐺0 — минор 𝐺1 , в котором удалено ребро (𝐼, 𝐷), следовательно, 𝐺0 — минор 𝐺. Граф 𝐺2 не является минором 𝐺, так как ребро (𝐵, 𝐼) не могло появиться в миноре графа без стягивания ребра (𝐵, 𝐶).

9 2. Блоки и графы блочной структуры Рассмотрим класс графов, которые можно изобразить на плоскости как сетку размера 𝑚 × 𝑛, где пересечения строк и столбцов — вершины нашего графа. Такие графы назовем блоками размерами 𝑚 × 𝑛. В блоках 𝑚𝑛 вершин, 𝑚(𝑛 − 1) + 𝑛(𝑚 − 1) рёбер. Для блоков можно определить границу, как подграф, порожденный вершинами степени меньше 4. Грани ца каждого блока состоит из четырех частей: верхней, нижней, правой и левой. На рисунке 3 пример блока, где 𝑚 = 11, 𝑛 = 41, граница которого выделена. Рис. 3. Граф–блок Определим процедуру склейки двух блоков 𝐵1 ⊔ 𝐵2 размеров 𝑚1 × 𝑛1 , 𝑚2 × 𝑛2 так: все вершины одной из частей границ 𝐵1 отождествляются с вершинами одной из частей границ 𝐵2 , при этом кратные рёбра не по являются. Фактически, блок 𝐵1 «приклеивается» к границе 𝐵2 . Границей ⋃︀ полученного графа назовём множество Γ = Γ1 Γ2 ∖ 𝛾, где Γ1 — граница 𝐵1 , Γ2 — граница 𝐵2 , а 𝛾— множество рёбер между «склеивающимися» вер шинами границ. Понятно, что склейка блоков определяется неоднозначно, что видно на рисунке 4, а на 5 показан пример графа, не являющегося склейкой двух блоков. Процедура склейки графа 𝐵1 ⊔ 𝐵2 и блока 𝐵3 определяется практиче ски так же, как и склейка блоков, с той лишь разницей, что теперь одна из границ 𝐵3 склеивается c вершинами границы 𝐵1 ⊔ 𝐵2 , по-прежнему у одного из графов существует такая часть границы, все вершины которой отождествляются с вершинами другого графа. Этот граф будем называть

10 Блок 𝐵1 Блок 𝐵2 𝐵1 ⊔ 𝐵2 Блок 𝐵1 Блок 𝐵2 𝐵1 ⊔ 𝐵2 Рис. 4 Блок 𝐵1 Блок 𝐵2 Граф 𝐵 ′ ̸= 𝐵1 ⊔ 𝐵2 Рис. 5 результатом склейки трёх блоков. Границей полученного графа будет мно жество Γ = Γ12 ∪ Γ3 ∖ 𝛾, где Γ12 — граница 𝐵1 ⊔ 𝐵2 , Γ3 — граница 𝐵3 , а 𝛾— множество рёбер между «склеивающимися» вершинами границ. Склейка трёх блоков проиллюстрирована на рисунке 6. Аналогично определяется склейка 𝑘 блоков и граница полученного графа, которая естественным об разом делится на части. Графы, получающиеся в результате склейки, будем называть графами блочной структуры. Назовем стратегию очищения графа 𝐺 = 𝐵1 ⊔ 𝐵1 ⊔ . . . ⊔ 𝐵𝑘 блочной структуры поблочной, если на каждом шаге существует не более одного блока 𝐵𝑖 , где 𝑖 ∈ 1 : 𝑘, все рёбра которого, за исключением рёбер границы, не являются одновременно ни очищенными, ни загрязненными, 𝑏𝑠(𝐺) — ми нимальное количество игроков, для которого существует поблочная страте гия, очищающая граф 𝐺 блочной структуры. Условия очищения рёбер для

11 блочного поиска совпадают с условиями смешанного поиска. Поблочную стратегию очищения графа 𝐺 = 𝐵1 ⊔𝐵2 ⊔. . .⊔𝐵𝑚 блочной структуры назо вём поблочно-связной, если на каждом шаге множество очищенных ребер связно, а поисковое число поблочно-связного поиска — 𝑐𝑏𝑠(𝐺). Заметим, что тогда 𝑚𝑖𝑥𝑠(𝐺) 6 𝑏𝑠(𝐺) 6 𝑐𝑏𝑠(𝐺). Блок 𝐵3 𝐵1 ⊔ 𝐵2 ⊔ 𝐵3 Блок 𝐵3 𝐵1 ⊔ 𝐵2 ⊔ 𝐵3 Блок 𝐵3 𝐵1 ⊔ 𝐵2 ⊔ 𝐵3 Рис. 6 3. Горизонтальная склейка блоков по одной из частей границы Понятно, что склейка блоков определяется не единственным образом. Рассмотрим графы, которые могли получиться в результате склейки бло ков, удовлетворяющие следующим условиям на каждом шаге склейки: 1. блоки «приклеиваются» по правой или левой границе; 2. после каждого шага полученный граф 𝐵1 ⊔ . . . ⊔ 𝐵𝑘 , 𝐵𝑖 размера 𝑚𝑖 ×

12 𝐵3 𝐵1 𝐵2 𝐵4 𝐵6 𝐵5 𝐵1 ⊔ 𝐵2 ⊔ 𝐵3 ⊔ 𝐵4 ⊔ 𝐵5 ⊔ 𝐵6 Рис. 7. Пример горизонтальной склейки, удовлетворяющей условиям 1–3 𝑛𝑖 , 𝑚𝑖 6 𝑛𝑖 где 𝑖 ∈ 1 : 𝑘 покрывается блоком 𝐵 размера max 𝑚𝑖 , 𝑖∈1:𝑘 такой блок будем называть минимальным покрывающим; 3. результат склейки нельзя получить склейкой меньшего числа блоков, удовлетворяющей условичм 1–2. Для таких графов блочной структуры верно следующее утверждение: Утверждение 3.1. Пусть 𝐺 = 𝐵1 ⊔. . .⊔𝐵𝑘 , где 𝐵1 размера 𝑚1 ×𝑛1 , . . . , 𝐵𝑘 — 𝑚𝑘 × 𝑛𝑘 – граф блочной структуры, удовлетворяющим условиям 1–3, где 𝑚𝑖 6 𝑛𝑖 , 𝑖 ∈ 1 : 𝑘, тогда 𝑠(𝐺) = max 𝑚𝑖 + 1, 𝑏𝑠(𝐺) = 𝑚𝑖𝑥𝑠(𝐺) = 𝑖∈1:𝑘 max 𝑚𝑖 . 𝑖∈1:𝑘 Д о к а з а т е л ь с т в о. Известно, что 𝑠(𝐺) = 𝑚𝑠(𝐺) и если стратегия A очищает граф 𝐺 с использованием 𝑘 игроков, то для любого 𝐺0 — подграфа 𝐺 — сужение стратегии А на 𝐺0 заведомо очищает 𝐺0 . Таким образом, получаем, что 𝑠(𝐺) > 𝑠(𝐺0 ) для любого 𝐺0 — подграфа 𝐺. Для графа 𝐺 блочной структуры получаем, что если 𝐺 = 𝐵1 ⊔. . .⊔𝐵𝑘 , то 𝑠(𝐺) > max{𝑠(𝐵1 ), . . . , 𝑠(𝐵𝑘 )}. Покажем, что для некоторого блока 𝐵 размера 𝑚 × 𝑛 выполняется равенство 𝑠(𝐵) = 𝑚 + 1. Для этого рассмотрим оптимальную стратегию и первый очистившийся столбец вершин 𝑣1 , . . . , 𝑣𝑚 графа 𝐵. Все рёбра меж ду вершинами этого столбца являются очищенными. Ребро 𝑒 = (𝑣𝑖 , 𝑣𝑖+1 )

13 очищено, следовательно, либо в вершине 𝑣𝑖 стоит игрок, либо все ребра, инцидентные 𝑣𝑖 очищены. В случае выполнения второго варианта получаем, что в 𝑖–ой строке вершин блока 𝐵 есть очищенное ребро. Если эта строка не полностью очи щена, в ней есть игрок. Если же строка полностью очищена, то в каждом столбце стоит игрок, откуда получается, что 𝑠(𝐵) > 𝑛, но 𝑚 + 1 < 𝑛, иначе рассматриваемый очищенный столбец не является первым. Итак, 𝑠(𝐵) > 𝑚. Рассмотрим шаг, когда очищалось последнее загрязнённое ребро 𝑒 в столбце. Заметим, по-прежнему верно, что в любой строке стоит игрок, при этом на последнем шаге игрок скользил вдоль ребра 𝑒. Значит, в одной из строк на предпоследнем шаге стояло 2 игрока. Тогда 𝑠(𝐵) > 𝑚 + 1. Приведем пример стратегии, очищающей блок 𝐵 с использованием 𝑚 + 1 игрока. Для этого пронумеруем столбцы блока от 1 до 𝑛, а строки — от 1 до 𝑚, а вершину, находящуюся в 𝑖–ой строке и 𝑗–ом столбце, обозначим 𝑣𝑖,𝑗 . Формально опишем стратегию очищения блока слева направо. Пусть 𝑆𝑖 , где 𝑖 ∈ 1 : 𝑚 + 1 — игроки, участвующие в очищении блока. for 𝑖 = 1, . . . , 𝑚 do поставить 𝑆𝑖 в 𝑣𝑖,1 ; 𝑆𝑚+1 скользить вдоль ребра 𝑒 = (𝑣𝑖,1 , 𝑣𝑖+1,1 ); {первый столбец очищен} 𝑗 = 2; while 𝑗 6 𝑛 do 𝑆𝑚+1 поставить в вершину 𝑣1,𝑗 ; for 𝑖 = 1, . . . , 𝑚 do 𝑆𝑖 скользит вдоль ребра 𝑒 = (𝑣𝑖,𝑗−1 , 𝑣𝑖,𝑗 ); 𝑆𝑚+1 скользить вдоль ребра 𝑒 = (𝑣𝑖,𝑗 , 𝑣𝑖+1,𝑗 ); {𝑗–ый столбец очищен} 𝑗 + +;

14 Видно, что такая стратегия очищает блок 𝐵. Аналогично, для сме шанного поиска получаем 𝑚𝑖𝑥𝑠(𝐵) = 𝑚, примером будет следующая стра тегия: for 𝑖 = 1, . . . , 𝑚 do поставить 𝑆𝑖 в 𝑣𝑖,1 ; {первый столбец очищен} 𝑗 = 2; while 𝑗 6 𝑛 do for 𝑖 = 1, . . . , 𝑚 do 𝑆𝑖 скользит вдоль ребра 𝑒 = (𝑣𝑖,𝑗−1 , 𝑣𝑖,𝑗 ); {𝑗–ый столбец очищен} 𝑗 + +; Аналогичным образом определяется стратегия очищения справа на лево. Теперь покажем, как с использованием 𝑚 + 1 игрока очистить граф 𝐺 блочной структуры, где 𝑚 — высота минимального покрывающего по крытия. Рассмотрим блок, левая граница которого пересекается с левой границей графа 𝐺 (если таких блоков несколько, то очистим их поочеред но описанным способом). Заметим, что мы сможем это сделать, так как 𝑚𝑖𝑥𝑠(𝐺) = 𝑚. Когда эти блоки очищены, все игроки в последнем столбце каждого блока. Заметим, что они все стоят в одном ряду по определению графа блочной структуры. Дальше продолжается тот же процесс на бло ках, имеющих общую границу с очищенными блоками, на каждом шаге вы ставлено не более, чем 𝑚, а во время очищения блока шириной 𝑚 выставлен 𝑚 игрок, стратегия является поблочной. Следовательно, 𝑏𝑠(𝐺) = 𝑚𝑖𝑥𝑠(𝐺). Итак, утверждение доказано.

15 4. Поисковые числа графов, получающихся в результате склейки двух блоков Пусть склеиваются два блока 𝐵1 , 𝐵2 . Найдём поисковые числа для всех способов склейки и предъявим оптимальные стратегии. Выделим два класса полученных графов с точностью до поворота. 4.1. Склейка двух блоков с отождествлением угловых вершин Начнём со склейки блоков, в результате которой хотя бы одна пара угловых вершин отождествляется. Блок 𝐵1 𝐵1 ⊔ 𝐵2 Блок 𝐵2 Рис. 8 Полученный граф назовём 𝐵 и будем искать для него 𝑚𝑖𝑥𝑠(𝐵), 𝑐𝑚𝑖𝑥𝑠(𝐵), 𝑏𝑠(𝐵), 𝑐𝑏𝑠(𝐵). 𝑛 𝑙−1 𝑚 𝑘−1 Рис. 9. Граф 𝐵 Начнём исследования поисковых чисел с нахождения 𝑚𝑖𝑥𝑠(𝐺). Имеют место следующие неравенства: 𝑚𝑖𝑥𝑠(𝐵) > min{min{𝑚 + 𝑙 − 1, 𝑚 + 𝑛}, max{𝑚, 𝑛}, 𝑚 + 𝑙 − 1, 𝑛 + 𝑘 − 1}

16 𝑚𝑖𝑥𝑠(𝐵) > min{max{𝑚, 𝑛}, 𝑚 + 𝑙 − 1, 𝑛 + 𝑘 − 1} Для удобства чтения доказательства и вывод неравенств приводятся в при ложении А к данной работе. Обобщая полученные неравенства, видим окон чательную оценку 𝑚𝑖𝑥𝑠(𝐵) > min{max{𝑚, 𝑛}, 𝑚 + 𝑙 − 1, 𝑛 + 𝑘 − 1}, которую можно переписать в следующем виде 𝑚𝑖𝑥𝑠(𝐵) > min{𝑚, 𝑛 + 𝑘 − 1}, 𝑚 > 𝑛, 𝑚𝑖𝑥𝑠(𝐵) > min{𝑛, 𝑚 + 𝑙 − 1}, 𝑛 > 𝑚 Предъявим стратегии, при которых неравенство превращается в ра венство. Для этого пронумеруем столбцы блока от 1 до 𝑛, а строки — от 1 до 𝑚, а вершину, находящуюся в 𝑖–ой строке и 𝑗–ом столбце, обозначим 𝑣𝑖,𝑗 : ∙ 𝑚 > 𝑛, 𝑚 > 𝑛 + 𝑘 − 1, следовательно 𝑚𝑖𝑥𝑠(𝐵) = 𝑛 + 𝑘 − 1. Оптималь ной стратегий тогда будет являться стратегия «снизу вверх», когда все игроки ставятся на вершины самой нижней строки, а затем по очереди скользят по рёбрам вверх, последовательно очищая строки. Описанная стратегия будет ещё и блочной, если рассмотреть полу ченный граф как склейку двух блоков размеров 𝑚 × (𝑛 + 𝑘 − 1) и 𝑙 × 𝑛. ∙ 𝑚 > 𝑛, 𝑚 6 𝑛 + 𝑘 − 1, следовательно 𝑚𝑖𝑥𝑠(𝐵) = 𝑚. Оптимальной будет следующая стратегия: – очищаются столбцы высотой 𝑚 «слева направо» или «справа налево» в зависимости от положения границы графа, мы будем считать, что используется стратегия «слева направо», после чего скользят по рёбрам до столбца 𝑘; – затем все игроки, кроме игрока в вершине 𝑣𝑚,𝑘 , поочередно сколь зят по рёбрам;

17 – теперь игрок в вершине 𝑣𝑚−1,𝑘+1 тоже стоит на месте, а другие скользят по рёбрам своей строки; – продолжая таким образом, получаем игрока в вершине 𝑣1,𝑛+𝑘−1 ; – игроки поочерёдно скользят вверх по рёбрам своих столбцов и очищают граф; Такую стратегию назовём диагональной. Диагональная стратегия яв ляется поблочной для такого класса графов. ∙ 𝑛 > 𝑚, 𝑛 > 𝑚+𝑙−1, следовательно 𝑚𝑖𝑥𝑠(𝐵) = 𝑚+𝑙−1. Оптимальной стратегией будет поблочная стратегия «слева направо», когда игроки последовательно очищают столбцы, двигаясь при этом по строкам. ∙ 𝑛 > 𝑚, 𝑛 6 𝑚 + 𝑙 − 1, следовательно 𝑚𝑖𝑥𝑠(𝐵) = 𝑛. Стратегия, анало гичная случаю 𝑚 > 𝑛, 𝑚 6 𝑛 + 𝑘 − 1. Все стратегии получились связными и поблочными, так что мы нашли и 𝑐𝑚𝑖𝑥𝑠(𝐵), 𝑏𝑠(𝐵), 𝑐𝑏𝑠(𝐵) для графов 𝐵 из этого класса. Таким образом, доказано утверждение Утверждение 4.1. Для любого графа 𝐵, полученного в результате склей ки двух блоков 𝐵1 и 𝐵2 размеров 𝑚 × 𝑘 и (𝑚 + 𝑙 − 1) × 𝑛, 𝑚𝑖𝑥𝑠(𝐵) = 𝑐𝑚𝑖𝑥𝑠(𝐵) = 𝑏𝑠(𝐵) = 𝑐𝑏𝑠(𝐵) = min{𝑚, 𝑛 + 𝑘 − 1}, 𝑚 > 𝑛 и 𝑚𝑖𝑥𝑠(𝐵) = 𝑐𝑚𝑖𝑥𝑠(𝐵) = 𝑏𝑠(𝐵) = 𝑐𝑏𝑠(𝐵) = min{𝑛, 𝑚 + 𝑙 − 1}, 𝑛 > 𝑚 4.2. Склейка двух блоков без отождествления угловых вершин Теперь рассмотрим ещё один класс графов, которые могут получаться в результате склейки двух блоков. Снова начнём исследования поисковых чисел с нахождения 𝑚𝑖𝑥𝑠(𝐺). Имеют место следующее неравенство: 𝑚𝑖𝑥𝑠(𝐵) > min{max{2𝑚, 𝑛}, max{𝑚, 𝑛+𝑘−1}, 𝑛+𝑝+𝑘−2, 𝑚+𝑙−1, 𝑚+𝑛}

18 𝑛 𝑙−1 𝑚 𝑘−1 𝑝−1 Рис. 10 Подробный вывод неравенства приводится в приложении B к данной рабо те. Теперь построим стратегии для каждого возможного значения миниму ма. ∙ min{𝑛 + 𝑚, max{𝑛 + 𝑘 − 1, 𝑚}, 𝑛 + 𝑝 + 𝑘 − 2, 𝑚 + 𝑙 − 1, max{2𝑚, 𝑛}} = 𝑛+𝑚 Стратегия следующая: очистить 𝑘 − 1 подряд идущих столбцов «сле ва направо» с использованием 𝑚 игроков, затем поставить 𝑛 игроков в вершины 𝑣𝑚,𝑘 . . . 𝑣𝑚,𝑛+𝑘−1 , продолжить очищение 𝑚 игроками «сле ва направо», после чего 𝑛 игроков очищают остаток графа «снизу вверх». Стратегия получилось поблочной; ∙ min{𝑛 + 𝑚, max{𝑛 + 𝑘 − 1, 𝑚}, 𝑛 + 𝑝 + 𝑘 − 2, 𝑚 + 𝑙 − 1, max{2𝑚, 𝑛}} = 𝑛 + 𝑝 + 𝑘 − 2 — стратегия «снизу вверх», является связной и блочной; ∙ min{𝑛 + 𝑚, max{𝑛 + 𝑘 − 1, 𝑚}, 𝑛 + 𝑝 + 𝑘 − 2, 𝑚 + 𝑙 − 1, max{2𝑚, 𝑛}} = 𝑚 + 𝑙 − 1 — стратегия «справа налево». Если рассматривать граф как результат склейки двух блоков, то такая стратегия не будет по блочной, но будет таковой, если рассматривать граф, полученный в результате склейки трёх блоков размеров 𝑚×𝑘, (𝑚+𝑙−1)×𝑛, 𝑚×𝑝; ∙ min{𝑛 + 𝑚, max{𝑛 + 𝑘 − 1, 𝑚}, 𝑛 + 𝑝 + 𝑘 − 2, 𝑚 + 𝑙 − 1, max{2𝑚, 𝑛}} = max{𝑛 + 𝑘 − 1, 𝑚} В этом случае стратегия строится так:

19 – 𝑛 игроков очищают «длинные» столбцы «сверху вниз», пока не окажутся в вершинах 𝑣𝑚,𝑘 . . . 𝑣𝑚,𝑘+𝑛−1 ; – 𝑘 − 1 игроков занимают вершины 𝑣𝑚,1 . . . 𝑣𝑚,𝑘−1 – Затем игроки становятся в диагональ: игрок в вершине 𝑣𝑚,𝑘+𝑛−1 остаётся на месте, остальные скользят вниз по рёбрам своих столбцов; – Теперь игрок в вершине 𝑣𝑚−1,𝑘+𝑛−2 тоже стоит на месте, а осталь ные скользят вниз по рёбрам, то есть на каждом шаге в строке остаётся игрок, у которого справа в строке нет игроков; – Когда в каждой строке с номером, меньшим 𝑚 + 1 есть игрок, игроки последовательно скользят по рёбрам своих строк. Cтратегия оказалась поблочной. ∙ min{𝑛 + 𝑚, max{𝑛 + 𝑘 − 1, 𝑚}, 𝑛 + 𝑝 + 𝑘 − 2, 𝑚 + 𝑙 − 1, max{2𝑚, 𝑛}} = max{2𝑚, 𝑛} Полученная в этом случае стратегия тоже будет поблочной. – «Сверху вниз» очищаются короткие строки по столбцам 𝑛 игро ками; – Затем в строке 𝑚 выставляем оставшихся игроков, если 2𝑚 > 𝑛; – Крайние игроки с двух сторон остаются на месте, остальные по следовательно скользят по рёбрам столбцов; – Повторяем предыдущий шаг, пока не дойдём до первой строки; – Так как игроков не меньше 2𝑚, то в каждой «длинной» строке стоит хотя бы по два игрока, все рёбра между которыми очище ны, так что теперь каждый игрок скользит по рёбрам строки в сторону ближней границы графа.

20 В итоге доказали следующее утверждение: Утверждение 4.2. Для графа 𝐵, являющегося результатом склейки двух блоков размеров 𝑚 × (𝑛 + 𝑝 + 𝑘 − 2) и 𝑙 × 𝑛 без отождествления вер шин, верно соотношение 𝑚𝑖𝑥𝑠(𝐵) = 𝑏𝑠(𝐵) = 𝑐𝑚𝑖𝑥𝑠(𝐵) = 𝑐𝑏𝑠(𝐵) = min{𝑚 + 𝑙 − 1, max{𝑛, 2𝑚}𝑚 + 𝑛, max{𝑚, 𝑛 + 𝑘 − 1}, 𝑛 + 𝑘 + 𝑝 − 2} Действительно, минимум может принимать любое из перечисленных значений, для каждого из них в таблице приведён пример на 𝑚, 𝑛, 𝑝, 𝑘, 𝑙. 𝑚 + 𝑙 − 1 max{𝑛, 2𝑚} 𝑚 + 𝑛 max{𝑚, 𝑛 + 𝑘 − 1} 𝑛 + 𝑘 + 𝑝 − 2 𝑚 5 4 5 5 10 𝑛 6 7 4 5 3 𝑝 5 5 9 6 3 𝑘 4 3 8 3 4 𝑙 3 5 6 4 10 5. Блочный граф «крест» Одним из самых распространённых приёмов для нахождения поиско вых чисел является операция взятия минора графа. В том случае, если поиск обладает свойством замкнутости класса графов, поисковое число ко торых меньше 𝑘, относительно взятия минора, это позволяет найти нижние оценки для поискового числа. Сейчас покажем, как результаты предыду щей главы помогают найти поисковые числа графа следующего вида: к каждой из частей границ блока 𝑚 × 𝑚 приклеиваются блоки 𝑚 × 𝑘, 𝑚 × 𝑙, 𝑚 × 𝑝, 𝑚 × 𝑞, что изображено на рисунке 11. У полученного графа 𝐺 выделим четыре минора, каждый из которых получен склейкой блока 𝑚 × 𝑚 с тремя из блоков 𝑚 × 𝑘, 𝑚 × 𝑙, 𝑚 × 𝑝, 𝑚 × 𝑞, а затем воспользуемся тем, что мы знаем поисковые числа для блочных графов такого вида. Получаем, что при 𝑘 6 𝑝, 𝑙 6 𝑞 𝑚𝑖𝑥𝑠(𝐺) > max{𝑀1 , 𝑀2 , 𝑀3 , 𝑀4 }

21 𝑞−1 𝑝−1 𝑚 𝑘−1 𝑙−1 𝑚 Рис. 11. «Граф-крест» 𝑀1 = min{2𝑚, 𝑚 + 𝑙 − 1, 𝑚 + 𝑘 − 1}, 𝑀2 = min{2𝑚, 𝑚 + 𝑞 − 1, 𝑚 + 𝑘 − 1}, 𝑀3 = min{2𝑚, 𝑚 + 𝑞 − 1, 𝑚 + 𝑝 − 1}, 𝑀4 = min{2𝑚, 𝑚 + 𝑙 − 1, 𝑚 + 𝑝 − 1}. Пусть 𝑙 6 𝑘, тогда 𝑀1 = 𝑀4 и 𝑚𝑖𝑥𝑠(𝐺) > max{𝑀1 , 𝑀2 , 𝑀3 } 𝑀1 = min{2𝑚, 𝑚 + 𝑙 − 1}, 𝑀2 = min{2𝑚, 𝑚 + 𝑞 − 1, 𝑚 + 𝑘 − 1}, 𝑀3 = min{2𝑚, 𝑚 + 𝑞 − 1, 𝑚 + 𝑝 − 1}. Теперь заметим, что max{𝑀1 , 𝑀2 , 𝑀3 } = ̸ 𝑚+𝑙−1, так как в этом слу чае 𝑚+𝑙−1 6 2𝑚, но тогда 𝑀2 , 𝑀4 > 𝑚+𝑙−1, потому что 𝑙 = min{𝑙, 𝑘, 𝑝, 𝑞}. Таким образом, всего три варианта, для каждого из который существует стратегия, причём связная. Снова нумеруем строки сверху вниз, столбы

22 слева направо, соответственно вершина 𝑣𝑖,𝑗 находится на пересечении 𝑖–ой строки и 𝑗–го столбца. 1. max{𝑀1 , 𝑀2 , 𝑀3 } = 2𝑚. Тогда с помощью 2𝑚 игроков можно очи стить следующим образом: ∙ 𝑚 игроков 𝑆1 , . . . , 𝑆𝑚 очищают «снизу вверх» блок 𝑚×𝑙, и стоят в вершинах 𝑣𝑚+𝑞−1,𝑝−1 , . . . , 𝑣𝑚+𝑞−1,𝑚+𝑝−1 ; ∙ оставшиеся 𝑚 игроков 𝑆𝑚+1 , . . . , 𝑆2𝑚 ставятся в вершины 𝑣𝑚+𝑞−1,𝑚+𝑝−1 , . . . , 𝑣𝑞−1,𝑚+𝑝−1 ; ∙ игроки 𝑆1 , . . . , 𝑆𝑚 скользят вдоль рёбер столбца и выстраивают ся по диагонали в вершинах 𝑣𝑝−1,𝑚+𝑝−1 , . . . , 𝑣𝑞−1,𝑚+𝑝−1 ; ∙ игроки 𝑆𝑚+1 , . . . , 𝑆2𝑚 скользят по строкам и очищают блок 𝑚 × (𝑘 − 1) «слева направо»; ∙ игроки 𝑆𝑚+1 , . . . , 𝑆2𝑚 ставятся в вершины 𝑣𝑚+𝑞−1,𝑝 , . . . , 𝑣𝑞−1,𝑝 ; ∙ игроки 𝑆1 , . . . , 𝑆𝑚 скользят вверх по рёбрам столбца и очищают столбцы из 𝑚 + 𝑞 + 𝑙 − 2 вершин; ∙ игроки 𝑆𝑚+1 , . . . , 𝑆2𝑚 скользят по строкам и очищают блок 𝑚 × (𝑝 − 1) «справо налево»; 2. max{𝑀1 , 𝑀2 , 𝑀3 } = 𝑚 + 𝑞 − 1, тогда 𝑚 + 𝑞 − 1 игроков смогут очистить граф так: ∙ 𝑚 игроков 𝑆1 , . . . , 𝑆𝑚 очищают «слева направо» блок 𝑚 × 𝑘, и стоят в вершинах 𝑣𝑚+𝑞−1,𝑚+𝑝−1 ,. . . , 𝑣𝑞−1,𝑚+𝑝−1 ; ∙ оставшиеся 𝑞 − 1 игроков 𝑆𝑚+1 , . . . , 𝑆𝑚+𝑞−1 ставятся в вершины 𝑣𝑚+𝑞−1,𝑚+𝑝−1 , . . . , 𝑣1,𝑚+𝑝−1 ; ∙ игроки 𝑆1 , . . . , 𝑆𝑚 скользят вдоль рёбер столбца и выстраивают ся по диагонали в вершинах 𝑣𝑞,𝑝 , . . . , 𝑣𝑚+𝑞−1,𝑚+𝑝−1 , игроки 𝑆𝑚+1 ,

23 . . . , 𝑆2𝑚 скользят по строкам и очищают блок 𝑚×(𝑞−1) «справа налево»; ∙ игроки 𝑆𝑚+1 , . . . , 𝑆2𝑚 становятся в вершины 𝑣𝑚+𝑞+𝑝−2,𝑚+𝑝−1 , . . . , 𝑣𝑚+𝑞−1,𝑚+𝑝−1 ; ∙ все игроки последовательно скользят по рёбрам по своих строк «справа налево» и очищают граф. 3. max{𝑀1 , 𝑀2 , 𝑀3 } = 𝑚 + 𝑝 − 1, тогда 𝑚 + 𝑝 − 1 игроков смогут очистить аналогично пункту 2; 4. max{𝑀1 , 𝑀2 , 𝑀3 } = 𝑚 + 𝑘 − 1, тогда 𝑚 + 𝑘 − 1 игроков смогут очистить аналогично пункту 2, начиная с очищения «сверху вниз» блока (𝑞 − 1) × 𝑚. Заметим, что приведённые стратегии получились связными и блочными. Таким образом, получим, что 𝑚𝑖𝑥𝑠(𝐺) = 𝑐𝑚𝑖𝑥𝑠(𝐺) = 𝑏𝑠(𝐺) = 𝑐𝑏𝑠(𝐺) = max{𝑀1 , 𝑀2 , 𝑀3 } 𝑀1 = min{2𝑚, 𝑚 + 𝑙 − 1}, 𝑀2 = min{2𝑚, 𝑚 + 𝑞 − 1, 𝑚 + 𝑘 − 1}, 𝑀3 = min{2𝑚, 𝑚 + 𝑞 − 1, 𝑚 + 𝑝 − 1}. 6. Связный поиск Докажем утверждение, показывающее одну из основных особенностей связного поиска, сформулированную в [7]. Мы приведём строгое доказа тельство следующего факта. Утверждение 6.1. Существует класс графов, для которых связный сме шанный поиск не замкнут относительно взятия минора, то есть суще ствует пара (𝐺, 𝐻), где G — минор H и 𝑐𝑚𝑖𝑥𝑠(𝐺) > 𝑐𝑚𝑖𝑥𝑠(𝐻).

24 𝑙 𝐵1 𝑘 𝐵4 𝐵3 𝑒 𝑘−1 𝐵2 𝐵5 Рис. 12. Граф 𝐻 Д о к а з а т е л ь с т в о. Граф 𝐻 = 𝐺 ∪ {𝑒} (рисунок 12), 𝑚𝑖𝑥𝑠(𝐻) = 2𝑘 = 𝑐𝑚𝑖𝑥𝑠(𝐻) (оптимальная стратегия для смешанного поиска «слева направо» является связной). Блоки графа 𝐺 назовём 𝐵1 , 𝐵2 , 𝐵3 , 𝐵4 , 𝐵5 , 𝐵3 имеет общие вершины с 𝐵1 , 𝐵2 , 𝐵4 , 𝐵5 , 𝐵1 размера 𝑘×𝑙, 𝐵2 — (𝑘−1)×𝑙, 𝐵3 — 2𝑘×𝑙, 𝐵4 — 𝑘×𝑙, 𝐵5 — (𝑘−1)×𝑙, 𝑙 ≫ 𝑘 > 3. Если в оптимальной стратегии граф очищается поблочно-связно, то возможны следующие варианты: ∙ Первым очищается 𝐵3 , после чего 𝐵3 защищен на шаге после очи щения последнего ребра блока. Значит, на всех вершинах блока, ко торым инцидентны ребра другого блока, поставлены игроки. Таким образом, 𝑐𝑏𝑠(𝐺) > 4𝑘 − 2. ∙ Первым очищается 𝐵1 . Тогда в силу требования связности затем очи щается 𝐵3 . Рассуждая, аналогично предыдущему пункту, получаем, что 𝑐𝑏𝑠(𝐺) > 3𝑘 − 2. ∙ Первым очищается 𝐵2 . Тогда в силу требования связности затем очи щается 𝐵3 . Рассуждая, аналогично предыдущему пункту, получаем, что 𝑐𝑏𝑠(𝐺) > 3𝑘 − 1. В силу симметрии графа получаем так же оценки, когда первым очи щается блок 𝐵4 или 𝐵5 , то есть в любом случае 𝑐𝑏𝑠(𝐺) > 3𝑘 − 2 > 2𝑘. Введем «систему координат»: присвоим всем столбцам вершин номера от 1 до 3𝑙 слева направо, а всем строкам — номера от 1 до 2𝑘 сверху вниз, тогда 𝑣𝑖,𝑗 = (𝑖, 𝑗). Нас интересует связный смешанный поиск.

25 Существует стратегия, для которой требуется 3𝑘 − 1 игрок, то есть 𝑐𝑚𝑖𝑠𝑥(𝐺) 6 3𝑘 − 1: очищается блок 𝐵1 слева направо, после чего 𝑘 игроков стоят в вершинах 𝑣𝑖,𝑙 , 𝑙 ∈ 1 : 𝑘. Теперь поставим еще 2𝑘 − 1 игрока таким образом: одного игрока в вершину 𝑣𝑘+1,𝑙 , по два в 𝑣𝑖,𝑙 , 𝑙 ∈ 𝑘 + 2 : 2𝑘. Теперь по одному игроку из вершин 𝑣𝑖,𝑙 , 𝑙 ∈ 𝑘 + 2 : 2𝑘 очищают блок 𝐵2 справа налево, после чего игроки из 𝑙–го столбца очищают блок 𝐵3 «слева направо», а затем блоки 𝐵4 , 𝐵5 . Для графа блочной структуры можно определить ячейку – полный двудольный подграф, порожденный четырьмя вершинами, по две в каждой доле. Заметим, что если в ячейке очищены два противоположных ребра, то и оставшиеся два ребра тоже очищены. Пусть это не так: среди этих ребер есть грязное 𝑒 = (𝑢, 𝑣). Тогда в 𝑢, 𝑣 стоят игроки. Но в таком случае по определению смешанного поиска ребро очищено, противоречие. Из этого следует, что если в блоке все строки очищены, то блок полностью очищен. Итак, пусть первым в оптимальной стратегии очищается 𝐵3 . Тогда рассмотрим, для примера, блок 𝐵1 и оценим, сколько в нем игроков. Так как 𝐵3 чист, то для любой строки блока 𝐵1 верно, что либо все ребра стро ки очищены, либо в строке стоит хотя бы один игрок. Если для всех строк выполняется второй вариант, то получаем оценку снизу на количество иг роков 𝑘 = 𝑚𝑖𝑥𝑠(𝐵1 ). Покажем, что в первом варианте игроков потребуется больше. Пусть есть полностью очищенная строка 𝑖. Тогда уже для любого столбца верно, что либо все его ребра очищены, либо в нем есть хотя бы один игрок. Если для всех столбцов выполняется второй вариант, то полу чаем оценку снизу на количество игроков 𝑙 >> 𝑘, то есть при достаточно большом 𝑘, например, 𝑘 = 10𝑙, подобная стратегия не может быть опти мальной. Таким образом, существует столбец 𝑗, все ребра которого очище ны (в столбце нет игрока). Рассмотрим его. Так как ни в какой вершине 𝑣𝑖,𝑗 , 𝑖 ∈ 1 : 𝑘 не стоит игрок, то для неё верно, что все инцидентные ей ребра

26 очищены. Получаем полностью очищенный столбец ячеек (у ячейки есть пара очищенных ребер). Теперь рассмотрим строки с номерами от 1 до 𝑘 и столбцы с номерами от 1 до 𝑗 − 1 (считаем, что 𝑗 − 1 > 1). Рассмотрим такой алгоритм: 𝑝 = 1, 𝑞 = 𝑗 − 1; while 𝑝 < 𝑘 + 1 do while 𝑞 > 0 do if 𝑒 = (𝑣𝑝,𝑞 , 𝑣𝑝,𝑞−1 ) очищено then 𝑝 + +; {опускаемся на строку вниз} else 𝑆 скользит вдоль 𝑒 = (𝑣𝑝,𝑞 , 𝑣𝑝,𝑞−1 ); 𝑝 + +; {в вершине 𝑣𝑝,𝑞−1 есть игрок 𝑆, а все инцидентные ей ребра, кроме 𝑒, уже очищены}; 𝑞 − −; {просматриваем следующий столбец} {𝑒 = (𝑣𝑝,𝑞 , 𝑣𝑝+1,𝑞 ) очищено как ребро в ячейке парой очищенных противо положных ребер в обоих случаях} Заметим, что в результате работы алгоритма мы очистим все вершины 𝑣𝑝,𝑞 , 𝑝 ∈ 1 : 𝑖 − 1, 𝑞 ∈ 1 : 𝑘. Аналогично очищаем оставшиеся вершины. Мы показали, как в таком случае с помощью игроков, находящихся в вершинах блока 𝐵1 , преобразовать стратегию так, чтобы в случае наличия очищен ной строки и очищенного столбца можно очистить весь блок до очищения блока 𝐵3 , что противоречит предположению. Таким образом, получаем, что для каждого 𝐵𝑗 , 𝑗 = 1, 2, 4, 5 верно, что в нем находится не меньше, чем 𝑚𝑖𝑥𝑠(𝐵𝑗 ) игроков. Тогда 𝑐𝑚𝑖𝑥(𝐺) = 4𝑘 − 2 > 3𝑘 − 1. Итак, получили, что для любой стратегии, использующей 𝑚 игроков, где первым очищается блок 𝐵3 , существует стратегия, очищающая граф не более чем 𝑚 игроками, в которой 𝐵3 не является первым очищенным блоком.

27 Пусть тогда первым очищается 𝐵1 . Рассмотрим момент, когда в блоке 𝐵1 есть очищенное множество и начинает очищаться 𝐵4 или 𝐵5 . В таком случае существует путь из 𝐵1 в один из этих блоков. Этот путь целиком лежит в 𝐵3 и проходит по всем столбцам ячеек. Тогда для каждого столбца верно, что либо в нем есть игрок, либо он полностью очищен. Если для всех верно первое, то уже есть 𝑙 игроков, что очень много. Значит, есть очищен ный столбец, в котором нет игрока. Тогда повторяем алгоритм, описанный выше, и получаем очищенный 𝐵3 . Доказали, что в оптимальной стратегии как только начинается очищение блоков 𝐵4 , 𝐵5 , блок 𝐵3 очищен. Рассматриваем шаг, когда в 𝐵3 впервые появился очищенный столбец 𝑗. Уже знаем, что в этот момент очищенные множества располагаются в блоках по одну сторону от 𝐵3 . Случай 1 Очищенное множество есть только в блоке 𝐵3 , в остальных блоках, возможно, лишь очищенная граница 𝐵3 . Тогда в каждой строке есть хотя бы один игрок для защиты от загрязнения на данном шаге, за исключением строки с номером 𝑘 + 1. Если там нет игрока, то она является полностью очищенной, откуда получаем в силу выбора столбца необходи мость 𝑙 − 1 ≫ 3𝑘 − 1 игрока. Значит, в блоке хотя бы 2𝑘 игроков. Теперь отметим, что загрязненные ребра есть с обеих сторон от очищенного столб ца, значит, если в строке очищено хотя бы 1 ребро, то необходимо строго больше 2𝑘 игроков. Следовательно, в строке чистых ребер нет, то есть в блоке 𝐵3 очищен только один столбец, причем на каждой вершине столб ца стоит игрок. На следующем шаге либо появляется новый игрок, откуда 𝑐𝑚𝑖𝑥𝑠(𝐻) < 𝑐𝑚𝑖𝑥𝑠(𝐺), либо переставляется один из игроков. Из-за связ ности мы можем удалять только игроков из крайних ячеек, но мы могли получить такую конфигурацию последовательным выставлением игроков, то есть очищение столбца было лишним шагом, а стратегию, в которой достигается этот случай, можно преобразовать таким образом, что к мо

28 менту такой расстановки игроков и расположения очищенных ребёр ещё не встречался шаг, на котором бы был очищенный столбец. Случай 2 Есть очищенный связный подграф 𝑊 хотя бы в одном из бло ков, пусть 𝐵1 , причем 𝑊 не является границей с 𝐵3 . Аналогично предыду щему случаю получаем, что в блоке хотя бы 2𝑘 игроков. Так как 𝐵4 , 𝐵5 загрязнены, то все 2𝑘 игроков находятся не левее очищенного столбца. Покажем, что 𝑗 = 𝑙, то есть первый очищенный столбец блока 𝐵3 — ле вая граница 𝐵3 . Пусть не так, тогда от 𝑊 существует очищенный путь до столбца 𝑗, проходящий через все столбцы 𝐵3 с номерами, меньшими 𝑗, а 𝑗 — первый очищенный столбец, то есть во всех столбцах с меньшими но мерами есть неочищенные ребра, следовательно, в них есть игроки, таким образом, 𝑐𝑚𝑖𝑥𝑠(𝐺) > 2𝑘. 1. 𝐵1 очищен не полностью. Тогда есть строки, в которых есть и очи щенное, и загрязненное рёбра, то есть там заведомо есть игрок. Если их нет, то все строки либо полностью очищены, а значит и блок очи щен, либо есть полностью загрязненная строка, а значит для защиты 𝑊 есть игрок внутри блока и 𝑐𝑚𝑖𝑥𝑠(𝐺) > 2𝑘. 2. 𝐵1 полностью очищен, в 𝐵2 есть очищенный связный подграф, опи санный выше. Аналогично предыдущему подслучаю получаем, что 𝑐𝑚𝑖𝑥𝑠(𝐺) > 2𝑘. 3. 𝐵1 , 𝐵2 полностью очищены. Рассмотрим шаг, когда впервые есть очи щенные ребра в строках 1 и 2𝑘. Из-за связности на этом шаге заве домо выставлено 2𝑘 игроков, по одному в каждой строке. Покажем, что есть строка, в которой более одного игрока. Видно, что на каж дом шаге в строке очищается не более двух ребер: скольжение по ребру увеличивает количество очищенных ребер в строке максимум на 1, а постановка игрока — на два. Пусть на данном шаге очисти

29 лось ребро 𝑒 в 𝐵1 (если очистилось 2 ребра, рассмотрим самое левое). Если 𝑒 = (𝑣1,𝑖 , 𝑣1,𝑖+1 ), 𝑖 ̸= 1, то в строке два игрока для защиты от загрязнения на данном шаге, а всего не менее 2𝑘 + 1. Иначе, чтобы выйти на границу блока 𝐵1 и попасть в 𝐵3 необходимо пройти через 𝑙 − 2 > 3𝑘 − 1 столбца, в каждом из которых есть игрок, так как все ребра 𝑒 = (𝑣1,𝑖 , 𝑣1,𝑖+1 ), 𝑖 ̸= 1, 2, загрязнены. 4. 𝐵1 полностью очищен, в 𝐵2 очищен лишь столбец 𝑙. Тогда в вершинах 𝑣𝑙,𝑖 , 𝑖 ∈ 𝑘 + 2, . . . , 2𝑘 стоят игроки. Пусть больше не требуется новых игроков. Для строк c номерами, меньшими 𝑘 + 2, верно следующее: если в вершине 𝑣𝑖,𝑦 , 𝑦 ∈ 𝑙 : 2𝑙 − 1 стоит игрок, то в (𝑖 − 1)–ой строке в блоке 𝐵3 игрок стоит в вершине 𝑣𝑖−1,𝑧 , где 𝑧 6 𝑦 + 1. Для 𝑖 = 𝑘 + 1 это очевидно, а дальше это верно, так как в столбцах с номерами, большими 𝑦 + 1 еще нет игроков. Если новых игроков не требуется, то ∙ один из игроков из вершин 𝑣𝑙,𝑖 , 𝑖 ∈ 𝑘 + 2, . . . , 2𝑘 покидает вер шину, а из-за связности это могут сделать только игроки c двух нижних вершин, и столбец перестает быть полностью очищен ным. Тогда такое же положение игроков и очищенных ребер можно получить, не очищая столбца: очистим 𝐵1 «слева напра во», выставим нужное количество игроков (как в оптимальной стратегии после ухода игрока из вершины стобца) в 𝑙–ый стол бец, а затем последовательно проскользим каждым игроком вдоль ребра до нужной позиции, после чего поставим удаленного игро ка на место, которое ему соответствовало на следующем шаге исходной стратегии; ∙ перемещается игрок из вершин 𝑣𝑙,𝑖 , где 𝑖 ∈ 1, . . . , 𝑘 + 1, при этом по доказанному выше в 𝑖–ой строке игрок стоит не дальше (𝑙 + 𝑘 + 2 − 𝑖)–го столбца. Значит, в какой-то момент получим,

30 что новых ребер больше не очистить. Если на следующем шаге покидает вершину игрок из 𝐵2 , то верно предыдущее рассуж дение. Иначе либо игрок скользит влево по ребру строки, и мы можем преобразовать стратегию описанным выше способом (убе рем ненужные шаги), либо загрязняется блок 𝐵1 и очищенный столбец, так как игрок больше не защищает строку от загряз ненных столбцов, а значит, мы можем преобразовать стратегию, последовательно выставляя оставшихся игроков в 𝑙–ом столбце. То есть, если не добавлять новых игроков, то стратегия преобразу ется таким образом, что получается та же конфигурация игроков и очищенных ребер, но при этом еще нет очищенного столбца. Тогда продолжаем дальше преобразованную стратегию и ждем следующе го появления очищенного столбца в блоке 𝐵3 , после чего попадаем в один из случаев и так далее. В итоге, на каком-то шаге будет выстав лено строго больше 2𝑘 игроков. Таким образом, утверждение доказа но. 7. Удаление блока Минором графа 𝐺 называется граф 𝐻, полученный из графа 𝐺 с по мощью последовательного удаления ребёр, вершин и стягивания ребёр. Из вестно, что для любого минора 𝐻 графа 𝐺 верно, что 𝑚𝑖𝑥𝑠(𝐻) 6 𝑚𝑖𝑥𝑠(𝐺). С помощью этого свойства найдём поисковые числа следующего класса блочных графов. Рассмотрим блок 𝑚 × 𝑚, из которого удалён блок 𝑘 × 𝑘, где 𝑘 < 𝑚 (рисунок 13). Такие графы блочной структуры можно получить в результате склейки минимум четырёх блоков, но в этом случае удобнее рассматривать новую процедуру удаления блока.

31 Рис. 13 Удалим в выделенных блоках все вертикальные рёбра, не входящие в границу: Рис. 14 Будем стягивать выделенные горизонтальные рёбра поэтапно справа налево 𝑘 − 1 раз: Рис. 15

32 Проделаем ту же самую процедуру с блоками, выделенными пункти ром и получим: 𝑞 𝑝 Рис. 16 Для таких графов 𝑚𝑖𝑥𝑠(𝐻) = 𝑚 − 𝑘 + 2, то есть совпадает с размером блока. Предъявим стратегию, которая очищает исходный граф с помощью 𝑚 − 𝑘 + 2 игроков. Снова занумеруем все вершины 𝑣𝑖,𝑗 , 𝑖, 𝑗 ∈ 1 : 𝑚 слева направа и снизу вверх. Обозначим 𝑝 и 𝑞 размеры блоков 𝑘 × 𝑞, 𝑝 × 𝑘, над рёбрами которых и проводились операции удаления и стягивания, причём 𝑝 > 𝑚 − 𝑝 − 𝑘 + 2, 𝑞 > 𝑚 − 𝑞 − 𝑘 + 2, 𝑝 > 𝑞, иначе можем переобозначить. Стратегия будет выглядеть так: ′ ∙ Поставить по 2 игрока в вершины 𝑣𝑞,𝑝+𝑘−2 , . . . , 𝑣𝑞,𝑚 , игроки 𝑆1′ , . . . , 𝑆𝑚−𝑝−𝑘+2 во время поиска остаются на этих местах, остальных игроков будем использовать для очищения; ∙ Последовательно скользить игроками𝑆1 , . . . , 𝑆𝑚−𝑝−𝑘+2 вдоль ребёр со ответствующих строк до вершин 𝑣𝑞,𝑝+𝑘−2 . . . 𝑣𝑞+𝑝+𝑘−2−𝑚,𝑚 , то есть иг роки выстраиваются в диагональ; ∙ При необходимости доставить в вершины вида 𝑣𝑖,𝑚 игроков так, что бы в каждом столбце с номерами от 1 до 𝑞 стояли игроки. Это воз можно, так как мы используем 𝑝 > 𝑞 игроков для очищения; ∙ Снова скользим активными игроками вниз по рёбрам столбца, пока это возможно, выстраивая по завершении игроков по диагонали. При

33 необходимости доставляем игроков и скользим по рёбрам строк и так далее. Полученная стратегия связная, так что 𝑐𝑚𝑖𝑥𝑠(𝐺) = 𝑚 − 𝑘 + 2. Для этого частного случая удаления блока оказалось достаточно удачно взять минор, однако в общем случае нахождение поисковых чисел является более сложной процедурой. Рассмотрим теперь класс блочных графов, состоящих из блоков раз мера 𝑚 × 𝑚, в которых удален блок 1 × 𝑘, где 𝑘 < 𝑚. Разобьём полученные графы на два класса: в первом случае удалёный блок расположен горизон тально (рисунок 17), а во втором — вертикально (рисунок 18). 𝑚1 𝑘 𝑚2 𝑚4 𝑚3 Рис. 17 Пусть 𝑚3 = max 𝑚𝑖 . Обозначим через 𝑎 = min 𝑚𝑖 . Так же заметим, 𝑖∈1:𝑛 𝑖∈1:𝑛 что 𝑚𝑖𝑥𝑠(𝐺) 6 𝑚𝑖𝑥𝑠(𝐵), где 𝐵 — блок размера 𝑚 × 𝑚. Предположим, что 𝑚𝑖𝑥𝑠(𝐺) < 𝑚, а значит в любой момент времени есть столбец и строка без игроков. Зафиксируем шаг, когда появились первый очищенный столбец или строка. Если это столбец, то существует столбец без игроков, в нём нет очищенных рёбер, откуда получаем, что в каждой строке стоит игрок и оценку 𝑚𝑖𝑥𝑠(𝐺) > 𝑚. В случае строки возможны варианты

34 ∙ Очищенная строка 𝑖 находится в блоке 𝑚3 × 𝑚. По предположению у нас есть строка и столбец без игроков. Заметим, что столбец не может быть ни полностью очищенным, ни полностью загрязнённым, откуда получается, что столбец без игроков 𝑗, где 𝑗 ∈ 𝑚1 +1 : 𝑚1 +𝑘 −1, при чём все его рёбра до строки 𝑚3 включительно очищены. Если строка без игроков расположена по одну сторону от удалённого блока с 𝑖, то получаем 𝑚𝑖𝑥𝑠(𝐺) > 𝑚. Значит, она находится среди строк с номера ми, большими 𝑚3 . Теперь смотрим на шаг, когда впервые появилась описанная конструкция столбца, то есть мы можем убрать игрока со столбца 𝑗. На предыдущем шаге в столбце 𝑗 стоял хотя бы один иг рок, значит существовал столбец 𝑗 ′ , в котором не было игроков, при этом все его рёбра до строки 𝑚3 загрязнены, следовательно между столбцами 𝑗, 𝑗 ′ стояли 𝑚3 игроков. Пусть 𝑗 ′ > 𝑗. Если во всех строках блока 𝑚× 𝑚 стоят хотя бы два игрока, то 𝑚𝑖𝑥𝑠(𝐺) > 2𝑚3 . Иначе есть строка 𝑖′ , 𝑖′ 6 𝑚3 , все рёбра которой до столбца 𝑚1 включительно очищены, а в вершинах 𝑣1,𝑖′ , . . . , 𝑣𝑚1 ,𝑖′ нет игроков. Но существует пол ностью загрязнённая строка, откуда получаем что в первых 𝑚1 > 𝑎 столбцах стоят игроки, откуда оценка 𝑚𝑖𝑥𝑠(𝐺) > 𝑚3 + 𝑎. В итоге, 𝑚𝑖𝑥𝑠(𝐺) > min{𝑚, 𝑚3 + 𝑎}. ∙ Очищенная строка 𝑖 находится в блоке 𝑚4 ×𝑚. Аналогично получаем наличие столбца описанного 𝑗 с той лишь разницей, что теперь загряз нены вершины столбца в строках, строго меньших 𝑚3 + 1, возможно, такой столбец не один. Покажем, что если 𝑚𝑖𝑥𝑠(𝐺) 6 min{𝑚, 𝑚3 +𝑎}, то пока такой столбец существует, в любом столбце из 𝑚 вершин дол жен стоять игрок. Рассмотрим первый шаг, на котором снимается последний игрок с одного из столбцов длины 𝑚. Получается, в этот момент по одну из сторон от столбца 𝑗 стоят 𝑚3 столбцов. Так во всех столбцах по другую сторону стоит игрок, то заведомо выставле

35 𝑚1 𝑚3 𝑚4 𝑘 𝑚2 Рис. 18 но 𝑚3 + 𝑎 игроков. Теперь покажем, что 𝑚𝑖𝑥𝑠(𝐺) = min{𝑚, 𝑚3 + 𝑎}. Для 𝑚 игроков подойдёт связная стратегия «слева направо», например. Чтобы очистить граф за 𝑚3 + 𝑎 игроков, воспользуемся стратегией, описанной для квадра та: 𝑎 игроков стоят на месте в той части графа, где достигается минимум 𝑚𝑖 а 𝑚3 очищает граф так же, как и в случае с квадратными удалёнными блоками. Теперь пусть 𝑚2 = max 𝑚𝑖 . Обозначим через 𝑎 = min 𝑚𝑖 . 𝑖∈1:𝑛 𝑖∈1:𝑛 В этом случае вертикального расположения удалённого блока заме тим, что блок размера 𝑚2 + 𝑚4 × 𝑚 будет минором исходного графа, а так как (𝑚2 + 𝑚4 ) < 𝑚, то 𝑚𝑖𝑥𝑠(𝐺) > 𝑚2 + 𝑚4 . С использованием 𝑚2 + 𝑚4 иг роков исходный граф можно очистить такой же стратегией, как и в случае, когда 𝑚3 = max 𝑚𝑖 . 𝑖∈1:𝑛 Давайте рассмотрим блоки размера 𝑚 × 𝑛, где 𝑚 < 𝑛, с удалённым блоком 1 × 𝑘. Возможно несколько вариантов расположения (рисунки 19, 20), рассмотрим их. Теперь будем поочередно удалять рёбра между вершинами столбца 𝑚1 + 1, стянем рёбра между вершинами 𝑣𝑖,𝑚1 +1 и 𝑣𝑖,𝑚1 +2 . Если получен

36 𝑚1 𝑚2 𝑘 𝑚4 𝑚3 Рис. 19 ный блок 𝐵1 имеет размер 𝑚 × 𝑚, то знаем 𝑚𝑖𝑥𝑠(𝐵1 ), иначе продолжаем процедуру. В итоге либо в какой-то момент получим блок 𝐵𝑙 размером 𝑚 × 𝑚1 + 𝑚2 , причём 𝑚1 + 𝑚2 > 𝑚, а значит 𝑚𝑖𝑥𝑠(𝐵𝑙 ) = 𝑚, либо полу чим квадрат с удалённым блоком 1 × 𝑘, тогда 𝑚𝑖𝑥𝑠(𝐵𝑙 ) = min{𝑚, 𝑎 + 𝑏}, где 𝑎 = max 𝑚𝑖 , 𝑏 = min 𝑚𝑖 . Таким образом, 𝑚𝑖𝑥𝑠(𝐺) > min{𝑚, 𝑎 + 𝑏}. 𝑖∈1:4 𝑖∈1:4 На самом деле, 𝑚𝑖𝑥𝑠(𝐺) = min{𝑚, 𝑎 + 𝑏}, стратегии строятся по тому же принципу, что и в случае квадрата. Пусть 𝑏 = 𝑚3 , тогда есть несколько вариантов: 1. 𝑎 + 𝑚3 = 𝑚 В этом случае рассмотрим подграф 𝐵 исходного графа, 𝐵 является блоком 𝑚 × 𝑚, из которого удалён блок 1 × 𝑘, а 𝑚𝑖𝑥𝑠(𝐵) = 𝑚, так как 𝑚3 + 𝑎 = 𝑚. Существует стратегия с использованием 𝑚 игроков очищает граф и является связной, например, «слева направо». 2. 𝑎 + 𝑚3 > 𝑚 Рассмотрим подграф 𝐵, для которого 𝑚3 = 𝑚′3 , 𝑚1 = 𝑎 такое, что 𝑚′3 + 𝑎 = 𝑚. Заметим, что для полученного блочного графа 𝑏 = 𝑚′3 ,

37 𝑚1 𝑚3 𝑚4 𝑘 𝑚2 Рис. 20 так как 𝑎 + 𝑚4 6 𝑚2 + 𝑚4 < 𝑚, а 𝑎 + 𝑚′3 = 𝑚, следовательно 𝑚′3 > 𝑚4 > 𝑎, 𝑚′3 > 𝑚2 > 𝑎. Получаем, что 𝑚𝑖𝑥𝑠(𝐺) = 𝑚, как и в предыдущем случае. 3. 𝑎 + 𝑚3 < 𝑚 Заметим, что тогда 𝑎 ̸= 𝑚1 , т.к. 𝑚1 + 𝑚3 = 𝑛 > 𝑚. Тогда рассмотрим такой подграф 𝐵, что 𝑚1 = 𝑚′1 > 𝑎 такое, что 𝑚′1 + 𝑚3 = 𝑚, то есть удалим из графа лишние столбцы. Снова получили, что 𝐵 являет ся блочным графа нужной нам структуры, для которого мы знаем, что 𝑚𝑖𝑥𝑠(𝐵) = min{𝑚3 + 𝑎, 𝑚}. Связные выигрывающие стратегии строятся уже описанными способами. Если же 𝑏 = 𝑚2 , то блок 𝐵 размера (𝑚2 + 𝑚4 ) × 𝑛 — минор графа 𝐺, 𝑚𝑖𝑥𝑠(𝐵) = 𝑚2 + 𝑚4 . Докажем, что 𝑎 = 𝑚4 . Из того, что 𝑚2 + 𝑚4 < 𝑚 < 𝑛, 𝑚1 + 𝑚3 = 𝑛, 𝑚2 > 𝑚3 , 𝑚1 , получаем 𝑚4 < 𝑚3 , 𝑚4 < 𝑚1 , а значит 𝑎 = 𝑚4 . С помощью (𝑎 + 𝑏) игроков исходный граф очищается, причём стратегия связная. Теперь рассмотрим общий случай: есть блок 𝑚×𝑛, из которого удален блок размера 𝑘1 × 𝑘2 , пример показан на рисунке 21.

38 𝑚3 𝑘2 𝑚4 𝑚2 𝑘1 𝑚1 Рис. 21 Пусть 𝑏 = 𝑚4 = max 𝑚𝑖 , 𝑎 = max 𝑚𝑖 . Рассмотрим подграф исходного 𝑖∈1:4 𝑖∈1:4 графа, где 𝑚3 = 𝑎 (граница полученного подграфа выделена). Заметим, что граф 𝐵, полученный удалением из блока 𝑚 × 𝑎 + 𝑏 удалением блока 𝑘1 × 1 является минором исходного графа, а 𝑚𝑖𝑥𝑠(𝐵) = min{𝑚, 𝑎 + 𝑏}. Понятно, что исходный граф можно очистить этим количеством игроков уже описанными стратегиями. 8. Путевая ширина графа Поисковые числа связаны соотношениями с такими инвариантами гра фа, как древесная и путевая ширина. В этом разделе рассматриваются некоторые свойства путевой ширины, помогающие при построении страте гий. Древесной декомпозицией графа 𝐺 =< 𝑉, 𝐸 > называется такое дере во 𝑇 , вершины которого 𝑉1 , . . . , 𝑉𝑛 , 𝑉𝑖 ⊂ 𝑉 для любого 𝑖 ∈ 1 : 𝑛, удовлетво ряют следующим свойствам:

39 1. 𝑛 ⋃︀ 𝑉𝑖 = 𝑉 , то есть каждая вершина исходного графа 𝐺 входит хотя 𝑖=1 бы в одну вершину древесной декомпозиции; 2. Если вершина 𝑣 исходного графа содержится в 𝑉𝑖 ∩𝑉𝑗 , то 𝑣 содержится во всех вершинах древесной декомпозиции на пути из 𝑉𝑖 в 𝑉𝑗 ; 3. Если существует ребро (𝑣, 𝑤) в исходном графе, то существует вер шина древесной декомпозиции 𝑉𝑘 , что вершины 𝑣, 𝑤 ∈ 𝑉𝑘 , то есть смежные вершины входят вместе в хотя бы одну вершину древесной декомпозиции. Шириной w(T) древесной декомпозиции T графа 𝐺 называется мощ ность максимальной её вершины минус один, то есть max |𝑉𝑖 |−1. Древесной 𝑖∈1:𝑛 шириной tw(𝐺) графа 𝐺 называется минимальная ширина среди всех воз можных древесных декомпозиций графа. Если рассматривать только те древесные декомпозиции, где полученное дерево является путём, то ана логично определяется путевая декомпозиция и путевая ширина pw(G) графа 𝐺. Понятно, что 𝑝𝑤(𝐺) > 𝑡𝑤(𝐺). Сформулируем несколько очевидных свойств путевой декомпозиции связного графа: Утверждение 8.1. Пусть 𝑉1 , . . . , 𝑉𝑛 какая-то путевая декомпозиция 𝑃1 графа 𝐺, где 𝑉𝑖 ⊆ 𝑉𝑖+1 для какого-то 𝑖. Тогда 𝑉1 , . . . , 𝑉𝑖−1 , 𝑉𝑖+1 , . . . 𝑉𝑛 — тоже путевая декомпозиция 𝑃2 графа 𝐺, при этом 𝑤(𝑃1 ) = 𝑤(𝑃2 ). Д о к а з а т е л ь с т в о. Покажем, что 𝑉1 , . . . , 𝑉𝑖−1 , 𝑉𝑖+1 , . . . 𝑉𝑛 — путевая де 𝑛 𝑛 ⋃︀ ⋃︀ композиция графа 𝐺. Так как 𝑉𝑖 ⊂ 𝑉𝑖+1 , то 𝑉𝑘 = 𝑉𝑘 = 𝑉 , то есть 𝑘=1, 𝑘̸=𝑖 𝑘=1 свойство 1 выполняется. Свойство 3 верно, так как все смежные вершины из 𝑉𝑖 учитываются 𝑉𝑖+1 , а свойство 2 по той же причине, что и свойство 1, а так как |𝑉𝑖 | 6 |𝑉𝑖+1 |, то 𝑤(𝑃1 ) = 𝑤(𝑃2 ). Аналогично доказывается следующее утверждение:

40 Утверждение 8.2. Пусть 𝑉1 , . . . , 𝑉𝑛 — какая-то путевая декомпозиция 𝑃1 графа 𝐺, где 𝑉𝑖+1 ⊆ 𝑉𝑖 для какого-то 𝑖. Тогда 𝑉1 , . . . , 𝑉𝑖 , 𝑉𝑖+2 , . . . 𝑉𝑛 — тоже путевая декомпозиция 𝑃2 графа 𝐺, при этом 𝑤(𝑃1 ) = 𝑤(𝑃2 ). Утверждение 8.3. Пусть 𝑉1 , . . . , 𝑉𝑛 — какая-то путевая декомпозиция 𝑃1 связного графа 𝐺 = (𝑉, 𝐸), |𝑉 | > 1, причём подграф, индуцирован ный 𝑉𝑖 для какого-то 𝑖, содержит только изолированные вершины. Тогда 𝑉1 , . . . , 𝑉𝑖−1 , 𝑉𝑖+1 , . . . 𝑉𝑛 — тоже путевая декомпозиция 𝑃2 связного графа 𝐺, при этом 𝑤(𝑃1 ) > 𝑤(𝑃2 ). Д о к а з а т е л ь с т в о. Так как граф связный, изолированных вершин нет, значит, для любой вершины существует вершина, смежная с ней, так что любая вершина 𝑣 ∈ 𝑉𝑖 входит в ещё какую-то вершину путевой деком позиции 𝑃1 , так что свойства 1 и 3 выполняются для 𝑃2 тоже. Так как 𝑃1 — путевая декомпозиция, то для неё выполняется свойство 2, тогда и для ⋂︀ 𝑃2 оно выполняется: если 𝑣 ∈ 𝑉𝑖 𝑉𝑗 , 𝑖 < 𝑗, то 𝑣 ∈ 𝑉𝑘 , где 𝑘 ∈ 𝑖 + 1 : 𝑗 − 1. Таким образом, доказано, что 𝑃2 — путевая декомпозиция. Из того, что все вершины 𝑃2 содержатся в 𝑃1 , следует 𝑤(𝑃1 ) > 𝑤(𝑃2 ). Утверждение 8.4. Пусть 𝑉1 , . . . , 𝑉𝑛 — какая-то путевая декомпозиция 𝑃1 связного графа 𝐺, 𝑣 ∈ 𝑉𝑖 , 𝑣 ∈ / 𝑉𝑖+1 , где 𝑣 — вершина исходного графа 𝐺, причём 𝑣 не смежна ни с одной вершиной 𝑣 ′ ∈ 𝑉𝑖 . Пусть 𝑉𝑖′ = 𝑉𝑖 ∖ 𝑣. То гда 𝑉1 , . . . , 𝑉𝑖−1 , 𝑉𝑖′ , 𝑉𝑖+1 , . . . 𝑉𝑛 — тоже путевая декомпозиция 𝑃2 связного графа 𝐺, при этом 𝑤(𝑃1 ) > 𝑤(𝑃2 ). Д о к а з а т е л ь с т в о. Из связности графа следует, что 𝑣 ∈ 𝑉𝑘 для какого-то 𝑘 ̸= 𝑖, 𝑘 ∈ 1 : 𝑛, тогда свойство 1 выполнено. Так как 𝑣 ∈ 𝑉𝑖 , 𝑣 ∈ / 𝑉𝑖+1 , то свойство 2 тоже выполнено, так как для любой вершины 𝑣 ′ ∈ 𝑉, 𝑣 ′ ̸= 𝑣 верно из того, что 𝑃1 — путевая декомпозиция, а вершина 𝑣 удалена только из последней вершины путевой декомпозиции, содержа щей 𝑣. Cвойство 3 выполняется, так как 𝑣 — изолированная вершина в подграфе, индуцированном вершинами из 𝑉𝑖 .

41 Заметим, что если вершина 𝑣 ∈ 𝑉𝑖 , 𝑣 ∈ / 𝑉𝑖+1 , при этом для любой вершины 𝑣 ′ ∈ 𝑉 , 𝑣 ′ смежна с 𝑣, верно, что существует 𝑘(𝑣 ′ ) < 𝑖 такой, что 𝑣, 𝑣 ′ ∈ 𝑉𝑘(𝑣′ ) , то можно построить новую путевую декомпозицию, где на ме сте 𝑉𝑖 будет находиться 𝑉𝑖′ = 𝑉𝑖 ∖ 𝑣, причём ширина путевой декомпозиции не увеличится. Доказательство окончено. Эти утверждения помогают выделить класс путевых декомпозиций, которые достаточно рассмотреть, чтобы найти путевую ширину графа. Да лее мы ограничимся только теми путевыми декомпозициями, к которым нельзя применить утверждения, указанные выше. Теперь сформулируем свойство путевой декомпозиции графов блочной структуры, на которой достигается путевая ширина. Такую путевую декомпозицию назовём ми нимальной. Утверждение 8.5. Для любой путевой декомпозиции 𝑉1 , . . . , 𝑉𝑛 графа блочной структуры 𝐺 верно, что если вершина 𝑎 ∈ 𝑉𝑘 , 𝑎 ∈ / 𝑉𝑘+1 , то в 𝑉𝑘 содержатся вершины 𝑎, 𝑏, 𝑐, которые находятся в одной ячейке. Д о к а з а т е л ь с т в о. Предположим противное. Рассмотрим первую вершину 𝑉𝑘 путевой декомпозиции, не содержащую такой тройки вершин исходного графа 𝑎, 𝑏, 𝑐. Из утверждений 8.1–8.4 следует, что существует вер шина 𝑎 такая, что 𝑎 ∈ 𝑉𝑘 , 𝑎 ∈ / 𝑉𝑘+1 , причём 𝑎 смежна с какой-то вершиной 𝑏 ∈ 𝑉𝑘 , при этом 𝑏 ∈ / 𝑉𝑘−1 , иначе бы мы могли удалить 𝑎 на предыдущем шаге. Так как 𝑎 ∈ / 𝑉𝑘+1 и степень любой вершины графа 𝐺 больше 1, то в исходном графе есть ребро (𝑐, 𝑎), а значит, 𝑐 ∈ 𝑉𝑙 , 𝑐 ∈ / 𝑉𝑘 , 𝑙 < 𝑘, так как иначе мы нашли искомую тройку вершин и получили противоречие. Рас смотрим ячейку вершин 𝑎, 𝑏, 𝑐, 𝑑. Так как 𝑐 ∈ / 𝑉𝑘 , то существует 𝑚 такое, что 𝑐, 𝑑 ∈ 𝑉𝑚 . Если 𝑑 ∈ 𝑉𝑘 , то получим противоречие, так как тогда мы нашли тройку 𝑎, 𝑏, 𝑑. Таким образом, существует 𝑟, когда 𝑏, 𝑑 ∈ 𝑉𝑟 , 𝑟 < 𝑘. Получаем, что из свойства 2 путевой декомпозиции 𝑎, 𝑏 ∈ 𝑉𝑘−1 . Тогда вер

42 шину 𝑎 можно удалить из 𝑉𝑘 , а мы рассматриваем путевые декомпозиции, к которым подобное действие уже нельзя применить. Таким образом, утвер ждение доказано. Теперь заметим, что если 𝑉1 , . . . , 𝑉𝑛 — минимальная путевая деком позиция, то и 𝑉𝑛 , . . . , 𝑉1 — тоже минимальная путевая декомпозиция, так как свойства путевой декомпозиции 1–3 по-прежнему выполняются, а мощ ность максимальной вершины декомпозиции не изменилась. Таким обра зом, утверждение 8.5 верно для 𝑉𝑛 , . . . , 𝑉1 , а значит, для 𝑉1 , . . . , 𝑉𝑛 верно следующее: Утверждение 8.6. Для любой путевой декомпозиции 𝑉1 , . . . , 𝑉𝑛 графа блочной структуры 𝐺 верно, что если вершина 𝑎 ∈ 𝑉𝑘 , 𝑎 ∈ / 𝑉𝑘−1 , то в 𝑉𝑘 содержатся вершины 𝑎, 𝑏, 𝑐, которые находятся в одной ячейке. Д о к а з а т е л ь с т в о. Применим к путевой декомпозиции 𝑉𝑛 , . . . , 𝑉1 утвер ждение 6, получим, что если вершина 𝑎 ∈ 𝑉𝑘+1 , 𝑎 ∈ / 𝑉𝑘 , то в 𝑉𝑘+1 содер жатся вершины 𝑎, 𝑏, 𝑐, которые находятся в одной ячейке. Теперь попробуем найти путевую ширина блока 𝐵 размера 𝑚 × 𝑛. Выделим общее свойство путевой декомпозиции блоков: Утверждение 8.7. Обозначим 𝑣𝑖,𝑗 , где 𝑗 ∈ 1 : 𝑛, — вершины 𝑖–ой строки блока 𝐵 размера 𝑚×𝑛. Тогда все вершины 𝑉𝑘 путевой декомпозиции графа, содержащие вершины 𝑖–ой строки, где 𝑖 ∈ 1 : 𝑚 образуют путь, то есть все описанные вершины путевой декомпозиции имеют последовательные номера. Д о к а з а т е л ь с т в о. Предположим противное, тогда существует такая па ра вершин 𝑣𝑖,𝑙 , 𝑣𝑖,𝑙+1 и такие числа 𝑝1 < 𝑝2 , что 𝑣𝑖,𝑙 ∈ 𝑉𝑝1 , 𝑣𝑖,𝑙 ∈ / 𝑉𝑘 при 𝑘 > 𝑝1 , а 𝑣𝑖,𝑙+1 ∈ 𝑉𝑝2 , 𝑣𝑖,𝑙+1 ∈ / 𝑉𝑠 при 𝑠 < 𝑝2 . Но по свойству путевой деком позиции вершины 𝑣𝑖,𝑙 , 𝑣𝑖,𝑙+1 принадлежат какой-то вершине 𝑉𝑘 , так в блоке 𝐵 эти вершины смежны.

43 Воспользовавшись этими утверждениями, мы можем доказать следу ющее: Утверждение 8.8. Если 𝐵 — блок размера 𝑚×𝑛, то 𝑝𝑤(𝐵) = min{𝑚, 𝑛}. Д о к а з а т е л ь с т в о. Покажем, что в путевой декомпозиции блока суще ствует вершина, содержащая вершин всех строк или столбцов блока. После этого воспользуемся утверждением 8.5 и получим, что 𝑝𝑤(𝐺) = min{𝑚, 𝑛}. Рассуждения будут похожи на нахождение поискового числа блока. Более того, пример путевой декомпозиции, на которой достигается путе вая ширина графа, строится с помощью стратегии очищения блока «слева направо» смешанного поиска: в 𝑉𝑖 попадают те вершины блока, в которых перед шагом 𝑖 и после него стоят игроки, а затем проводятся преобразова ния, описанные в утверждениях 8.1–8.4. По построению стратегии выпол няются свойства 1 и 3 путевой декомпозиции, а свойство верно, так как стратегия монотонная. Теперь покажем, что в путевой декомпозиции существует вершина, содержащая вершины всех строк или всех столбцов. Для это рассмотрим 𝑖 ⋃︀ номер 𝑖 такой, что 𝑉𝑘 содержит вершины всех строк или всех столбцов, 𝑘=1 а для любого 𝑗 < 𝑖 это неверно. Рассмотрим вершину 𝑉𝑖 . Пусть в ней нет вершин, например, строки 𝑗. Так как какая-то вершина этой строки уже была ранее, то по утверждению 8.7 любая вершина этой строки уже была в 𝑉𝑙 , где 𝑙 < 𝑖 (𝑙 для каждой вершины может быть своим). Но тогда суще 𝑖′ ⋃︀ ′ ствует 𝑖 < 𝑖, что 𝑉𝑘 содержит вершины всех столбцов, откуда получаем 𝑘=1 противоречие.

44 Заключение В работе найдены поисковые числа 𝑚𝑖𝑥𝑠(𝐺), 𝑐𝑚𝑖𝑥𝑠(𝐺), 𝑏𝑠(𝐺), 𝑐𝑏𝑠(𝐺) для следующих графов 𝐺 блочных структуры: Рис. 22. Граф-блок Рис. 23. Граф, полученный горизонтальной склейкой блоков 𝐵𝑖 размера 𝑚𝑖 × 𝑛𝑖 , где 𝑚 𝑖 6 𝑛𝑖 Рис. 24. Графы, полученные склейкой двух блоков Рис. 25. Граф, полученный удалением одного блока из другого

45 Рис. 26. «Граф–крест» Для графа–блока найдена путевая ширина и сформулированы неко торые свойства путевой декомпозиции графов блочной структуры.

46 Приложение А Рассматриваются графы из 4.1, полученные в результате склейки двух блоков (рисунок 27) c отождествлением угловых вершин. Для таких гра фов блочной структуры хочется найти некоторые поисковые числа. Вна чале попробуем найти 𝑚𝑖𝑥𝑠(𝐵), для этого строим для описанных графов оптимальную монотонную стратегию смешанного поиска. 𝑛 𝑙−1 𝑚 𝑘−1 Рис. 27 Теперь рассматриваем первый шаг поиска, когда появляется полно стью очищенный столбец или полностью очищенная строка: 1. Пусть нужная нам строка и столбец появились одновременно, а так как на предыдущем шаге ни очищенного столбца, ни очищенной стро ки не было, то и в строке, и в столбце есть игроки. Более того, рас сматриваемые строка и столбец пересекаются (иначе невозможно очи стить рёбра строки и столбца за один шаг). Тогда есть несколько вариантов: ∙ Очищена строка из 𝑛+𝑘−1 вершин и столбец из 𝑚+𝑙−1. В таком случае 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛+𝑘 −1, 𝑚+𝑙 −1}. Действительно, если очищен такой столбец, то в каждой строке должен стоять игрок, так как полностью очищенных строк без игроков ещё нет, откуда

47 получаем, что 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑙 − 1. Аналогично рассуждая, получаем, что 𝑚𝑖𝑥𝑠(𝐵) > 𝑛 + 𝑘 − 1. Тогда 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛 + 𝑘 − 1, 𝑚 + 𝑙 − 1}. ∙ Очищена строка из 𝑛 + 𝑘 − 1 вершин и столбец из 𝑚 вершин. Тогда в 𝑚 строках из 𝑛 + 𝑘 − 1 вершины есть игроки, то есть 𝑚𝑖𝑥𝑠(𝐵) > 𝑚. Таким же образом получаем, что 𝑚𝑖𝑥𝑠(𝐵) > 𝑛 + 𝑘 − 1, в итоге 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛 + 𝑘 − 1, 𝑚}. ∙ Очищена строка из 𝑛 вершин и столбец из 𝑚 + 𝑙 − 1. Рассуж дая так же, как и в предыдущем пункте, делаем вывод, что 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛, 𝑚 + 𝑙 − 1}. Три полученных неравенства позволяют сделать оценку, что для стра тегий такого типа 𝑚𝑖𝑥𝑠(𝐵) > min{max{𝑛+𝑘−1, 𝑚+𝑙−1}, max{𝑛, 𝑚+ 𝑙 − 1}, max{𝑛 + 𝑘 − 1, 𝑚}} > min{𝑛 + 𝑘 − 1, 𝑚 + 𝑙 − 1}. 2. Очищена только строка из 𝑛 + 𝑘 − 1 вершин или только столбец из 𝑚 + 𝑙 − 1. Тогда 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑙 − 1 или, соответственно, 𝑚𝑖𝑥𝑠(𝐵) > 𝑛 + 𝑘 − 1. 3. Очищен только столбец из 𝑚 вершин. Если при этом в каждом столб це стоит игрок, тогда 𝑚𝑖𝑥𝑠(𝐵) > 𝑛+𝑘 −1. Если есть столбец без игро ков, все рёбра которого загрязнены, тогда в каждой строке, с которой пересекается столбец, стоит игрок, то есть выставлено как минимум 𝑚 игроков. Эти строки из 𝑛 + 𝑘 − 1 вершины будем называть «длин ными», а из 𝑛 — «короткими». Если в каждой строке стоит игрок, то 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑙 − 1, иначе есть полностью загрязнённая строка из 𝑛 вершин. Пусть после появления такого столбца на каждом шаге оптимальной стратегии в «длинных» строках всегда есть хотя бы по одному игроку, пока есть полностью загрязнённая «короткая» стро ка. Далее рассмотрим, сколько нужно дополнительно игроков, что

48 избавиться от таких строк. Для этого необходимо, чтобы в каждой такой строке стоял игрок, тогда снова оценка 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑙 − 1, иначе всегда есть строка без игроков. Рассмотрим тогда шаг, когда в графе осталась только одна гряз ная «короткая» строка без игроков. Если есть полностью очищен ная строка, то количество игроков в «коротких» строках 𝑛, тогда 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑛. В противном случае в остальных строках есть иг роки. Если в строке были очищенные рёбра и один игрок, то мы не можем его снять со строки в силу монотонности стратегии, значит, ли бо была строка с двумя игроками, тогда 𝑚𝑖𝑥𝑠(𝐵) > 𝑚+𝑙−1, либо мы сняли игрока с вершины строки без очищенных рёбер и снова полу чили такую строку. Таким образом, 𝑚𝑖𝑥𝑠(𝐵) > min{𝑚+𝑙 −1, 𝑚+𝑛}. Теперь посмотрим, когда в «длинных» строках может быть меньше 𝑚 игроков, то есть, когда мы можем убрать игрока оттуда при наличии полностью загрязнённой «короткой» строки. В силу монотонности стратегии это возможно только и только тогда, когда есть очищен ная строка. Теперь рассмотрим шаг, на котором появилась первая очищенная «длинная» строка. С одной стороны, стоит хотя бы 𝑚 иг роков в длинных строках, с другой — стоят игроки в 𝑛 «длинных» столбцах, то есть 𝑚𝑖𝑥𝑠(𝐵) > max{𝑚, 𝑛}. Таким образом, можно сказать, что 𝑚𝑖𝑥𝑠(𝐵) > min{min{𝑚 + 𝑙 − 1, 𝑚 + 𝑛}, max{𝑚, 𝑛}, 𝑚 + 𝑙 − 1, 𝑛 + 𝑘 − 1} 𝑚𝑖𝑥𝑠(𝐵) > min{max{𝑚, 𝑛}, 𝑚 + 𝑙 − 1, 𝑛 + 𝑘 − 1}. 4. Очищена только строка из 𝑛 вершин. Аналогично рассуждая, полу чаем, что 𝑚𝑖𝑥𝑠(𝐵) > min{max{𝑚, 𝑛}, 𝑚 + 𝑙 − 1, 𝑛 + 𝑘 − 1}.

49 Обобщая полученные неравенства, видим окончательную оценку 𝑚𝑖𝑥𝑠(𝐵) > min{max{𝑚, 𝑛}, 𝑚 + 𝑙 − 1, 𝑛 + 𝑘 − 1}, которую можно переписать в следующем виде 𝑚𝑖𝑥𝑠(𝐵) > min{𝑚, 𝑛 + 𝑘 − 1}, 𝑚 > 𝑛, 𝑚𝑖𝑥𝑠(𝐵) > min{𝑛, 𝑚 + 𝑙 − 1}, 𝑛 > 𝑚 .

50 Приложение B Ищется 𝑐𝑚𝑖𝑥𝑠(𝐵) для графов 𝐵 блочной структуры, являющихся ре зультатом склейки двух блоков без отождествления угловых вершин. 𝑛 𝑙−1 𝑚 𝑘−1 𝑝−1 Рис. 28 Рассматривается оптимальная монотонная стратегия смешанного по иска и первый шаг, когда появляется полностью очищенный столбец или полностью очищенная строка, пусть 𝑘 6 𝑝, то есть в рассуждениях мы при выборе между 𝑝 и 𝑘 выбираем 𝑘: 1. Пусть нужная нам строка и столбец появились одновременно, а так как на предыдущем шаге ни очищенного столбца, ни очищенной стро ки не было, то и в строке, и в столбце есть игроки. Более того, рас сматриваемые строка и столбец пересекаются. Тогда есть несколько вариантов (так же, как и в склейке выше): ∙ Очищена строка из 𝑛 + 𝑝 + 𝑘 − 2 вершин и столбец из 𝑚 + 𝑙 − 1. В таком случае 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛 + 𝑘 + 𝑝 − 2, 𝑚 + 𝑙 − 1}. Действительно, если очищен такой столбец, то в каждой строке должен стоять игрок, так как полностью очищенных строк без игроков ещё нет, откуда получаем, что 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑙 − 1. Аналогично рассуждая, получаем, что 𝑚𝑖𝑥𝑠(𝐵) > 𝑛 + 𝑝 + 𝑘 − 2. Тогда 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛 + 𝑝 + 𝑘 − 2, 𝑚 + 𝑙 − 1}.

51 ∙ Очищена строка из 𝑛 + 𝑝 + 𝑘 − 2 вершин и столбец из 𝑚 вершин. Тогда в 𝑚 строках из 𝑛 + 2𝑘 − 2 вершины есть игроки, то есть 𝑚𝑖𝑥𝑠(𝐵) > 𝑚. Таким же образом получаем, что 𝑚𝑖𝑥𝑠(𝐵) > 𝑛 + 2𝑘 − 2, в итоге 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛 + 𝑝 + 𝑘 − 2, 𝑚}. ∙ Очищена строка из 𝑛 вершин и столбец из 𝑚 + 𝑙 − 1. Рассуж дая так же, как и в предыдущем пункте, делаем вывод, что 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛, 𝑚 + 𝑙 − 1}. Три полученных неравенства позволяют сделать оценку, что для стра тегий такого типа 𝑚𝑖𝑥𝑠(𝐵) > min{max{𝑛+𝑝+𝑘−2, 𝑚+𝑙−1}, max{𝑛, 𝑚+ 𝑙 − 1}, max{𝑛 + 𝑝 + 𝑘 − 2, 𝑚}}. Заметим, что в таком случае стратегия заведомо не будет блочной. 2. Очищена только строка из 𝑛 + 𝑝 + 𝑘 − 2 вершины или только столбец из 𝑚 + 𝑙 − 1. Тогда 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑙 − 1 или 𝑚𝑖𝑥𝑠(𝐵) > 𝑛 + 𝑝 + 𝑘 − 2. 3. Очищен только столбец из 𝑚 вершин, тогда либо в каждом столбце стоит игрок и 𝑚𝑖𝑥𝑠(𝐵) > 𝑛 + 𝑝 + 𝑘 − 2, либо есть столбец без игроков, всё рёбра которого загрязнены, откуда получаем, что в каждой стро ке, с которой пересекается столбец, стоит игрок, то есть выставлено как минимум 𝑚 игроков. Эти строки из 𝑛+𝑝+𝑘−2 вершины будем на зывать «длинными», а из 𝑛 — «короткими». Если в каждой строке сто ит игрок, то 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑙 − 1, иначе есть полностью загрязнённая строка из 𝑛 вершин. Пусть после появления такого столбца на каждом шаге оптимальной стратегии в «длинных» строках всегда есть хотя бы по одному игроку, пока есть полностью загрязнённая «короткая» строка. Далее оценим, сколько нужно дополнительно игроков, чтобы избавиться от таких строк. Для этого необходимо, чтобы в каждой такой строке стоял игрок, тогда снова оценка 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑙 − 1, иначе всегда есть строка без игроков.

52 Рассмотрим тогда шаг, когда в графе осталась только одна гряз ная «короткая» строка без игроков. Если есть полностью очищен ная строка, то количество игроков в «коротких» строках 𝑛, тогда 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑛. В противном случае в остальных строках есть иг роки. Если в строке были очищенные рёбра и один игрок, то мы не можем его снять со строки в силу монотонности стратегии, значит, ли бо была строка с двумя игроками, тогда 𝑚𝑖𝑥𝑠(𝐵) > 𝑚+𝑙−1, либо мы сняли игрока с вершины строки без очищенных рёбер и снова полу чили такую строку. Таким образом, 𝑚𝑖𝑥𝑠(𝐵) > min{𝑚+𝑙 −1, 𝑚+𝑛}. Теперь посмотрим, когда в «длинных» строках может быть меньше 𝑚 игроков, то есть, когда мы можем убрать игрока с этих вершин при наличии полностью загрязнённой «короткой строки». В силу мо нотонности стратегии это возможно только и только тогда, когда есть очищенная «длинная» строка. Давайте рассмотрим шаг, на котором появилась первая очищенная «длинная» строка. Заметим, что в каж дом из 𝑛 длинных столбцов стоит хотя бы один игрок. Если в каждом столбце стоит игрок, тогда 𝑚𝑖𝑥𝑠(𝐵) > 𝑛+𝑝+𝑘−2. Пусть есть очищен ные столбцы без игроков. Если все очищенные столбцы находятся по одну сторону от длинных столбцов, то 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛 + 𝑘 − 1, 𝑚} (𝑛 в «длинных» столбцах и 𝑘 − 1 в «коротких» столбцах по другую сторону). В противном случае, есть очищенные столбцы по обе сторо ны от «длинных» столбцов. Рассмотрим теперь первый момент, когда по обе стороны есть очищенные столбцы. Если с одной из сторон есть грязный «короткий» столбец, то оценка 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛 + 𝑚, 𝑚}, так как между столбцами в каждой строке для защиты от загряз нения должен быть хотя бы один игрок. Иначе есть точно с одной стороны от «длинных» столбцов 𝑘 − 1 столбец с хотя бы одним игро ком, откуда оценка 𝑚𝑖𝑥𝑠(𝐵) > max{𝑛 + 𝑘 − 1, 𝑚}.

53 Итак, получили, что 𝑚𝑖𝑥𝑠(𝐵) > min{max{𝑛 + 𝑚, 𝑚}, max{𝑛 + 𝑘 − 1, 𝑚}, 𝑛 + 𝑝 + 𝑘 − 2, 𝑚 + 𝑙 − 1, 𝑚 + 𝑛} = min{𝑛 + 𝑚, max{𝑛 + 𝑘 − 1, 𝑚}, 𝑛 + 𝑝 + 𝑘 − 2, 𝑚 + 𝑙 − 1}. 4. Очищена только «короткая» строка. Если в каждой строке стоит иг рок, то 𝑚𝑖𝑥𝑠(𝐵) > 𝑚 + 𝑙 − 1, иначе есть строка без игроков и очи щенных рёбер, то есть в «длинных» столбцах есть 𝑛 игроков. Далее, оценим количество игроков, если все «короткие» столбцы очищаются новыми игроками, отличными от 𝑛 уже выставленных. Изначально у нас нет очищенных «коротких» столбцов. Рассмотрим первый мо мент, когда появляется первый очищенный столбец. Снова, либо в каждом столбце стоит игрок, тогда 𝑚𝑖𝑥𝑠(𝐵) > 𝑛 + 𝑘 + 𝑝 − 2, либо есть полностью грязный столбец без игроков. В случае выполнения второго посмотрим, как расположены очищенный и полностью гряз ный столбец. Если они по одну сторону от «длинных» столбцов, то между ними в каждой строке стоит игрок, тогда 𝑚𝑖𝑥𝑠(𝐵) > 𝑛 + 𝑚, если по разные, то в 𝑘 − 1 «коротком» столбце есть игроки, то есть всего игроков не меньше 𝑛 + 𝑘 − 1. Так как по другую сторону от длинных столбцов есть полностью грязный столбец, то общее коли чество игроков в силу монотонности оптимальной стратегии хотя бы 𝑚, ведь очищенный столбец не теряется. Тогда в этом случае оценка 𝑚𝑖𝑥𝑠(𝐵) > max{𝑚, 𝑛 + 𝑘 − 1}. Аналогично предыдущему пункту, можно показать, что для того, что бы с одной стороны от «длинных» столбцов не было полностью за грязнённых столбцов, нужен заведомо min{𝑘 − 1, 𝑚} игроков. Теперь посмотрим, когда можно убрать с «длинного» столбца одно го из игроков. Понятно, что для этого столбец должен быть полно стью очищен. Рассмотрим шаг, когда с полностью очищенного столб ца снимается последний игрок. Если на этом шаге полностью неочи

54 щенный столбец находится от него только с одной стороны, тогда 𝑚𝑖𝑥𝑠(𝐵) > max{𝑚, 𝑛 + 𝑘 − 1} (𝑚 игроков должны защищать от за грязнения, а 𝑘 − 1 необходимы, чтобы в одном из блоков не было пол ностью загрязнённых столбцов, так как в таком случае либо в каждом столбце есть игрок с одной сторон, либо есть очищенный). Если же такие столбцы находятся с двух сторон, то 𝑚𝑖𝑥𝑠(𝐵) > max{2𝑚, 𝑛} (𝑛 заведомо стоят, а 2𝑚 защищают от загрязнения, с каждой стороны по 𝑚). В итоге, имеет место неравенство 𝑚𝑖𝑥𝑠(𝐵) > min{𝑛+𝑚, max{𝑛+𝑘−1, 𝑚}, 𝑛+𝑝+𝑘−2, 𝑚+𝑙−1, max{2𝑚, 𝑛}}.

55 Литература 1. Абрамовская Т.В., Петров Н.Н. Теория гарантированного поиска на графах // Дифференциальные уравнения и процессы управления. 2012. № 2. С. 9–65. 2. Головач П.А. Об одном топологическом инварианте в задачах пресле дования // Дифференциальные уравнения. 1989. T. 2, № 6. С. 923–929. 3. Петров Н.Н. Задачи преследования при отсутствии информации об убегающем // Дифференциальные уравнения. 1982. Т. 18, № 8. С. 1345–1352. 4. Parsons T.D. Pursuit–evasion in a graph // Theory and applications of graphs. Berlin: Springer. 1978. P. 426–441. 5. Kirousis L.M., Papadimitriou C.H. Searching and pebbling // Theoretical Computer Science. 1986. V. 47, № 1. P. 205–218. 6. Takahashi A., Ueno S., Kajitani Y. Mixed searching and proper-path-width // Theoretical Computer Science. 1995. V. 137, № 2. P. 253–268. 7. Barriere L., Fraigniaud P., Santoro N., Thilikos D.M. Connected and Internal Graph Searching // In 29th Workshop on Graph Theoretic Concepts (WG). Springer-Verlag. 2003. P. 34–45. 8. Boting Yang Strong-mixed Searching and Pathwidth // Journal of Combinatorial Optimization. 2007. V. 13, № 1. P. 47–59.

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв