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

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

Условие

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


Решение

  Оценка. Рассмотрим граф, вершинами которого являются зажимы, а рёбрами – сопротивления. Заметим, что между вершинами A и B не может быть пути, состоящего менее чем из девяти рёбер (иначе при коротком замыкании всех рёбер этого пути у нас получалось бы короткое замыкание цепи). Кроме того, для любых девяти рёбер существует путь из A в B, не проходящий через эти рёбра. Следовательно, по теореме Менгера, существует не менее 10 попарно не пересекающихся (по рёбрам) путей из A в B. Так как в каждом из этих путей не менее 10 рёбер, то всего рёбер не менее 100.
  Пример цепи со 100 сопротивлениями – это 10 попарно непересекающихся путей длины 10 из вершины A в вершину B.


Ответ

100 сопротивлений.

Замечания

  Теорема Менгера. Если в графе G c двумя отмеченными вершинами A и B для любых k рёбер существует путь из A в B, не проходящий ни по одному из этих рёбер, то существует набор из  k + 1  попарно непересекающихся (по рёбрам) путей из A в B.
  Доказательство см., например, здесь.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 21
Год 1958
вариант
Класс 9
Тур 2
задача
Номер 5

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

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