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$ pozitiftir).

Sadece yapısı olan bir yolun varlığına ihtiyacım var $i_0 i_1...i_k i_0$ (farklı kenarlar dizisi) ile $k\geq 1$.

Answer 1

Evet. Hepsi için$i,j$, $(A^k)_{ij}>0$, yani en az bir uzunluk yürüyüşü var $k$ itibaren $v_1$ -e $v_2$ ve en az bir uzunluk yürüyüşü var $k$ itibaren $v_2$ -e $v_1$. Bu kapalı yöndeki yürüyüş$v_1$ -e $v_2$ ve sonra geri dön $v_1$ önemsiz olmayan yönlendirilmiş bir döngü içermelidir (yani en az 2 uzunlukta bir döngü).