E-catalog        

Библиогр.: 12 назв.

Связный граф с n @ 3 вершинами, полученный из контура Cn путём переориентации некоторых его дуг, называется многоугольным графом. Рассмотрим некоторую биекцию р между множеством стоков и множеством источников многоугольного графа G. Присоединим к G все дуги вида vр(v), где v — сток. Полученный сильносвязный граф будем называть р-графом. Рассматривая последовательность различных матриц A, A2, A3, ... (степеней булевой матрицы A), заметим, что эта последовательность конечна. Если Am — её последний элемент, то Am+1 = Al для некоторого l @ т . Число 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.