Книга: Золотой билет

Изоморфизм графов

Изоморфизм графов

В Королевстве насчитывается несколько сотен фанатов «Блейд Квеста» – массовой многопользовательской ролевой онлайн-игры. Как и в других играх подобного плана, участники здесь получают новую личность, или аватар; каждый исполняет роль определенного персонажа и общается с другими персонажами, за которыми тоже стоят реальные жители Королевства. В виртуальном мире дружеские связи сохраняются: те, кто дружат в жизни, становятся друзьями и в игре, а те, кто враждуют, заново проникаются взаимной неприязнью.

Джон, Изабель, Кевин, Лаура, Молли и Нэнси очень любят играть в «Блейд Квест».

Рис. 4.10. Любители «Блейд Квеста»

Их персонажей зовут Акрис, Лэмбо, Криард, Де Гарольд, Хрхрхр и Вирус, но кто под каким именем скрывается – неизвестно: эта информация пользователям игры недоступна, и они могут видеть только схему дружеских связей между персонажами.

Рис. 4.11. Аватары в «Блейд Квесте»

Проанализировав обе схемы, Лаура отправила остальным игрокам сообщение от имени своего аватара: «Я знаю, кто ты!» А вы уже догадались, кто есть кто?

Схемы будут соответствовать друг другу лишь в том случае, если Изабель – это Хрхрхр, Джон – Де Гарольд, Кевин – Криард, Лаура – Лэмбо, Молли – Акрис, а Нэнси – Вирус. Например, «реальная» Молли дружит с Лаурой и Нэнси, а ее аватар Акрис – с Лэмбо и Вирусом.

Установить, соответствуют ли друг другу подобные схемы, – это все равно что определить, изоморфны два графа или нет. Некоторые схемы сопоставить нельзя, другие – можно, иногда даже несколькими способами. Проблема изоморфизма графов лежит в NP, поскольку, зная, кто есть кто, можно легко проверить соответствие дружеских связей.

Вопрос о том, относится ли проблема изоморфизма также и к классу P, до сих пор открыт; никто пока не придумал хороший алгоритм, который всегда находил бы искомое соответствие в случае, если оно действительно есть. Мы также не знаем, является ли эта проблема NP-полной, хотя, по мнению ученых, некоторые признаки косвенно указывают на то, что не является. Изоморфизм графов стоит в ряду немногочисленных задач, занимающих некое промежуточное положение: они вроде бы труднее, чем задачи из P, но легче, чем задачи NP-полные, вроде поиска гамильтонова пути или максимального разреза.

Оглавление книги