У каждого примитивного орграфа есть направленный цикл?

Question

Орграф представляет собой ориентированный граф.

Направлено цикл или простой ориентированный контур представляет собой ориентированный контур , в котором только повторяющиеся вершины первая и последняя вершина.

Диграф примитивно , если его матрица смежности примитивно.

Квадратная неотрицательная матрица $A$называется примитивным, если существует положительное целое число$k$ такой, что $A^k >0$ (все записи $A^k$ положительные).

Мне нужно только наличие пути со структурой $i_0 i_1...i_k i_0$ (последовательность четких ребер) с $k\geq 1$.

Answer 1

Да. Для всех$i,j$, $(A^k)_{ij}>0$, так что есть хотя бы одна прогулка длиной $k$ из $v_1$ к $v_2$ и есть хотя бы одна прогулка по длине $k$ из $v_2$ к $v_1$. Эта закрытая направленная прогулка, идущая от$v_1$ к $v_2$ а затем обратно к $v_1$ должен содержать нетривиальный направленный цикл (т.е. цикл длины не менее 2).