ในทฤษฎีกราฟอันดับวงจรของกราฟทิศทางเป็น มาตรวัด การเชื่อมต่อของกราฟทิศทาง ที่เสนอครั้งแรกโดย Eggan และBüchi ( Eggan 1963 ) โดยสัญชาตญาณแล้ว แนวคิดนี้วัดว่ากราฟทิศทางนั้นใกล้เคียงกับกราฟทิศทางที่ไม่มีวงจร (DAG) มากน้อยเพียงใด ในแง่ที่ว่า DAG มีอันดับวงจรเป็นศูนย์ ในขณะที่ กราฟ ทิศทางสมบูรณ์ที่ มีอันดับ nและมีวงวนในตัวเองที่แต่ละจุดยอดจะมีอันดับวงจรเท่ากับnอันดับวงจรของกราฟทิศทางมีความสัมพันธ์อย่างใกล้ชิดกับความลึกของต้นไม้ของกราฟที่ไม่มีทิศทางและความสูงของดาวในภาษาปกตินอกจากนี้ยังมีการนำไปใช้ใน การคำนวณ เมทริกซ์แบบเบาบาง (ดูBodlaender et al. 1995 ) และตรรกศาสตร์ ( Rossman 2008 )

อันดับวัฏจักรr ( G ) ของกราฟ ระบุทิศทาง G  = ( V ,  E )ถูกกำหนดแบบอุปนัยดังนี้:

• ถ้าGไม่มีวัฏจักร ดังนั้นr ( G ) = 0
• ถ้าGเป็นเมทริกซ์ที่มีการเชื่อมต่ออย่างแน่นหนาและEเป็นเมทริกซ์ที่ไม่ว่างเปล่า แล้ว

${\displaystyle r(G)=1+\min _{v\in V}r(Gv),\,}$โดยที่⁠ ⁠${\displaystyle Gv}$คือกราฟระบุทิศทางที่ได้จากการลบจุดยอดv และขอบทั้งหมดที่เริ่มต้นหรือสิ้นสุดที่v

• ถ้าGไม่มีการเชื่อมต่ออย่างแน่นหนาr ( G ) จะเท่ากับลำดับวัฏจักรสูงสุดในบรรดาส่วนประกอบที่มีการเชื่อมต่ออย่างแน่นหนาทั้งหมดของG

ความลึกของต้นไม้ในกราฟแบบไม่มีทิศทางมีคำจำกัดความที่คล้ายคลึงกันมาก โดยใช้การเชื่อมต่อแบบไม่มีทิศทางและส่วนประกอบที่เชื่อมต่อกัน แทนที่จะใช้การเชื่อมต่อที่แข็งแกร่งและส่วนประกอบที่เชื่อมต่อกันอย่างแข็งแกร่ง

แนวคิด Cycle rank ถูกนำเสนอโดยEggan (1963)ในบริบทของstar heightของภาษาปกติ ต่อมาได้รับการค้นพบใหม่โดย ( Eisenstat & Liu 2005 ) ในฐานะการวางนัยทั่วไปของtree-depth ที่ไม่มีทิศทาง ซึ่งได้รับการพัฒนามาตั้งแต่ช่วงทศวรรษ 1980 และนำไปประยุกต์ใช้กับ การคำนวณ เมทริกซ์แบบเบาบาง ( Schreiber 1982 )

อันดับวัฏจักรของ DAG คือ 0 ในขณะที่กราฟระบุทิศทางสมบูรณ์อันดับnที่มีวงวนในตัวเองที่แต่ละจุดยอดจะมีอันดับวัฏจักรเท่ากับnนอกเหนือจากนี้ อันดับวัฏจักรของกราฟระบุทิศทางอื่นๆ อีกเล็กน้อยเป็นที่ทราบกันดี ได้แก่ เส้นทางไร้ทิศทางอันดับnซึ่งมีความสัมพันธ์ของขอบแบบสมมาตรและไม่มีวงวนในตัวเอง มีอันดับวัฏจักร เท่ากับ n ( McNaughton 1969 ) สำหรับทอรัส แบบมีทิศทาง กล่าว คือผลคูณคาร์ทีเซียนของวงจรแบบมีทิศทางสองวงที่มีความยาวmและnเรามี และสำหรับm ≠ n ( Eggan 1963 , Gruber & Holzer 2008 ) ${\displaystyle P_{n}}$${\displaystyle \lfloor \log n\rfloor }$${\displaystyle (m\times n)}$${\displaystyle T_{m,n}}$${\displaystyle r(T_{n,n})=n}$${\displaystyle r(T_{m,n})=\min\{m,n\}+1}$

