Теория тупиков

Перед тем, как читать это прочитайте пожалуйста основные определения.

Обозначения.

Q - пустое множество.

Часть обозначений содержится в теории циклов.

ТЕОРИЯ ТУПИКОВ.

Пусть игровое поле, - множество всех допустимых не полных ходов. Пусть , а - множество всех неполных ходов, которые не уничтожают ни одной клетки из множества . Если мы говорим, что неприкосновенно, но для нас допустимыми неполными ходами являются только элементы из множества .

Положим - все клетки из множества , которые невозможно уничтожить никаким ходом , принадлежащим . Пусть .

Теорема 1. такой, что полностью уничтожает .

Доказательство. Если . Утверждение очевидно.

Если , то $ тупик в G, не лежащий в . Положим . Далее по индукции: . Множества не пересекаются, поэтому среди них лишь конечное число непустых, так как поле конечно. Пусть - минимальный индекс такой, что Все последующие тоже пусты.

Лемма. Клетка . Тогда удаляет .

Доказательство. Очевидно, что если , то можно сначала удалить , потом , а потом . Пусть теперь наоборот – известно, что можно удалить ходом . Пусть расставляет стенок , после чего клетка удалена. Если . Далее – по индукции, докажем, что . Пусть множество клеток, которые удаляют стенки . Тогда по предположению индукции .

Допустим , тогда . Поскольку тупик в (а иначе её нельзя было бы удалить), и , то тем более тупик в , а поскольку - удаляет, то .

Теперь доказать теорему 1 просто – так как любую клетку из можно удалить, то . Удаляя последовательно можно удалить всё . Более того, так как . Значит

Определение. Пусть неприкосновенно и . Введём на и структуру графа. {Вершины }={клетки }, {рёбра в }={открытые стенки внутри }. {Вершины }={клетки }, {рёбра в }={открытые стенки внутри }и { корни в }={открытые стенки между и }. Клетки из , соединённые с клетками из ,будут называться вершинами с корнем.

Теорема 2. Если , удаляющий , то:

1)  каждая клетка из , имеет не более одного корня.

2)  каждая связная компонента в имеет не более одной клетки с корнем.

3)  не имеет циклов.

Доказательство. Проводится единообразно для всех трёх случаев.

1)  Пусть клеткаимеет 2 корня с и. Положим

2)  Пусть - путь между и , которые соединены с клетками и. Положим

3)  Пусть -цикл в .

Докажем, что . Для очевидно.

Пусть. Поскольку все стенки внутри - открыты, то не содержит тупиков . Поэтому (смотри теорему1), значит удалить нельзя. Но , значит, тоже полностью не удалить никаким ходом из .

Теорема 3. Пусть - 2 графа, построенных как указано выше. - подграф, дерево с корнем. Тогда , который удаляет только W

