Странные жуки (задача)

сегодня в 13:09

Профессор Хоппер исследует сексуальное поведение жуков одного редкого вида. Профессор предполагает, что данный вид содержит особей двух полов, и сексуальные контакты совершаются только между особями противоположного пола. Пол каждого жука определить не представляется возможным. К счастью, у каждого жука на спине написан уникальный номер, и все сексуальные контакты между наблюдаемыми особями были зафиксированы.

Профессору Хопперу нужна Ваша помощь: по результатам наблюдений необходимо сказать, есть ли среди жуков гомосексуальные пары, или их существование считается недоказанным.



Решение:

Входные данные описывают граф связей между жуками.

Попробуем раскрасить вершины графа в два цвета. Если не удается сделать это так, чтобы любые две соседние вершины были разных цветов, «странные» пары гарантированно существуют.

Более формально, такие пары существуют при наличии в графе циклов нечетной длины. Если же циклов нечетной длины нет, граф двудольный. Таким образом, задача сводится к классическому алгоритму – проверка графа на двудольность.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends: 'You Say What You Like, Because They Like What You Say' - http://www.medialens.org/index.php/alerts/alert-archive/alerts-2013/731-you-say-what-you-like-because-they-like-what-you-say.html