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

Question

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

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

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

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

ฉันต้องการเพียงการดำรงอยู่ของเส้นทางที่มีโครงสร้าง $i_0 i_1...i_k i_0$ (ลำดับของขอบที่แตกต่าง) ด้วย $k\geq 1$.

Answer 1

ใช่. สำหรับทุกอย่าง$i,j$, $(A^k)_{ij}>0$ดังนั้นจึงมีความยาวอย่างน้อยหนึ่งการเดิน $k$ จาก $v_1$ ถึง $v_2$ และมีระยะทางเดินอย่างน้อยหนึ่งครั้ง $k$ จาก $v_2$ ถึง $v_1$. เส้นทางเดินแบบปิดซึ่งไปจาก$v_1$ ถึง $v_2$ แล้วกลับไปที่ $v_1$ ต้องมีวัฏจักรชี้นำที่ไม่สำคัญ (เช่นวงจรความยาวอย่างน้อย 2)