Периоды $\varphi$-графов

Связный граф с $n\geq3$ вершинами, полученный из контура $C_n$ путём переориентации некоторых его дуг, называется многоугольным графом. Рассмотрим некоторую биекцию $\varphi$ между множеством стоков и множеством источников многоугольного графа $G$. Присоединим к $G$ все дуги вида $v\varphi(v)$, где $v$ – сток. Полученный сильносвязный граф будем называть $\phi$-графом. Рассматривая последовательность различных матриц $A,A^2,A^3,\dots$ (степеней булевой матрицы $A$), заметим, что эта последовательность конечна. Если $A^m$ – её последний элемент, то $A^{m+1}=A^l$ для некоторого $l\leq m$. Число $\mathrm{ind}(A)=l-1$ называется индексом матрицы $A$, а число $\mathrm p(A)=((m+1)-l)$ – её периодом. Для графа $G$ с матрицей смежности $A$ положим $\mathrm{ind}(G)=\mathrm{ind}(A)$ и $\mathrm p(G)=\mathrm p(A)$ (индекс и период графа). Вычислены значения периодов всех неизоморфных $var\phi$-графов с числом вершин до 9. Рассчитаны максимальные периоды $\varphi$-графов с числом вершин до 17. Доказана теорема, позволяющая вычислить период любого $\varphi$-графа. Найдено значение максимального периода $n$-вершинных $\varphi$-графов при чётном $n$ и дана оценка максимального периода при нечётном $n$.