Apakah setiap digraf primitif memiliki siklus terarah?

Question

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

Answer 1

Anda bisa menafsirkan $(A^n)_{i,j}$ sebagai jumlah jalur dengan panjang $n$ dari puncak $i$ ke simpul $j$.

Sejak kita punya $A^k>0$, kami juga punya, untuk $n\in\mathbb N$, itu $A^{nk}>0$.

Oleh karena itu, kita dapat menemukan jalur dengan panjang sembarang dalam grafik, sehingga grafik harus mengandung sebuah siklus.