ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116272
Темы:    [ Четность и нечетность ]
[ Подсчет двумя способами ]
[ Индукция (прочее) ]
[ Теория графов (прочее) ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Шень А.Х.

В стране 100 городов и несколько дорог. Каждая дорога соединяет два каких-то города, дороги не пересекаются. Из каждого города можно добраться до любого другого, двигаясь по дорогам. Докажите, что можно объявить несколько дорог главными так, чтобы из каждого города выходило нечётное число главных дорог.


Решение 1

  Разобьём все города на пары и соединим каждую пару своим маршрутом. Посчитаем для каждой дороги кратность: число маршрутов, в которые она вошла. Сумма кратностей для выходящих из города дорог нечётна: "свой" маршрут даёт вклад 1, а остальные – 0 или 2. Значит, из каждого города выходит нечётное число дорог нечётной кратности. Их и объявим главными.


Решение 2

  Рассмотрим граф городов и дорог и докажем по индукции, что факт верен для любого связного графа с чётным числом вершин.
  База. При  n = 1  утверждение очевидно.
  Шаг индукции. Пусть утверждение доказано для всех графов с меньших чем 2n (чётным) числом вершин. Возьмём связный граф на 2n вершинах и выделим в нём остовное дерево. В этом дереве возьмём любую висячую вершину А и рассмотрим вершину B, к которой она прикреплена. Если к вершине B прикреплено нечётное число висячих вершин, объявим главными все рёбра, ведущие из B в висячие вершины, удалим B и эти висячие вершины вместе со всеми выходящими из них рёбрами и применим предположение индукции к оставшемуся графу. В противном случае применим предположение индукции к графу, который получается удалением всех висячих вершин, прикреплённых к B, а потом дополнительно объявим главными все рёбра, ведущие из B в висячие вершины.

Замечания

5 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2010/2011
Номер 32
вариант
Вариант весенний тур, базовый вариант, 10-11 класс
Задача
Номер 5

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .