Digraph ดั้งเดิมทุกตัวมีวงจรกำกับหรือไม่?

Question

เดี่ยวเป็นกราฟ

วงจรกำกับหรือวงจรกำกับที่เรียบง่ายเป็นวงจรกำกับซึ่งในจุดซ้ำเพียง แต่เป็นจุดแรกและครั้งสุดท้าย

เดี่ยวดั้งเดิมถ้าเมทริกซ์ถ้อยคำที่เป็นแบบดั้งเดิม

เมทริกซ์ที่ไม่เป็นลบกำลังสอง $A$ถูกกล่าวว่าเป็นแบบดั้งเดิมหากมีจำนวนเต็มบวก$k$ ดังนั้น $A^k >0$ (รายการทั้งหมดของ $A^k$ เป็นบวก)

Answer 1

คุณสามารถตีความ $(A^n)_{i,j}$ เป็นจำนวนเส้นทางที่มีความยาว $n$ จากจุดยอด $i$ ถึงจุดยอด $j$.

เนื่องจากเรามี $A^k>0$เรายังมีสำหรับ $n\in\mathbb N$, นั่น $A^{nk}>0$.

ดังนั้นเราสามารถค้นหาเส้นทางที่มีความยาวตามอำเภอใจในกราฟได้ดังนั้นจึงต้องมีวัฏจักร