Читать статья по математике: "Обучение решению математических задач с помощью графов" Страница 5

(Назад) (Cкачать работу)

П.Т.З. 7. "Наибольшее и наименьшее число элементов".

Город имеет в плане вид прямоугольника, разбитого на клетки: n улиц параллельны друг другу, m других пересекаются под прямым углом. На улицах города – но не на перекрестках – стоят милиционеры. Каждый милиционер сообщает номер проходящего мимо него автомобиля, направление его движения и время, когда он проехал. Какое наименьшее число милиционеров нужно расставить на улицах, чтобы по их показаниям можно было однозначно восстановить путь любого автомобиля, едущего по замкнутому маршруту (маршрут не проходит по одному и тому же участку улицы дважды)?

Решение:

Наименьшее число милиционеров равно (m-1)(n-1).

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

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

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

Похожие работы