Периоды p-графов | Прикладная дискретная математика. 2018. № 41. DOI: 10.17223/20710410/41/5

Связный граф с n ^ 3 вершинами, полученный из контура C_n путём переориентации некоторых его дуг, называется многоугольным графом. Рассмотрим некоторую биекцию р между множеством стоков и множеством источников многоугольного графа G. Присоединим к G все дуги вида vр(v), где v - сток. Полученный сильносвязный граф будем называть р-графом. Рассматривая последовательность различных матриц A, A², A³,... (степеней булевой матрицы A), заметим, что эта последовательность конечна. Если A^m - её последний элемент, то A^m+¹ = A¹ для некоторого l ^ m. Число ind(A) = l - 1 называется индексом матрицы A, а число p(A) = ((m + 1) - l) - её периодом. Для графа G с матрицей смежности A положим ind(G) = ind(A) и p(G) = p(A) (индекс и период графа). Вычислены значения периодов всех неизоморфных р-графов с числом вершин до 9. Рассчитаны максимальные периоды р-графов с числом вершин до 17. Доказана теорема, позволяющая вычислить период любого р-графа. Найдено значение максимального периода n-вершинных р-графов при чётном n и дана оценка максимального периода при нечётном n.