|
Название: Граф Монте-Кристо. Отправлено: Sirion от Январь 25, 2012, 05:11:16 Граф Монте-Кристо - это такой граф, рёберная структура которого нам неизвестна. Мы видим только его вершины.
Для исследования этого графа нам дан специальный прибор - щекотометр. Он работает следующим образом: мы подключаем к каждой вершине графа по детектору, а затем щекочем одну из вершин (назовём ей Щ). После этого каждый из детекторов, подключенных к остальным вершинам, выдаёт нам величину самого длинного элементарного пути от вершины, к которой он подключен, до вершины Щ (либо 0, если пути между этими двумя вершинами не существует). Затем мы можем пощекотать другую вершину, и так далее, пока нам не надоест. Можем ли мы с помощью щекотометра определить структуру графа Монте-Кристо? Название: Re: Граф Монте-Кристо. Отправлено: iPhonograph от Январь 25, 2012, 13:06:05 нет, ня
Показать скрытый текст Название: Re: Граф Монте-Кристо. Отправлено: Sirion от Январь 25, 2012, 13:18:26 Таки да, не получается. Но нам в помощь послан ещё один прибор - самогонный инвертор. Он работает на самогоне и, соответственно своему названию, способен временно инвертировать граф Монте-Кристо, соединяя рёбрами те вершины, которые не были соединены, и разъединяя те, которые были.
Можем ли мы узнать структуру графа с помощью этих двух приборов? Название: Re: Граф Монте-Кристо. Отправлено: iPhonograph от Январь 25, 2012, 15:37:25 |