Question

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

Answer 1

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