|
|
 |
Условие
Между зажимами 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.
Доказательство см., например, здесь.
