Деревья по кругу.

Эндоморфизмы и орбиты, небольшая теория для левой руки.

Abstract: orbits of an endomorphism of a finite set are represented as connected components of a suitably defined graph. Their structure is surprisingly simple: a collection of disjoint trees rooted on the vertices of a unique cycle.

Пусть \(f:X\rightarrow X\), произвольное отображение множества \(X\) в себя, т.е. эндоморфизм \(X\). Известно, что если \(f\) является автоморфизмом (т.е. биекцией), то оно разбивает \(X\) на непересекающиеся орбиты. Каждая орбита состоит из точек
$$\ldots f^{-2}(x), f^{-1}(x), x, f(x), f^2(x), \ldots$$
для некоторого \(x\), где \(f^n\) означает \(n\)-кратное применение \(f\) (\(f^0(x) = x\), \(f^{n+1}(x) = f(f^n(x))\), \(f^{-n}(x) = (f^{-1})^n(x)\)). Если \(X\) конечно, то всякая орбита является циклом, состоящим из конечного числа точек, и для некоторого \(n\) будет \(x = f^{n}(x)\). В случае бесконечного \(X\) могут существовать орбиты, состоящие из бесконечного (счетного) числа различных точек.

Как выглядят аналоги орбит для произвольных эндоморфизмов конечных множеств?

Обычное определение орбиты не дает интересного обобщения на эндоморфизмы, т.к. получающися множества пересекаются. Вместо этого, дадим следующее определение:

Множество \(M\), \(M \subseteq X\), \(f\)-замкнуто, если \(x \in M\equiv f(x)\in M\), т.е. \(f\)-замкнутое множество содержит вместе с каждой точкой \(x\) ее образ \(f(x)\) и все прообразы \(f^{-1}(x)\).

Очевидно, что

Пересечение \(f\)-замкнутых множеств \(M\) и \(N\) — \(f\)-замкнуто:

	\(x\in M \cap N\)
\(\equiv\)	{ определение пересечения множеств }
	\(x\in M \wedge x\in N\)
\(\equiv\)	{ определение \(f\)-замкнутости}
	\(f(x)\in M \wedge f(x)\in N\)
\(\equiv\)	{ определение пересечения множеств }
	\(f(x)\in M \cap N\)

Орбитой называется непустое минимальное \(f\)-замкнутое множество, т.е. \(f\)-замкнутое множество не имеющее собственных \(f\)-замкнутых подмножеств.

Для автоморфизмов это определение совпадает со стандартным.

Очевидно, что орбиты не пересекаются (иначе их пересечение было бы их \(f\)-замкнутым подмножеством, в нарушение требования минимальности). Кроме этого, всякая точка принадлежит хотя бы одному \(f\)-замкнутому множеству, например всему \(X\). Это значит, что для всякой точки определено пересечение всех \(f\)-замкнутых множеств, содержащих эту точку. Такое пересечение будет орбитой. Следовательно \(X\) разбивается на непересекающиеся орбиты.

Граф

Отображению \(f\) можно сопоставить ориентированный граф (который останется безымянным, как единственный, подлежащий рассмотрению), с множеством вершин \(X\) и множеством дуг \(\{(x, f(x)) | x \in X \}\).

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

Мы будет также рассматривать неориентированную версию этого же графа (в которой забыты направление дуг) и будет в этом случае говорить о "ребрах" (а не дугах), неориентированнх путях и неориентированных циклах.

Все пути и циклы предполагаются простыми, т.е. проходящими через данную дугу или вершину не более одного раза.

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

Рассмотрим дугу \(a\) из вершины \(x\) в вершину \(y\) (т.е. предположим, что \(y = f(x)\)). Для соответствующего ребра \(a\) определим

$$\sigma(x, a) = +1$$
$$\sigma(y, a) = -1$$

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

Если ребро \(a\) соединяет вершины \(x\) и \(y\), то \(\sigma(x, a) + \sigma(y, a) = 0\) (свойство (0))

Если вершина \(x\) соединяет разные ребра \(a\) и \(b\), то \(\sigma(x, a) + \sigma(x, b) \leq 0\) (свойство (1))

Теперь мы может доказать простую лемму:

Если \(a_0, ... a_n\) неориентированный путь между вершинами \(x\) и \(y\), то \(\sigma(x, a_0) + \sigma(y, a_n) > -2\), т.е. крайние ребра пути не могут быть одновременно входящими.

