Изменения

Перейти к: навигация, поиск

Примеры сведения к задачам поиска потока

157 байт убрано, 22:42, 25 декабря 2016
м
Нет описания правки
</table>}}
</includeonly>
[[Файл:Monster.png|right|Пример поля]] [[Файл:MonsterSolution.png|right|Решение текущего примера]] 
Сразу скажем, что выбраться за пределы поля эквивалентно тому, что Минотавр может дойти до какой-либо крайней клетки.
=== Решение и доказательство корректности ===
Покажем то, что минимальное {{Теорема|statement=Минимальное количество клеток, которое нужно закрасить, равно максимальному количеству клеточно-непересекающихся путей из позиции Минотавра до крайних клеток поля. |proof=Очевидно, что ответ не больше, чем количество всех путей от Минотавра до крайних клеток. Сделаем ещё более строгое неравенство: ответ не больше, чем максимальное количество клеточно-непересекающихся путей, т.к. если взять какие-нибудь <tex>2</tex> пересекающихся пути и закрасить клетку в позиции, где они пересекаются, то блокируется выход за пределы поля сразу по <tex>2</tex> этим путям. С другой стороны, если закрасить клетку на каком-то из путей, то блокируется только этот путь, т.к. были взяты клеточно-непересекающиеся пути. Значит, ответ не меньше, чем количество таких путей. В итоге получаем то, что и хотели доказать.}}
=== Переход к сети ===
50
правок

Навигация