การคำนวณอันดับวัฏจักรนั้นยากในเชิงการคำนวณ: Gruber (2012)พิสูจน์ว่าปัญหาการตัดสินใจที่เกี่ยวข้องเป็นNP-completeแม้แต่สำหรับกราฟทิศทางแบบเบาบางที่มีดีกรีขาออกสูงสุดไม่เกิน 2 ก็ตาม ในทางที่ดี ปัญหานี้สามารถแก้ไขได้ในเวลาบนกราฟทิศทางที่มีดีกรีขาออก สูงสุด ไม่เกิน 2 และในเวลาบนกราฟทิศทางทั่วไป มีอัลกอริทึมประมาณค่าที่มีอัตราส่วนการประมาณค่า ${\displaystyle O(1.9129^{n})}$${\displaystyle O^{*}(2^{n})}$${\displaystyle O((\log n)^{\frac {3}{2}})}$

การประยุกต์ใช้ลำดับวัฏจักรครั้งแรกเกิดขึ้นในทฤษฎีภาษาเชิงรูปธรรมเพื่อศึกษาความสูงของดาวในภาษา ปกติเอ็กแกน (1963)ได้สร้างความสัมพันธ์ระหว่างทฤษฎีของนิพจน์ปกติ ออโตมาตาจำกัด และกราฟทิศทางในปีต่อมา ความสัมพันธ์นี้เป็นที่รู้จักในชื่อทฤษฎีบทของเอ็กแกนดูซาคารอวิช (2009)ในทฤษฎีออโตมาตา ออโตมาตาจำกัดแบบไม่กำหนดที่มี ε-การเคลื่อนไหว (ε-NFA) ถูกกำหนดให้เป็น5-tuple ( Q , Σ, δ , q0 _, F ) ซึ่งประกอบด้วย

• เซตจำกัดของสถานะQ
• เซตจำกัดของสัญลักษณ์อินพุต Σ
• ชุดของขอบที่มีป้ายกำกับδซึ่งเรียกว่าความสัมพันธ์การเปลี่ยนผ่าน : Q × (Σ ∪{ε}) × Qโดยที่ ε แทนคำว่าง
• สถานะเริ่มต้นq ₀ ∈ Q
• เซตของสถานะF ที่ถูก จำแนกเป็นสถานะยอมรับF ⊆ Q

คำw ∈ Σ ^*จะได้รับการยอมรับโดย ε-NFA ก็ต่อเมื่อมีเส้นทางแบบมีทิศทางจากสถานะเริ่มต้นq ₀ไปยังสถานะสุดท้ายบางสถานะในFโดยใช้ขอบจากδซึ่งการต่อกันของป้ายกำกับทั้งหมดที่เยี่ยมชมตามเส้นทางนั้นให้ผลลัพธ์เป็นคำwเซตของคำทั้งหมดใน Σ ^*ที่ได้รับการยอมรับโดยออโตมาตอนคือภาษาที่ ได้รับการยอมรับโดยออโตมาตอนA

เมื่อพูดถึงคุณสมบัติของกราฟระบุทิศทางของออโตมาตาจำกัดแบบไม่กำหนดAที่มีเซตสถานะQเราจะกล่าวถึงกราฟระบุทิศทางที่มีเซตจุดยอดQซึ่งเกิดจากความสัมพันธ์การเปลี่ยนสถานะของมัน โดยทฤษฎีบทนี้มีรายละเอียดดังต่อไปนี้

ทฤษฎีบทของเอ็กแกน : ความสูงของดาวในภาษาปกติLเท่ากับอันดับวงจรต่ำสุดในบรรดาออโตมาตาจำกัดแบบไม่กำหนดทั้งหมดที่มีการเคลื่อนไหว εที่ยอมรับL

บทพิสูจน์ของทฤษฎีบทนี้ได้รับการนำเสนอโดยEggan (1963)และล่าสุดโดยSakarovitch (2009 )

อีกหนึ่งการประยุกต์ใช้แนวคิดนี้คือ การคำนวณ เมทริกซ์แบบเบาบางกล่าวคือ การใช้การแยกส่วนแบบซ้อนกันเพื่อคำนวณการแยกตัวประกอบ Choleskyของเมทริกซ์ (สมมาตร) ในแบบขนานเมทริก ซ์แบบเบาบาง M ที่กำหนด อาจถูกตีความว่าเป็นเมทริกซ์ประชิดของกราฟระบุทิศทางสมมาตรGบน จุดยอด nจุด ในลักษณะที่ว่ารายการที่ไม่เป็นศูนย์ของเมทริกซ์มีความสัมพันธ์แบบหนึ่งต่อหนึ่งกับขอบของGหากอันดับวัฏจักรของกราฟ ระบุทิศทาง Gมีค่าไม่เกินkการแยกตัวประกอบ Cholesky ของMสามารถคำนวณได้ในขั้นตอนไม่เกินkบนคอมพิวเตอร์แบบขนานที่มีโปรเซสเซอร์ ( Dereniowski & Kubale 2004 ) ${\displaystyle (n\times n)}$${\displaystyle n}$

• อันดับวงจร