رتبة الدورة

في نظرية المخططات ، يُعدّ رتبة الدورة للمخطط الموجه مقياسًا لاتصال المخططات الموجهة ، وقد اقترحه إيغان وبوتشي ( إيغان، 1963 ) . وبشكلٍ بديهي، يقيس هذا المفهوم مدى قرب المخطط الموجه من المخطط الموجه غير الدوري (DAG)، بمعنى أن المخطط الموجه غير الدوري له رتبة دورة صفر، بينما المخطط الموجه الكامل من الرتبة n مع حلقة ذاتية عند كل رأس له رتبة دورة n . ترتبط رتبة الدورة للمخطط الموجه ارتباطًا وثيقًا بعمق الشجرة للمخطط غير الموجه وبارتفاع النجمة للغة منتظمة . كما يُستخدم هذا المفهوم في حسابات المصفوفات المتفرقة (انظر بودليندر وآخرون، 1995 ) والمنطق ( روسمان، 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.

إن عمق الشجرة في الرسم البياني غير الموجه له تعريف مشابه جداً، حيث يستخدم الاتصال غير الموجه والمكونات المتصلة بدلاً من الاتصال القوي والمكونات المتصلة بقوة.

تم تقديم رتبة الدورة بواسطة إيجان (1963) في سياق ارتفاع النجمة للغات المنتظمة . وقد أعيد اكتشافها بواسطة ( أيزنستات وليو 2005 ) كتعميم لعمق الشجرة غير الموجه ، والذي تم تطويره بدءًا من الثمانينيات وتطبيقه على حسابات المصفوفات المتفرقة ( شرايبر 1982 ) .

رتبة الدورة في الرسم البياني الموجه غير الدوري (DAG) هي 0، بينما الرسم البياني الموجه الكامل من الرتبة n مع حلقة ذاتية عند كل رأس له رتبة دورة n . وبصرف النظر عن ذلك، فإن رتبة الدورة لبعض الرسوم البيانية الموجهة الأخرى معروفة: المسار غير الموجه${\displaystyle P_{n}}$من الرتبة n ، والتي تمتلك علاقة حافة متناظرة ولا تحتوي على حلقات ذاتية، لها رتبة دورة${\displaystyle \lfloor \log n\rfloor }$( ماكنوتون 1969 ) . للمخرج${\displaystyle (m\times n)}$-حلقة${\displaystyle T_{m,n}}$أي، حاصل الضرب الديكارتي لدائرتين موجهتين بطولين m و n ، لدينا ${\displaystyle r(T_{n,n})=n}$و${\displaystyle r(T_{m,n})=\min\{m,n\}+1}$لـ م ≠ ن ( إيجان 1963 ، جروبر وهولزر 2008 ).

يُعدّ حساب رتبة الدورة أمرًا صعبًا حسابيًا: فقد أثبت غروبر (2012) أن مسألة القرار المقابلة هي مسألة NP-كاملة ، حتى بالنسبة للرسوم البيانية الموجهة المتفرقة ذات درجة الخروج القصوى التي لا تتجاوز 2. ومن الجانب الإيجابي، يمكن حل هذه المسألة في وقت${\displaystyle O(1.9129^{n})}$على الرسوم البيانية الموجهة ذات درجة الخروج القصوى التي لا تتجاوز 2، وفي الوقت${\displaystyle O^{*}(2^{n})}$فيما يخص الرسوم البيانية الموجهة العامة، توجد خوارزمية تقريبية بنسبة تقريبية.${\displaystyle O((\log n)^{\frac {3}{2}})}$.

• رتبة الدائرة