ПРОБЛЕМА СВЯЗАННОСТИ В НЕКОТОРЫХ ЗАДАЧАХ ПОИСКА НА ГРАФАХ

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

В данной работе рассматривается задача поиска с дискретным временем мобильного объекта на графе. На связном неориентированном графе G находится невидимый объект, перемещения которого невозможно предсказать. К его поимке стремится множество игроков S, которые также могут передвигаться на G. Условия, при которых искомый объект пойман игроками, а также некоторые другие параметры задачи, задают вид поиска. Тем не менее, в каждой задаче гарантированного поиска требуется найти минимальное количество игроков, которые ловят объект независимо от его действий — эта величина называется поисковое число графа G.
В обзоре [1] Т. В. Абрамовской и Н.Н. Петрова приводится следующая интерпретация задачи поиска на графах. Пусть в пещере, состоящей из лазов и ходов, потерялся спелеолог. У спасателей есть карта пещеры в виде графа, но перемещения исследователя непредсказуемы, а передвигаться он может с любой скоростью. Более того, следует предположить, что он действует себе во вред и самостоятельно не может выбраться из пещеры. Таким образом, спелеолог никак не может помочь спасателям, которым нужен алгоритм действий, гарантирующий, что хоть один из команды спасателей наткнётся на блуждающего спелеолога. П. А. Головач показал в [2], что задача о поиске спелеолога сводится к дискретной задаче поиска на графе.
Часто дискретную задачу поиска удобно формулировать как задачу очищения графа. Будем говорить, что ребро очищено, если на нём гарантированно нет объекта, иначе ребро загрязнено. Считается, что изначально все рёбра графа загрязнены, а игроки стремятся обеспечить момент, когда все рёбра графа единовременно очищены. Далее в работе будем придерживаться именно такой терминологии.
Для описания возможных действий игроков введём следующие шаги поиска:
1. поставить игрока в вершину графа;
2. игрок скользит вдоль ребра из одного из концов, где он ранее находился;
3. снять игрока с вершины.
Очищенное ребро е = (u,v) защищено от загрязнения в данный момент, если для каждой из вершин и, v верно, что в вершине стоит игрок или все рёбра, инцидентные ей, очищены. Иными словами, ребро повторно загрязняется, если в вершинах на пути от него до загрязнённого ребра нет ни одного игрока. Можно считать, что в начальный момент на графе нет ни одного игрока, а дальше выполняется последовательность шагов поиска, которая называется стратегией поиска. Стратегию называют монотонной (monotone), если при её использовании не допускается повторное загрязнение рёбер. Если на каждом шаге множество очищенных рёбер индуцирует связный подграф, то такая стратегия является связной. Использование связной стратегии моделирует ситуацию, когда игрокам необходимо поддерживать безопасный канал связи. Например, спасатели в пещере могут посылать сообщения друг другу и быть уверенными, что сообщение не будет перехвачено спелеологом.
Существуют несколько видов поиска, которые различаются условиями очищения рёбер и множеством допустимых стратегий. В стандартном поиске разрешены все шаги поиска, перечисленные выше, а чтобы очистить ребро е = (u,v), игроку необходимо проскользить вдоль ребра е от одного его конца к другому. Стандартный поиск был впервые поставлен в [3] Н.Н. Петровым и в [4] Т.Д. Парсонсом. Поисковое число стандартного поиска обозначается s(G). Если потребовать, чтобы все стратегии в таком поиске были связными, то получим связный поиск (connected search), поисковое число которого обозначается cs(G).
Поиск, в котором запрещён шаг 2, а ребро е = (u,v) считается очищенным, если для в вершинах u,v стоят игроки, называется вершинным поиском (node search), тогда ns(G) - поисковое число в данном случае. Вершинный поиск был поставлен в [5] Кироусисом и Пападимитриу, там же была показана связь с «игрой в камни».
В смешанном поиске (mixed search), сформулированном Такахаши, Уено и Каджитани в [6], разрешены все шаги поиска, а ребро считается очищенным, если оно очищено по условиям вершинного или стандартного поисков, mixs(G) — поисковое число смешанного поиска.
В случае, когда множество очищенных вершин смешанного поиска индуцирует связный подграф на каждом шаге, говорят, что поиск связный смешанный (connected mixed search), а его поисковое число обозначают cmixs(G). Для каждого поиска можно определить монотонную стратегию и поисковые числа mmixs(G), mns(G), mcmixs(G). Нас интересуют стандартный, смешанный (mixed) и связный смешанный (connected mixed search) поиски. В следующей главе будет введён блочный поиск для специального класса графов, сформированного на основе примера в статье [7], среди авторов которой — Д.М. Тиликос и Н. Санторо. Для некоторых классов блочных графов будут найдены поисковые числа интересующих нас поисков и построены оптимальные стратегии.

Купить