Apakah setiap digraf primitif memiliki siklus terarah?
Sebuah digraph adalah grafik diarahkan.
Sebuah siklus diarahkan atau sederhana diarahkan sirkuit adalah sirkuit diarahkan di mana simpul hanya mengulangi adalah simpul pertama dan terakhir.
Sebuah digraph primitif jika matriks ketetanggaan adalah primitif.
Matriks non-negatif persegi $A$dikatakan primitif jika terdapat bilangan bulat positif$k$ seperti yang $A^k >0$ (semua entri dari $A^k$ positif).
Saya hanya membutuhkan keberadaan jalan dengan struktur $i_0 i_1...i_k i_0$ (urutan tepi berbeda) dengan $k\geq 1$.
Jawaban
Iya. Untuk semua$i,j$, $(A^k)_{ij}>0$, jadi setidaknya ada satu panjang jalan kaki $k$ dari $v_1$ untuk $v_2$ dan setidaknya ada satu panjang jalan kaki $k$ dari $v_2$ untuk $v_1$. Jalan terarah tertutup ini yang dimulai dari$v_1$ untuk $v_2$ dan kemudian kembali ke $v_1$ harus berisi siklus terarah non-sepele (yaitu siklus dengan panjang minimal 2).