Предыдущая страница реферата | 1  2  3  4  5  6

Если милиционеры расставлены требуемым образом, то вся сетка улиц распадается на какое-то число k кусков, не содержащих замкнутых маршрутов (циклов), - иначе найдется цикл, по которому можно проехать не будучи замененным ни одним милиционером. Если оставшийся кусок сетки содержит р перекрестков то в нем содержится ровно р – 1 отрезков улиц. Так как перекрестков всего m n, то число отрезков, на которых нет милиционеров, равно mn – k. Общее число отрезков улиц равно 2mn – m – n. Таким образом, число занятых отрезков равно

mn – m – n + k > (n – 1)(n – 1).

Пример нужной расстановки (n – 1)(n – 1) милиционеров показан на рисунке

Скачали данный реферат: Панков, Neelov, Углов, Junge, Якименко, Брежнев.
Последние просмотренные рефераты на тему: диплом государственного образца, диплом разработка, бумага реферат, сочинение 5 класс.





Предыдущая страница реферата | 1  2  3  4  5  6