Her ilkel digrafın yönlendirilmiş bir döngüsü var mı?

Question

Bir digraf , yönlendirilmiş bir grafiktir.

Bir yönlendirilmiş çevrim ya da basit bir yönlendirilmiş devre tekrar eden noktalar ilk ve son noktalar olduğu bir yönlendirilmiş bir devredir.

Bir digraf, bitişik matrisi ilkelse ilkeldir.

Negatif olmayan bir kare matris $A$pozitif bir tam sayı varsa ilkel olduğu söylenir$k$ öyle ki $A^k >0$ (tüm girişler $A^k$ pozitif).

Answer 1

Yorumlayabilirsin $(A^n)_{i,j}$ uzunluktaki yolların sayısı olarak $n$ tepe noktasından $i$ tepe noktasına $j$.

Sahip olduğumuzdan beri $A^k>0$ayrıca bizde $n\in\mathbb N$, bu $A^{nk}>0$.

Bu nedenle, grafikte keyfi uzunlukta yollar bulabiliriz, bu yüzden bir döngü içermelidir.