Доказательство. Всякое дерево (# - длина дерева) с корнем имеет висячую вершину, отличную от корня. Для W эта вершина - тупик. Удаляем его. После каждого удаления от W останется снова дерево. Если - то это корень. У него одна стенка открыта. Значит он тупик. Его можно удалить. Если , снова находим висячую вершину и так далее.

Теорема 4. Пусть- разложение на связные компоненты. - связно . Тогда не содержит корня.

Доказательство. Заметим, что компонент можно удалить в любом случае (смотри теорему 3). Положим . Пусть неприкосновенно. В соответствии с этим введём структуру графа на , и на .

Пусть - разложение на связные компоненты. имеет корень с , причём ровно один. В самом деле, пусть . Так как W - связно, то существует путь . Пусть - минимальный индекс такой, что путь не пересекается с . Тогда - - корень. Теперь докажем единственность. Пусть -2 корня в с . Они соединены с клетками и. Так каки - связны, то $ пути . Но тогда -цикл в . По теореме 1 можно удалить за 1 ход, по теореме 2 -не имеет циклов тоже не имеет циклов. Получили противоречие. Единственность доказана.

Если не содержит корня с , то каждая компонента имеет всего 1 корень и может быть удалена по теореме 3. Если же, например, имеет корень с , то тогда имеет два корня с и, согласно теореме 2, не может быть удалено.

Пусть - ход, удаляющий последовательно, следуя теореме 3. Докажем, что . В самом деле - связно и каждая клетка из имеет соседа из у неё осталась незакрытая стенкавсе клетки из ещё целы . По построению удаляет всё, кроме .

Теорема 5. Пусть в ходе игры поле превратилось в поле. Тогда

Доказательство. Нужно доказать, что . Пусть, напротив, в позиции ход уничтожающий . Выкинем из те стенки, которые закрыты в и докажем что получившийся ход - допустим и уничтожает . Если все стенки закрыты, то - уничтожена. Противоречие с тем, что . Пусть . Пусть закрыты ходом , прочие - закрыты по условию, поэтому тупик, уничтожаемый стенкой ещё жив и является тупиком тоже можно закрыть. В конце концов закроет .

Определение. Пусть - общее число клеток поля . Пусть оба игрока придерживаются минимаксной стратегии и обеспечивают себе соответственнои клеток. Разность называется минимаксным выигрышем 1Р. Величина зависит только от позиции. Следовательно, можно писать .

Теорема 6. Если ход оптимален и закрывает хотя бы одну стенку внутри , тогда удаляет полностью.

Доказательство. Пусть . Тогда только стенка внутри . Пусть - где - неполный ход, удаляющий . Пусть - позиция, возникающая после хода. Пусть не удаляет множество . Пусть - позиция, возникающая после . Тогда 2Р может закрыть множество(так как по теореме 5 ), получить позицию и выиграть ещё очков. Итого выигрыш 1Р составит: . Но после хода 2Р может выиграть лишь очков. Итого выигрыш 1Р составит:, что на больше чем после хода. Но оптимален, удаляется полностью.

Теорема 7. Пусть ход - оптимален и не затрагивает ни одной стенки из . Пусть- позиция после хода . Тогда возможны 2 варианта:

а) - дерево с корнем длины 2. (- корень в )

б) -линейное дерево без корня длины 4 (- середина )

При этом если в существует неизолированная вершина с корнем, то вариант б) невозможен.

Доказательство. Пусть стенка разделяет клетки и . Тогда возможны 2 варианта:

а) (с точностью до переименования) и .

б)

Рассмотрим вариант а). Так как полный ход, тоне закрывает тупиков. Следовательно, не тупик. Следовательно, соседи. В самом деле, если бы , тоимела бы два корня и тогда не лежала бы в (теорема 2). Пусть - связная компонента в , содержащая . Положим . Тогда по теореме 4 , так как не имеет корня, - связно и . Поэтому существует неполный ход, который уничтожает всё, кроме . Рассмотрим ход . После него 2Р не может не затронуть .Следовательно по теореме 6 он обязан удалитьи закрыть оптимально одну стенку в. Итого 1Р имеет: . Пусть ход , кроме не уничтожает множество . Тогда 2Р может уничтожить и сходить оптимально в . Итого 1Р имеет: , что на меньше, чем после хода . Но ход оптимален.

б) Докажем, что. Так как и не тупики в, то у них есть соседи - . Если связная компонента, содержащаяи , имеет 2 корня, что невозможно по теореме 2 (+теорема 1). Пусть. Пусть не уничтожает множество . Тогда 2Р может удалить и сходить оптимально в .

Покажем, что если содержит неизолированный корень, то ситуация б) невозможна. Пусть - корень в , - его сосед. Пусть W - связная компонента, содержащая. Так как-связно, не имеет корня, то по теореме 4 , где - удаляет всё, кроме. Согласно пункту а) после хода , где - стенка междуи . 1Р может себе обеспечитьочков. Противоречие с оптимальностью .Поэтому если ситуация б) возникла, то не содержало неизолированного корня. Поэтому и , так как иначе - неизолированный корень. Пусть W - связная компонента, содержащая. Множество не может иметь корня, так как он был бы не изолирован, что невозможно. Поэтому по теореме 4 -удаляет всё, кроме . Рассмотрим ход . 2Р не может не закрыть стенку внутри по теореме 6 он вынужден забрать клетки и сделать оптимальный ход в . Итого 1Р имеет: С другой стороны, еслине закрывает , то , так как . Поэтому . Таким образом, всё утверждение доказано.

