22 Граф преобразования конечного множества.

Определение 22.1:
Пусть $\Omega$ - конечное множество, $\varphi:\Omega\to\Omega$, $$E:=\{(a,\varphi(a))\mid{a}\in\Omega\}\subset\Omega\times\Omega.$$ Тогда ориентированный граф $\Gamma(\varphi):=(\Omega,E)$ называется графом преобразования $\varphi$.

Замечание 22.1:
Ориентированный граф является графом преобразования множества своих вершин тогда и только тогда, когда из каждой вершины выходит одно ребро.

Пример 22.1:
Пусть $\Omega=\overline{1,7}$, $\varphi=\begin{pmatrix}1,2,3,4,5,6,7 \\ 7,3,4,5,3,6,4\end{pmatrix}$, тогда граф $\Gamma(\varphi)$ будет выглядеть следующим образом

7	$\to$	4	$\gets$	3	$\gets$	2	$\gets$	1
		$\uparrow$	$\nearrow$
		5

и единичный цикл в точке $6$.

Определение 22.2:
Вершина $a$ графа $\Gamma(\varphi)$ называется

1. циклической или регулярной, если существует $t\geq1$ такое, что $\varphi^t(a)=a$;
2. точкой подхода, если для любого $t\geq1$ $\varphi^t(a)\neq{a}$;
3. начальной точкой если для любого $x\in\Omega$ $\varphi(x)\neq{a}$.

Замечание 22.2:

1. Регулярные вершины и точки подхода образуют разбиение множества вершин графа преобразования.
2. Начальная вершина является точкой подхода.

Определение 22.3:
Циклом длины $t\geq1$ называется подграф вида

$a_1$	$\to$	$a_2$	$\to$	$\cdots$	$\to$	$a_k$
$\uparrow$						$\downarrow$
$a_t$	$\gets$	$a_{t-1}$	$\gets$	$\cdots$	$\gets$	$a_{k+1}$

Подходом длины $l$ называется подграф вида

$a_1$

$\to$

$a_2$

$\to$

$\cdots$

$\to$

$a_{l-1}$

$\to$

$a_l$

где

1. $a_0$ - начальная вершина,
2. $a_1$ - $a_{l-1}$ - точки подхода,
3. $a_l$ - регулярная вершина.

Определение 22.4:
Пусть $\varphi:\Omega\to\Omega$, тогда вершины $a,b\in\Omega$, графа $\Gamma(\varphi)$ называются связными, если существуют $i,j\in\mathbb{N}_0$ такие, что $\varphi^i(a)=\varphi^j(b)$.
Если вершины $a$ и $b$ связны, то будем обозначать $a\sim{b}$.
Если все вершины графа связны, то будем говорить, что граф связен.

Замечание 22.3:
Несложно видеть, что отношение связности на множестве вершин $\Omega$ является отношением эквивалентности.

• рефлексивность Так как $\varphi(a)=\varphi(a)$, то $a\sim{a}$ ($i=j=1$);
• симметричность Если $a\sim{b}$, то существуют числа $i,j\in\mathbb{N}_0$ такие, что $\varphi^i(a)=\varphi^j(b)$, тогда $\varphi^i(b)=\varphi^i(a)$, то есть $b\sim{a}$.
• транзитивность Если $\varphi^i(a)=\varphi^j(b)$ и $\varphi^k(b)=\varphi^s(c)$, где б. о. о. будем считать, что $k\geq{j}$, тогда $\varphi^{i+k-j}(a)=\varphi^k(b)=\varphi^s(c)$.

Теорема 22.1:
Граф преобразования конечного множества является объединением попарно не персекающихся подграфов, каждый из которых является циклом с подходами.

Доказательство:

Так как отношение связности является отношением эквивалентности, то оно разбивает множество $\Omega$ на не пересекающиеся классы эквивалентности. $$\Omega=\Omega_1\sqcup\ldots\sqcup\Omega_s.$$ Так как для любого $a\in\Omega$ $\varphi(a)\sim{a}$, то для любого $r\in\overline{1,s}$ $\varphi(\Omega_r)\subset\Omega_r$. Тогда для любого $r\in\overline{1,s}$ можно рассмотреть отображение $\varphi_r:=\varphi|_{\Omega_r}$. Так как классы не пересекаются, то вершины в них входящие связаны ребрами только друг с другом. Подграф состоящий из вершин $\Omega_r$ и вершин их соединяющих есть $\Gamma(\varphi_r)$ и $$\Gamma(\varphi)=\Gamma(\varphi_1)\sqcup\ldots\sqcup\Gamma(\varphi_s).$$ Остается доказать, что $\Gamma(\varphi_r)$ - это цикл с подходами.
Пусть $c\in\Omega_r$, тогда ввиду конечности $\Omega_r$ последовательность элементов $$c,\varphi(c),\ldots,\varphi^i(c),\ldots$$ периодическая. То есть вершина $c$ лежит либо на цикле, либо на подходе к нему. Остается доказать, что в графе $\Gamma(\varphi_r)$ только один цикл.
Пусть $a,b\in\Omega_r$ две циклические вершины графа $\Gamma(\varphi_r)$. Тогда существует $t\in\mathbb{N}$ такое, что $\varphi^t(a)=a$ и ввиду связности множества вершин $\Omega_r$ существуют $i,j\in\mathbb{N}_0$ такие, что $\varphi^i(a)=\varphi^j(b)$. Существует $k\in\mathbb{N}$ такое, что $kt\geq{i}$, следовательно $$a=\varphi^{kt}(a)=\varphi^{kt-i}(\varphi^i(a))=\varphi^{kt-i}(\varphi^j(b))=\varphi^{kt-i+j}(b),$$ то есть $a$ и $b$ лежат на одном цикле.

previous contents