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

Aug 18 2020

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

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

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

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

Ответы

3 Sudix Aug 18 2020 at 09:06

Вы можете интерпретировать $(A^n)_{i,j}$ как количество путей длиной $n$ из вершины $i$ к вершине $j$.

Поскольку у нас есть $A^k>0$, у нас также есть, для $n\in\mathbb N$, тот $A^{nk}>0$.

Следовательно, в графе можно найти пути произвольной длины, поэтому он должен содержать цикл.