Иерархия голубей?
Я шел, хотя проблемы на теории графов, отправленной профессором Ericksson от моей alma mater и, столкнулись с этим довольно уникальным вопросом о голубях и их врожденной тенденции сформировать иерархии. Вопрос идет следующим образом:
Каждый раз, когда группы голубей собираются, они инстинктивно устанавливают иерархию. Для любой пары голубей один голубь всегда клюет другой, отгоняя его от еды или потенциальных помощников. Та же пара голубей всегда выбирает ту же иерархию, даже после лет разделения, независимо от того, что другие голуби вокруг. Удивительно, полная иерархия может содержать циклы — например, голубь голубь куч B, который клюет голубя C, который клюет голубя A.
Докажите, что любое конечное множество голубей может быть расположено подряд слева направо так, чтобы каждый голубь сразу клевал голубя с его левой стороны от него.
Так как это - вопрос на Теории графов, первые вещи, которые пришли в мою голову, которая является этим, просто прося топологический вид графики отношений (отношения, являющиеся иерархией). Что сделало, это немного более сложное было тем, что могут быть циклические отношения между голубями. Если у нас есть циклическая зависимость следующим образом:
A-> B-> C-> A
куда кучи на B, B кучи на C и C возвращаются и клюют на A
Если мы представляем его в пути, предложенном проблемой, у нас есть что-то следующим образом: C B A
Но вышеупомянутое данное упорядочивание строки не включает в иерархию между C и A.
У меня была другая идея решить его математической индукцией, где основной случай для двух голубей, расположенных согласно их иерархии, предполагая, что расположение иерархии допустимо для n голубей и затем доказательства его, чтобы быть верным для n+1 голубей.
Я не уверен, спускаюсь ли я по неправильной дорожке здесь. Некоторое понимание того, как я должен анализировать эту проблему, будет полезно.
Спасибо
2 ответа
Я бы доказал, что действительно с помощью индукции (a> b означает a peacks b):
- для k = 2, очевидно, выполняется
- пусть для k = n всегда требуется порядок, давайте докажем, что он существует для n +1. Выберите и закажите n голубей (A1> A2 ...> An) из заданного n + 1. И пусть C - (n + 1) -й голубь.
Если C клюет A1, то его можно добавить в начало «строки» и доказать утверждение. Если A1 клюет C, тогда давайте сравним C с A2 - если C клюет A2, тогда он может быть вставлен между A1 и A2, и утверждение выполняется. Если нет - повторите этот процесс сравнения до последней пары - A (n-1) и An, по ходу процесса мы предполагаем, что A (n-1)> C. Если C> An, то C может быть вставлен между A (n-1). ) и An, если нет - его можно вставить в конец «строки».
qed
P.S. Обратите внимание, что «циклы клевания» не обязательно существуют - если мы присваиваем голубям номер от 1 до n и предполагаем, что голубь клюет другого, если его число больше, то мы, очевидно, можем расположить их по очереди, но не по кругу, чтобы каждый голубь клюет своего левого соседа.
П.П.С. Это доказательство также дает алгоритм построения требуемого порядка.
Рассматривали ли вы возможность построения направленного графа и поиска гамильтонова пути, который посещает каждую точку (голубя) один раз? Гамильтонов путь должен выявить последовательность - это не доказательство, однако. Просто решение.