Следствие 1. Пусть . Чтобы сделать оптимальный ход, первому игроку следует:

Пункт 1. Проверить, есть ли в неизолированный корень, с соседом . Если есть - удалить и выбрать:

а) либо закрыть стенку между и .

б) либо забрать и сходить оптимально в. Если нет - смотри пункт 2.

Пункт 2. Проверить, содержит ли линейный подграф длины. Если есть - удалить и выбрать:

а) либо закрыть стенку между и.

б) либо забратьи сходить оптимально в.

Если нет - удалитьи сходить оптимально в.

Доказательство. Пусть содержит, где- корень, - его сосед. Пустьсвязная компонента , содержащая. Тогдане имеет корня неполный ход , удаляющий. Так какнеполный ход, то он не закрывает ни одной стенки внутри . Пустьоптимальный для ход. Еслизакрывает стенкувнутри, то устроен так: удаляет множество , не трогая стенок внутри, а потом закрывает стенку. В этом случае ход можно дополнить закрытием стенок , где - стенка между и , - стенка между и . Ход эквивалентен ходу, поскольку закрывает ровно те же стенки. Поэтому, если оптимален, то ход - тоже оптимален и может быть найден по алгоритму, данному в условии. Пусть не закрывает ни одной стенки внутри. Тогда посколькуобладает не изолированным корнем, то по теореме 7 удаляет (где и- могут быть отличны оти ) и перекрывает стенку междуи. При этом игроку №1 обеспечен выигрыш . Рассмотрим ход . После него 2Р должен забрать и сходить оптимально в . Итого 1Р имеет: ходтоже оптимален и может быть найден по этому алгоритму. Пусть теперь не содержит неизолированного корня, зато содержит линейный подграф , содержащийся в компоненте не имеет корня, иначе он был бы неизолирован. Поэтому существует неполный ход, удаляющий. Пустьлюбой такой ход. Посколькунеполон, он не закрывает стенок внутри . Пусть оптимальный ход. Предположим закрывает стенку внутри, следовательно по теореме 6 устроен так: сначала он удаляет , не задевая ни одной стенки из, а потом ставит стенку. Положим , где - стенка между и. Он закрывает те же стенки, что и, поэтому тоже оптимален и может быть найден согласно приведённому алгоритму. Пусть теперьне закрывает ни одной стенки из. Тогда по теореме 7, так как не имеет не изолированного корня, то удаляет, где - линейный подграф в и ставит стенку между и. Рассмотрим ход . Тогда 2Р не может не закрыть стенку из, следовательно по теореме 6 обязан удалить клеткии сходить оптимально в. Итого 1Р имеет: . Следовательно ходоптимален и находится по данному алгоритму. Пусть теперьне имеет ни изолированного корня, ни линейного подграфа длины 4. Тогда, согласно теореме 7 оптимальный ход обязан закрывать какую-нибудь стенку внутри. По теореме 6 оптимальный ход удаляет полностью. Именно это и советует делать приведённый алгоритм.

Теорема 8. Пусть , где - это либо: а) , где - корень, а - его сосед: б) - линейный граф длины 4. Пусть - минимаксный выигрыш 1Р при условии, что первым ходом он удаляет . Тогда .

Доказательство. Согласно теореме 1 1Р имеет 2 варианта:

1)  Удалятьи ходить оптимально в .

2)  Перерезать корень в ( разделить пополам )

В случае 1) Он имеет.

В случае 2) 2Р не может не закрыть стенки из . Следовательно, по теореме 6 он удаляети ходит оптимально в, тогда 1Р имеет . Поскольку 1Р играет по минимаксу, то .

Следствие 2. Если в условиях теоремы 8 , то удалять - оптимально.