сам я дискретку не учил по этому ХЗ что это за теорема, по идеии разчет должен быть какойто математический на матрици смежности может кто знает или сталкивался с подобными вопросами?
оффтоп, конечно, но не могу удержаться: зачем обходить туннели, если можно блокировать все возможные выходы и подождать, а для пущей эффективности и забавы - закидать шумовыми и дымовыми шашками)
sambd минимальное количество полицейских S, гарантирующих поимку беглеца Это довольно известная задача с большим количеством литературы по ней. К сожалению она относится к NP-hard. Начинать можно с Википедии (http://en.wikipedia.org/wiki/Pursuit-evasion) Кстати если не ошибаюсь, то в первой версии поста у тебя была немного другая формулировка - "перекрыть путь", а не поймать. В этом случае речь идет о вычисление "vertex-connectivity" графа.
ну если перекрыть то можно и поймать, хотя и есть разница но нужно найти минимум ... ок спасибо, а вот на русском есть какая нить литература? так как я чтото не нашел ничего полезно ... хотя может и плохо искал
sambd ну если перекрыть то можно и поймать Совсем не обязательно. Сравни с игрой в шашки, где легко перекрыть дамке определенный путь, но крайне сложно ее поймать. а вот на русском есть какая нить литература? Чего не знаю, того не знаю..
sambd Fomin F.V. Petrov N.N. , Pursuit-evasion and search problems on graphs // Congr. Numer. 1996. Vol. 122. P. 47-58. Fomin F.V., Golovach P.A., Petrov N.N., Search problems on 1-skeletons of regular polyhedrons //Games Theory and Appl. Vol. III. N.Y.: Nova Science Publisher, 1997. P. 27-37. http://tex.imm.uran.ru/tom6/pet/
Stiver не самое лучшее сравнение. -------------------------------- а, вообще, эта задача интересная: она относится к особенностям боевых действий в замкнутых помещениях. её решение очень сильно зависит от того, на кого охота идёт. если на каждом перекрёстке ставить датчики движения иль более активные системы, то проход беглеца станет невозможным (если он не вооружён). при наличие оружия попытка поймать живым может привести к потерям среди охотников.
