Олимпиадная задача по теории графов: электрическая решётка 3×3 и 5×5 – минимальное число измерений (Шаповалов А. В.)

  Нетрудно убедиться в том, что если перегорели только провода, выходящие из фиксированного узла, то между любыми двумя другими узлами ток проходит. Поэтому каждый узел должен быть задействован в процессе измерений, то есть число измерений не может быть меньше половины числа узлов (8 в случае а) и 18 в случае б)).

  Покажем, что этого числа проверок достаточно. Для этого определенным образом разобьём все узлы на пары (узлы в паре пометим одинаковыми буквами) и для каждой проверим, что ток проходит между узлами этой пары.   а) "Линия тока"  A–A  (B–B)  очевидно пересекается с линиями  C–C  и  D–D  (см. шаг 1). Таким образом, все узлы, помеченные буквами от A до D, связаны проводами (принадлежат одной компоненте). Остальные узлы также принадлежат этой компоненте – например линия тока  E–E  проходит либо через A, либо через C (см. шаг 2).

  б) Здесь потребуется три шага (см. рис.).   На первом шаге все проверенные узлы принадлежат одной компоненте по теоремео пересечении ломаных. На втором шаге линия тока обязана пройти через один из узлов, принадлежащих компоненте, поскольку один из проверяемых узлов всегда окружен уже проверенными узлами. На третьем шаге проверяем узлы, симметричные относительно диагоналиEEFGHH(каждая такая линия тока диагональ, очевидно, пересекает).

Ответ задачи отсутствует