Индукция по длине пути.
\(n = 1\). Немедленно по свойству (0).
\(n = k + 1\). Пусть \(a_0, ... a_k\) неориентированный путь между вершинами \(x\) и \(z\), а ребро \(a_{k+1}\) соединяет \(z\) и \(y\).

	\(\sigma(x, a_0) + \sigma(y, a_{k+1})\)
\(=\)	\(\sigma(x, a_0) + \sigma(y, a_{k+1}) + \sigma(z, a_k) - \sigma(z, a_k)\)
\(>\)	{ по гипотезе индукции \(\sigma(x, a_0) + \sigma(z, a_k) > -2\) }
	\(-2 + \sigma(y, a_{k+1}) - \sigma(z, a_k)\)
\(=\)	\(-2 + \sigma(y, a_{k+1}) - \sigma(z, a_k) + \sigma(z, a_{k+1}) - \sigma(z, a_{k+1})\)
\(\geq\)	{ по свойству (1) \(\sigma(z, a_k) + \sigma(z, a_{k+1}) \leq 0\)}
	\(-2 + \sigma(y, a_{k+1}) + \sigma(z, a_{k+1})\)
\(=\)	{ по свойству (0) \(\sigma(y, a_{k+1}) + \sigma(z, a_{k+1}) = 0\)}
	\(-2\)

Циклы

Рассмотрим ориентированные циклы в нашем графе. Для всякой вершины \(x\), лежащей на ориентированном цикле из \(n\) вершин \((x_i | 0 \leq i < n)\), имеем \(f^n(x) = x\). В частности, циклы длины 1 это в точности стационарные точки \(f\). Обратно, множество вершин всякого ориентированного цикла длины \(n\) можно описать как $$\{f^i(x) | 0 \leq i < n\} = \{f^i(x) | 0 \leq i\} = \{x, f(x), \ldots, f^{n-1}(x)\}$$ где за \(x\) можно принять любую вершину цикла.

При помощи функции \(\sigma\) легко доказывается и следующий полезный факт:

Всякий цикл ориентирован.

Рассмотрим неориентированный цикл из ребер \(a_i\), соединяющих вершины \(x_i\) и \(x_{i+1}\), где \(0 \leq i < n\) и \(i+1\) понимается по модулю \(n\). Составим сумму $$S = \sum_{0 \leq i < n}\sigma(x_i, a_i) + \sigma(x_{i+1}, a_i)$$ По свойству (0), каждое слагаемое этой суммы равно 0. Перегруппировав слагаемые, получим $$S = \sum_{0 \leq i < n}\sigma(x_i, a_i) + \sigma(x_i, a_{i-1}) = 0$$ По свойству (1) (применимому, т.к. цикл простой), каждое слагаемое здесь не больше нуля. Так как сумма равно 0, то каждое слагаемое равно 0: $$\sigma(x_i, a_i) + \sigma(x_i, a_{i-1}) = 0$$ Т.е., в каждую вершину цикла входит и выходит одна дуга, то есть цикл ориентирован.

С этого момента не будет различать ориентированные и неориентированные циклы.

Просто доказывается следующее свойство:

Циклы имеющие общую вершину совпадают.

Действительно, пусть циклы \(\{f^i(x) | 0 \leq i\}\) и \(\{f^i(y) | 0 \leq i\}\) имеют общую точку. Т.е. \(f^p(x) = f^q(y)\). Для произвольной точки первого цикла имеем

	\(f^i(x)\)
\(=\)	{ для произвольного \(d\), так как \(f^n(x) = x\) }
	\(f^{i+ d\cdot n}(x)\)
\(=\)	{ выберем \(d\) так, что \(i+ d\cdot n > p\) }
	\(f^{p + \Delta}(x)\)
\(=\)	\(f^\Delta(f^p(x))\)
\(=\)	{ \(f^p(x) = f^q(y)\) }
	\(f^{q +\Delta}(y) \in \{f^i(y) | 0 \leq i\}\)

Аналогично, всякая точка второго цикла принадлежит первому.

Отсюда следует интересное свойство:

Всякий неориентированный путь \(P\) между вершинами \(x\) и \(y\), лежащими на циклах, полностью лежит в некотором цикле.

Применим индукцию по длине \(P\).

