Клевать порядок голубей?

Question

Я собирался, хотя проблемы по теории графов, опубликованной Проф. Эрикссон из моей alma-mater и наткнулся на этот довольно уникальный вопрос о голубях и их врожденной склонности к формированию ордеров клевания. Вопрос звучит так:

Всякий раз, когда собираются группы голубей, они инстинктивно устанавливают клевание порядок. Для любой пары голубей один голубь всегда клюет другого, за рулем это далеко от еды или потенциальных партнеров. Одна и та же пара голубей всегда выбирает тот же порядок клевания, даже после нескольких лет разлуки, неважно какие другие голуби вокруг. Удивительно, но общий клевать порядок может содержать циклы - например, голубь A клюет голубь B, который клюет голубь C, который клюет голубя A.

Докажите, что любой конечный набор голубей можно расположить в ряд слева направо прямо так, что каждый голубь клюет Голубь сразу слева от него.

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

A-> B-> C-> A

где A клюет на B, B клюет на C, а C возвращается и клюет на A

Если мы представим это способом, предложенным проблемой, у нас будет что-то следующее: C B A

Но приведенный выше порядок строк не учитывает порядок раскладки между C и A.

У меня была другая идея решить ее математической индукцией, когда базовый случай для двух голубей, расположенных в соответствии с их порядком клевания, предполагая, что порядок клевания действует для n голубей, а затем доказал, что это верно для n + 1 голубей .

Я не уверен, что пойду не по тому пути. Некоторые идеи о том, как я должен анализировать эту проблему, будут полезны.

Спасибо

Answer 1

Я бы доказал, что действительно с использованием индукции (a> b означает пики b):

1. для k = 2, очевидно, имеет место
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, если нет - его можно вставить в конец «строки».

ч.т.д.

PS Обратите внимание, что "циклы клевания" не обязательно существуют - если мы присваиваем голубю число от 1 до n и предполагаем, что голубь клюет другого, если его число больше, то мы, очевидно, можем упорядочить их в строке, но не по кругу, чтобы каждый голубь клевал своего левого соседа.

P.P.S. Это доказательство также дает алгоритм для построения необходимого порядка.

Answer 2

Рассматривали ли вы создание ориентированного графа, а затем ищите гамильтонов путь, который посещает каждую точку (голубя) один раз?Путь гамильтониана должен раскрыть последовательность - это не доказательство.Просто решение.