Граф Монте-Кристо.

[Sirion]

Граф Монте-Кристо - это такой граф, рёберная структура которого нам неизвестна. Мы видим только его вершины.

Для исследования этого графа нам дан специальный прибор - щекотометр. Он работает следующим образом: мы подключаем к каждой вершине графа по детектору, а затем щекочем одну из вершин (назовём ей Щ). После этого каждый из детекторов, подключенных к остальным вершинам, выдаёт нам величину самого длинного элементарного пути от вершины, к которой он подключен, до вершины Щ (либо 0, если пути между этими двумя вершинами не существует). Затем мы можем пощекотать другую вершину, и так далее, пока нам не надоест.

Можем ли мы с помощью щекотометра определить структуру графа Монте-Кристо?

[iPhonograph]

нет, ня
Показать скрытый текст

если полный граф на 5 вершинах потеряет одно ребро, прибор этого не заметит

[Sirion]

Таки да, не получается. Но нам в помощь послан ещё один прибор - самогонный инвертор. Он работает на самогоне и, соответственно своему названию, способен временно инвертировать граф Монте-Кристо, соединяя рёбрами те вершины, которые не были соединены, и разъединяя те, которые были.

Можем ли мы узнать структуру графа с помощью этих двух приборов?

[iPhonograph]

нет, ня

Показать скрытый текст

Если в алёграфе потерять одно ребро, то приборы это не обнаружат.
Алёграф - это граф на девяти вершинах 1,2,...9 с рёбрами (i,j) для всех пар цифр i и j, лежащих в одном ряду или в одном столбце на клавиатуре телефона.