\(n = 0\). Очевидно.
\(n = k + 1\). По лемме, хотя бы одно из крайних ребер \(P\) — исходящее. Пусть это ребро, исходящее из точки \(x\). Это ребро соединяет \(x\) с вершиной \(f(x)\), также лежащей на цикле. Таким образом, путь \(f(x), \ldots, y\) длины \(k\) соединяет точки, лежащие на циклах и следовательно (по гипотезе индукции), полностью лежит в некотором цикле. Этот цикл имеет общую точку \(f(x)\) с циклом в котором лежит точка \(x\) и, следовательно, эти циклы совпадают. Таким образом, путь \(x, \ldots, y\) полностью лежит в цикле.

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

Настало время использовать конечность \(X\).

Всякая орбита конечного множества содержит цикл.

Действительно, орбита \(M\) не пуста по определению. Выберем в ней точку \(x\) и рассмотрим функцию \(\phi : \mathbb{N} \rightarrow M\), \(\phi(n) = f^n(x)\). Т.к. \(M\) конечно, \(\phi\) не может быть однозначным отображением и существуют натуральные числа \(p\) и \(q\), такие что \(f^p(x) = f^q(x)\). Следовательно, \(f^p(x)\) лежит на цикле длины не большей \(|p - q|\).

Зафиксируем орбиту и ее единственный цикл.

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

Очевидно, что

• это множество не содержит других точек цикла, так как по свойству, установленному выше, всякий путь соединяющий точки цикла лежит в этом цикле, а ребра цикла были удалены;
  
• это множество не содержит циклов, т.к. цикл в компоненте единственный и его ребра удалены.

Итак, компонента является связным (по построению) графом без циклов, т.е. деревом, пересекающимся с циклом ровно в одной точке, которую можно выбрать за корень. Каждой точке цикла соответствует такое дерево. Деревья, соответствующие разным точкам цикла не пересекаются (как компоненты связности).

Докажем, что всякая точка \(x\) орбиты принадлежит такому дереву. Для этого достаточно показать, что \(x\) можно соединить с некоторой вершиной цикла неориентированным путем не проходящим через ребра цикла (т.е. неориентированным путем пролегающем в прореженном графе) Т.к. орбита связна, то существует неориентированный путь \(P\), соединяющий \(x\) с вершиной цикла. Если этот путь содержит ребро цикла \(a\), то он распадается в композицию путей \(P = P_0\cdot a\cdot Q_0\). \(P_0\) соединяет \(x\) с одной из точек, соединенных ребром \(a\), т.е. с некоторой точкой на цикле. Повторяя процесс этот процесс необходимое число раз мы получим путь \(P_n\), который не содержит ребер цикла (возможно вообще не содержит ребер).

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

Под действием последовательного применения преобразования \(f\), всякая точка сначала движется по дереву, в направлении корня, сливаясь при этом с другими точками этого дерева. После достижения корня, точка начинает двигаться по циклу.

Бесконечность

В случае бесконечного множества, орбита может быть устроена несколько сложнее.

Вместо циклов, придется рассмотреть траектории, определенные, как последовательности точек \((f^n(x) | n > 0)\). Цикл является частным случаем траектории.

Так же как и в случае с циклами, неориентированный путь, соединяющий точки на траекториях, сам лежит в некоторой траектории. Однако траектории имеющие общую точку не обязаны совпадать. К счастью, имеется более слабое, но полезное свойство: если пересечение траекторий непусто, то оно является траекторией.

Как и в конечном случае, рассмотрим компоненту связности. Возьмем пересечение всех содержащихся в ней траекторий. Предположим, что оно непусто. В таком случае, это перечение есть траектория. Образуем прореженный граф, удалив все ребра траектории-пересечения. Так как мы удалили как минимум по ребру из каждой траектории, то в рассматриваемой компоненте связности не осталось ни одной траектории, в частности, ни одного цикла. Неориентированная компонента связности прореженного графа является таким образом, связным ацикличным графом, т.е. деревом.

Итак, в случае непустого пересечения траекторий, орбита распадается на непересекающиеся деревья, корни которых закреплены на траектории-пересечении.

Остается рассмотреть случай пустого пересечения. Пример такой ситуации доставляет функция

$$f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$$

$$f(x, y) = (\lfloor x/2^y\rfloor\cdot 2^y, y+1)$$

\(f\) строит бесконечное "дерево", начиная с листьев, склеивая \(2^y\) смежных узлов уровня \(y\) в один узел уровня \(y+1\).

Очевидно, что все множество \(\mathbb{N}\times\mathbb{N}\) является орбитой. Каждая траектория через конечное число шагов достигает оси \(x = 0\), следовательно все траектории пересекаются, но их пересечение пусто.

Однако здесь бессоница отступает и авторы прекращают дозволенные речи.