أساس الدورة

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 20 صور
الموسوعة الحرة
الفرق المتناظر لدورتين هو رسم بياني جزئي أويلري

في نظرية المخططات ، وهي فرع من فروع الرياضيات، تُعرف قاعدة الدورات للمخطط غير الموجه بأنها مجموعة من الدورات البسيطة التي تُشكل أساس فضاء الدورات للمخطط. أي أنها مجموعة دنيا من الدورات التي تسمح بالتعبير عن كل مخطط فرعي ذي درجة زوجية كفرق متناظر بين دورات الأساس.

يمكن تكوين أساس دوري أساسي من أي شجرة ممتدة أو غابة ممتدة للرسم البياني المعطى، وذلك باختيار الدورات المتكونة من خلال دمج مسار في الشجرة وحافة واحدة خارجها. وبدلاً من ذلك، إذا كانت حواف الرسم البياني ذات أوزان موجبة، فيمكن إنشاء أساس الدورة ذي الوزن الأدنى في وقت متعدد الحدود .

في الرسوم البيانية المستوية ، تُشكّل مجموعة الدورات المحدودة لتضمين الرسم البياني أساسًا للدورات. ويتوافق أساس الدورات ذو الوزن الأدنى للرسم البياني المستوي مع شجرة جوموري-هو للرسم البياني الثنائي .

التعريفات

الرسم البياني الجزئي الممتد لرسم بياني معين G له نفس مجموعة رؤوس G نفسه ، ولكن قد يحتوي على عدد أقل من الحواف. يُقال إن الرسم البياني G ، أو أحد رسوماته البيانية الجزئية، هو رسم بياني أويلري إذا كان لكل رأس من رؤوسه درجة زوجية (عدد الحواف المتصلة به). كل دورة بسيطة في الرسم البياني هي رسم بياني جزئي أويلري، ولكن قد توجد دورات أخرى. فضاء الدورات في الرسم البياني هو مجموعة رسوماته البيانية الجزئية الأويلرية. وهو يشكل فضاءً متجهيًا على الحقل المنتهي ذي العنصرين . عملية جمع المتجهات هي الفرق المتناظر بين رسمين بيانيين جزئيين أو أكثر، مما يُشكل رسمًا بيانيًا جزئيًا آخر يتكون من الحواف التي تظهر عددًا فرديًا من المرات في وسيطات عملية الفرق المتناظر. [ 1 ]

أساس الدورة هو أساس لهذا الفضاء المتجهي، حيث يمثل كل متجه أساس دورة بسيطة. ويتكون من مجموعة من الدورات التي يمكن دمجها، باستخدام الفروق المتناظرة، لتشكيل كل رسم بياني فرعي أويلري، وهو الرسم البياني الأدنى الذي يتمتع بهذه الخاصية. يحتوي كل أساس دورة لرسم بياني معين على نفس عدد الدورات، وهو ما يساوي بُعد فضاء دوراته. يُسمى هذا العدد رتبة الدائرة للرسم البياني، وهو يساويم-ن+ج{\displaystyle m-n+c}أينم{\displaystyle m}يمثل عدد الحواف في الرسم البياني،ن{\displaystyle n}يمثل عدد الرؤوس، وج{\displaystyle c}يمثل عدد المكونات المتصلة . [ 2 ]

قواعد الدراجات الخاصة

تمت دراسة العديد من الأنواع الخاصة من قواعد الدورات، بما في ذلك قواعد الدورات الأساسية، وقواعد الدورات الأساسية الضعيفة، وقواعد الدورات المتفرقة (أو 2)، وقواعد الدورات التكاملية. [ 3 ]

دورات مستحثة

لكل رسم بياني أساس دوري، حيث تكون كل دورة فيه دورة مستحثة . في الرسم البياني المتصل بثلاثة رؤوس ، يوجد دائمًا أساس يتكون من دورات محيطية ، وهي دورات لا يؤدي حذفها إلى فصل الرسم البياني المتبقي. [ 4 ] [ 5 ] في أي رسم بياني آخر غير الرسم البياني المُشكَّل بإضافة حافة واحدة إلى دورة، يجب أن تكون الدورة المحيطية دورة مستحثة.

الدورات الأساسية

لوتي{\displaystyle T}هي شجرة ممتدة أو غابة ممتدة لرسم بياني معينجي{\displaystyle G}، وهـ{\displaystyle e}حافة لا تنتمي إلىتي{\displaystyle T}ثم الدورة الأساسيةجهـ{\displaystyle C_{e}}محدد بواسطةهـ{\displaystyle e}هي الدورة البسيطة المكونة منهـ{\displaystyle e}بالإضافة إلى المسار فيتي{\displaystyle T}ربط نقاط نهايةهـ{\displaystyle e}يوجد بالضبطم-ن+ج{\displaystyle m-n+c}دورات أساسية، واحدة لكل حافة لا تنتمي إلىتي{\displaystyle T}كل منها مستقل خطيًا عن الدورات المتبقية، لأنه يتضمن حافةهـ{\displaystyle e}وهذا غير موجود في أي دورة أساسية أخرى. لذلك، تُشكّل الدورات الأساسية أساسًا لفضاء الدورات. [ 1 ] [ 2 ] يُطلق على أساس الدورات المُنشأ بهذه الطريقة اسم أساس الدورات الأساسية أو أساس الدورات الأساسية القوية . [ 3 ]

من الممكن أيضًا تحديد خصائص قواعد الدورات الأساسية دون تحديد الشجرة التي تُعتبر أساسية لها. توجد شجرة يكون فيها أساس دورة معين أساسيًا إذا وفقط إذا احتوت كل دورة على حافة غير موجودة في أي دورة أساسية أخرى، أي أن كل دورة مستقلة عن غيرها. ويترتب على ذلك أن مجموعة من الدورات تُشكل أساس دورة أساسيًا لـجي{\displaystyle G}إذا وفقط إذا كانت لها خاصية الاستقلال وكان لديها العدد الصحيح من الدورات لتكون أساسًا لـجي{\displaystyle G}[ 6 ]​

دورات أساسية ضعيفة

يُطلق على أساس الدورة اسم الأساس الضعيف إذا أمكن ترتيب دوراته ترتيبًا خطيًا بحيث تتضمن كل دورة ضلعًا واحدًا على الأقل غير موجود في أي دورة سابقة. أساس الدورة الأساسي يكون تلقائيًا أساسًا ضعيفًا (لأي ترتيب للأضلاع). [ 3 ] [ 7 ] إذا كان كل أساس دورة في الرسم البياني أساسًا ضعيفًا، فإن الأمر نفسه ينطبق على كل قاصر في الرسم البياني. بناءً على هذه الخاصية، يمكن تمييز فئة الرسوم البيانية (والرسوم البيانية المتعددة ) التي يكون فيها كل أساس دورة أساسًا ضعيفًا بخمسة قاصرات ممنوعة : رسم الهرم المربع ، والرسم البياني المتعدد الناتج عن مضاعفة جميع أضلاع دورة رباعية الرؤوس، ورسمان بيانيان متعددان ناتجان عن مضاعفة ضلعين من رباعي الأوجه ، والرسم البياني المتعدد الناتج عن مضاعفة أضلاع مثلث ثلاث مرات. [ 8 ]

دورات الوجه

إذا تم تضمين رسم بياني مستوٍ متصل ومحدود في المستوى، فإن كل وجه من أوجه التضمين يكون محدودًا بدورة من الحواف. أحد الأوجه يكون بالضرورة غير محدود (لأنه يشمل نقاطًا بعيدة كيفما كانت عن رؤوس الرسم البياني)، بينما تكون الأوجه المتبقية محدودة. وفقًا لصيغة أويلر للرسوم البيانية المستوية ، يوجد بالضبطم-ن+1{\displaystyle m-n+1}الوجوه المحدودة. الفرق المتناظر لأي مجموعة من دورات الوجوه هو حدود المجموعة المقابلة من الوجوه، وتختلف حدود مجموعات الوجوه المحدودة المختلفة، لذا لا يمكن تمثيل المجموعة نفسها كفرق متناظر لدورات الوجوه بأكثر من طريقة واحدة؛ وهذا يعني أن مجموعة دورات الوجوه مستقلة خطيًا. وباعتبارها مجموعة مستقلة خطيًا من عدد كافٍ من الدورات، فإنها تُشكّل بالضرورة أساسًا للدورات. [ 9 ] وهو دائمًا أساس دورات ضعيف، ويكون أساسيًا إذا وفقط إذا كان تضمين الرسم البياني خارجيًا مستويًا .

بالنسبة للرسوم البيانية المُضمنة بشكل صحيح على أسطح أخرى بحيث تكون جميع أوجه التضمين أقراصًا طوبولوجية، فليس من الصحيح عمومًا وجود أساس دوري باستخدام دورات الأوجه فقط. تُولّد دورات الأوجه لهذه التضمينات مجموعة فرعية مناسبة من جميع الرسوم البيانية الفرعية الأويلرية. زمرة التماثلح2(S،Z2){\displaystyle H_{2}(S,\mathbb {Z} _{2})}السطح المعطىS{\displaystyle S}تُعرّف هذه النظرية الرسوم البيانية الفرعية الأويلرية التي لا يمكن تمثيلها كحدود لمجموعة من الوجوه. يستخدم معيار ماك لين للتسطيح هذه الفكرة لوصف الرسوم البيانية المستوية بدلالة قواعد الدورات: يكون الرسم البياني غير الموجه المحدود مستويًا إذا وفقط إذا كان له قاعدة دورات متفرقة أو قاعدة ثنائية ، [ 3 ] وهي قاعدة يشارك فيها كل ضلع من أضلاع الرسم البياني في دورتين أساسيتين على الأكثر. في الرسم البياني المستوي، تكون قاعدة الدورات التي تشكلها مجموعة الوجوه المحدودة متفرقة بالضرورة، وعلى العكس من ذلك، فإن قاعدة الدورات المتفرقة لأي رسم بياني تشكل بالضرورة مجموعة الوجوه المحدودة لتضمين مستوٍ لرسمه البياني. [ 9 ] [ 10 ]

القواعد التكاملية

يمكن تفسير فضاء الدورات للرسم البياني باستخدام نظرية التماثل باعتباره مجموعة التماثلح1(جي،Z2){\displaystyle H_{1}(G,\mathbb {Z} _{2})}من مُركَّب تبسيطي بنقطة لكل رأس من رؤوس الرسم البياني وقطعة مستقيمة لكل حافة من حواف الرسم البياني. يمكن تعميم هذا البناء على مجموعة التماثل.ح1(جي،R){\displaystyle H_{1}(G,R)}على حلقة عشوائيةR{\displaystyle R}. ومن الحالات الخاصة المهمة حلقة الأعداد الصحيحة ، التي تكون لها مجموعة التماثلح1(جي،Z){\displaystyle H_{1}(G,\mathbb {Z} )}هي زمرة أبيلية حرة ، وهي زمرة جزئية من الزمرة الأبيلية الحرة المولدة بواسطة حواف الرسم البياني. وبشكل أقل تجريدًا، يمكن إنشاء هذه الزمرة عن طريق تعيين اتجاه عشوائي لحواف الرسم البياني المعطى؛ ثم عناصر الزمرةح1(جي،Z){\displaystyle H_{1}(G,\mathbb {Z} )}هي عبارة عن ترقيم لحواف الرسم البياني بأعداد صحيحة، بحيث يكون مجموع ترقيم الحواف الواردة عند كل رأس مساويًا لمجموع ترقيم الحواف الصادرة. عملية المجموعة هي جمع متجهات الترقيم هذه. أساس الدورة الصحيحة هو مجموعة من الدورات البسيطة التي تولد هذه المجموعة. [ 3 ]

الحد الأدنى للوزن

إذا مُنحت حواف الرسم البياني أوزانًا عددية حقيقية، يُمكن حساب وزن الرسم البياني الفرعي كمجموع أوزان حوافه. أساس الوزن الأدنى لفضاء الدورات هو بالضرورة أساس دورات: وفقًا لنظرية فيبلن ، [ 11 ] يُمكن تحليل أي رسم بياني فرعي أويلري ليس دورة بسيطة إلى عدة دورات بسيطة، والتي بالضرورة تكون ذات وزن أصغر.

بحسب الخصائص القياسية للقواعد في الفضاءات المتجهة والماترويدات، فإن قاعدة الدورة ذات الوزن الأدنى لا تقلل فقط من مجموع أوزان دوراتها، بل تقلل أيضًا من أي توليفة رتيبة أخرى لأوزان الدورات. على سبيل المثال، هي قاعدة الدورة التي تقلل من وزن أطول دورة فيها. [ 12 ]

خوارزميات الوقت متعدد الحدود

في أي فضاء متجهي، وبشكل أعم في أي مصفوفة ، يمكن إيجاد أساس ذي وزن أدنى باستخدام خوارزمية جشعة تنظر في عناصر الأساس المحتملة واحدًا تلو الآخر، مرتبة حسب أوزانها، وتُضمّن عنصرًا في الأساس عندما يكون مستقلًا خطيًا عن عناصر الأساس المختارة سابقًا. يمكن اختبار الاستقلال الخطي باستخدام طريقة الحذف الغاوسي . مع ذلك، قد يحتوي الرسم البياني غير الموجه على مجموعة كبيرة جدًا من الدورات البسيطة، لذا سيكون من غير العملي حسابيًا توليد جميع هذه الدورات واختبارها.

قدّم هورتون (1987) أول خوارزمية زمنية متعددة الحدود لإيجاد أساس ذي وزن أدنى، في الرسوم البيانية التي يكون فيها وزن كل حافة موجبًا. تستخدم خوارزميته هذا النهج القائم على التوليد والاختبار، لكنها تقصر الدورات المولدة على مجموعة صغيرة منيا(من){\displaystyle O(mn)}تُسمى هذه الدورات بدورات هورتون . دورة هورتون هي دورة أساسية في شجرة أقصر مسار في الرسم البياني المُعطى. يوجد على الأكثر n شجرة مختلفة لأقصر مسار (شجرة لكل رأس بداية)، ولكل منها أقل من m دورة أساسية، مما يُحدد الحد الأقصى لعدد دورات هورتون. وكما أوضح هورتون، فإن كل دورة في أساس دورة الوزن الأدنى هي دورة هورتون. [ 13 ] باستخدام خوارزمية ديكسترا لإيجاد كل شجرة أقصر مسار، ثم استخدام طريقة الحذف الغاوسي لإجراء خطوات الاختبار في خوارزمية الأساس الجشع، نحصل على خوارزمية ذات زمن متعدد الحدود لأساس دورة الوزن الأدنى. وقد طوّر باحثون لاحقون خوارزميات مُحسّنة لهذه المشكلة، [ 14 ] [ 15 ] [ 16 ] [ 17 ] مما يُقلل من تعقيد الوقت في أسوأ الحالات لإيجاد أساس دورة الوزن الأدنى في الرسم البياني.م{\displaystyle m}الحواف ون{\displaystyle n}الرؤوس إلىيا(م2ن/سجل⁡ن){\displaystyle O(m^{2}n/\log n)}[ 18 ]​

صعوبة NP

إن إيجاد الأساس الأساسي ذي الوزن الأدنى الممكن يرتبط ارتباطًا وثيقًا بمشكلة إيجاد شجرة ممتدة تُقلل متوسط ​​المسافات بين أزواج الحواف؛ وكلاهما من المسائل الصعبة حسابيًا (NP-hard ). [ 19 ] كما أن إيجاد أساس أساسي ضعيف ذي وزن أدنى هو أيضًا من المسائل الصعبة حسابيًا (NP-hard)، [ 7 ] وتقريبه من المسائل الصعبة حسابيًا (MAXSNP-hard) . [ 20 ] إذا سُمح بالأوزان السالبة والدورات ذات الأوزان السالبة، فإن إيجاد أساس دورة ذي وزن أدنى (بدون قيود) هو أيضًا من المسائل الصعبة حسابيًا (NP-hard)، حيث يمكن استخدامه لإيجاد دورة هاميلتونية : إذا كان الرسم البياني هاميلتونيًا، وكانت جميع الحواف تحمل الوزن -1 ، فإن أساس الدورة ذي الوزن الأدنى يتضمن بالضرورة دورة هاميلتونية واحدة على الأقل.

في الرسوم البيانية المستوية

لا يشترط أن يكون أساس الدورات ذي الوزن الأدنى للرسم البياني المستوي هو نفسه الأساس المُشكَّل من وجوهه المحدودة: فقد يتضمن دورات ليست وجوهًا، وقد لا تُحتسب بعض الوجوه كدورات في أساس الدورات ذي الوزن الأدنى. مع ذلك، يوجد أساس دورات ذي وزن أدنى لا تتقاطع فيه أي دورتين: فلكل دورتين في الأساس، إما أن تُحيط الدورتان بمجموعات فرعية منفصلة من الوجوه المحدودة، أو أن تُحيط إحدى الدورتين بالأخرى. تُقابل هذه المجموعة من الدورات، في الرسم البياني الثنائي للرسم البياني المستوي المُعطى، مجموعة من القطوع التي تُشكِّل شجرة جوموري-هو للرسم البياني الثنائي، وهي أساس الوزن الأدنى لفضاء قطوعه . [ 21 ] بناءً على هذه الازدواجية، يُمكن إنشاء تمثيل ضمني لأساس الدورات ذي الوزن الأدنى في الرسم البياني المستوي في وقتيا(نسجل3⁡ن){\displaystyle O(n\log ^{3}n)}[ 22 ]​

التطبيقات

استُخدمت قواعد الدورات لحل مسائل الجدولة الدورية، مثل مسألة تحديد جدول زمني لنظام النقل العام. في هذا التطبيق، تتوافق دورات قاعدة الدورة مع متغيرات في برنامج عدد صحيح لحل المسألة. [ 23 ]

في نظرية الصلابة الهيكلية وعلم الحركة ، تُستخدم قواعد الدورة لتوجيه عملية وضع نظام من المعادلات غير المتكررة التي يمكن حلها للتنبؤ بصلابة أو حركة الهيكل. في هذا التطبيق، تؤدي قواعد الدورة ذات الوزن الأدنى أو شبه الأدنى إلى أنظمة معادلات أبسط. [ 24 ]

في الحوسبة الموزعة ، تم استخدام قواعد الدورة لتحليل عدد الخطوات اللازمة لاستقرار الخوارزمية. [ 25 ]

في مجال المعلوماتية الحيوية ، استُخدمت القواعد الحلقية لتحديد معلومات النمط الفرداني من بيانات تسلسل الجينوم. [ 26 ] كما استُخدمت القواعد الحلقية لتحليل البنية الثلاثية للحمض النووي الريبي (RNA) . [ 27 ]

يمكن استخدام أساس دورة الوزن الأدنى لرسم بياني لأقرب جار لنقاط مأخوذة من سطح ثلاثي الأبعاد للحصول على إعادة بناء للسطح. [ 28 ]

في علم المعلومات الكيميائية ، يُشار إلى أساس الدورة الأدنى للرسم البياني الجزيئي باسم أصغر مجموعة من أصغر الحلقات . [ 29 ] [ 30 ] [ 31 ]

مراجع

  1. 1 2 ديستل، راينهارد (2012)، "1.9 بعض الجبر الخطي" ، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات، المجلد  173، سبرينغر، الصفحات 23-28 .
  2. 1 2 غروس، جوناثان ل.؛ يلين، جاي (2005)، "4.6 الرسوم البيانية والفضاءات المتجهة" ، نظرية الرسوم البيانية وتطبيقاتها (الطبعة الثانية )، مطبعة سي آر سي، ص 197-207 ، ISBN   9781584885054.
  3. 1 2 3 4 5 ليبشن، كريستيان؛ ريزي، روميو (2007)، "فئات قواعد الدورات"، الرياضيات التطبيقية المنفصلة ، ​​155 (3): 337-355 ، doi : 10.1016/j.dam.2006.06.007 ، MR 2303157 .
  4. ^ ديستيل (2012) ، ص 32، 65.
  5. ↑ توت، دبليو تي (1963)، "كيفية رسم مخطط بياني"، وقائع الجمعية الرياضية بلندن ، السلسلة الثالثة، 13 (1): 743-767 ، رمز Bibcode : 1963PLMS...13..743T ، doi : 10.1112/plms/s3-13.1.743 ، MR 0158387 انظر على وجه الخصوص إلى النظرية 2.5.
  6. ↑ كريب، د. و.؛ رينجيزن، ر. د.؛ شير، د. ر. (1981)، "حول قواعد الدورات في الرسم البياني"، وقائع المؤتمر الثاني عشر لجنوب شرق الولايات المتحدة حول التوافقية ونظرية الرسم البياني والحوسبة، المجلد الأول (باتون روج، لويزيانا، 1981) ، كونغرسوس نوميرانتيوم، المجلد 32، الصفحات 221-229 ، MR 0681883   .
  7. 1 2 ريزي، روميو (2009)، "من الصعب إيجاد قواعد دورات أساسية ضعيفة دنيا"، Algorithmica ، 53 (3): 402-424 ، doi : 10.1007/s00453-007-9112-8 ، MR 2482112 ، S2CID 12675654  .
  8. ^ هارتفيجسن، ديفيد؛ Zemel، Eitan (1989)، “هل كل أساس دورة أساسي؟”، مجلة نظرية الرسم البياني ، 13 (1): 117–137 ، دوى : 10.1002/jgt.3190130115 ، MR 0982873 .
  9. 1 2 ديستل (2012) ، الصفحات من 105 إلى 106.
  10. ^ Mac Lane، S. (1937)، “شرط اندماجي للرسوم البيانية المستوية” (PDF) ، Fundamenta Mathematicae ، 28 : 22–32 ، دوى : 10.4064/fm-28-1-22-32.
  11. ↑ فيبلين، أوزوالد (1912)، "تطبيق المعادلات النمطية في تحليل المواقع"، حوليات الرياضيات ، السلسلة الثانية، 14 (1): 86-94 ، doi : 10.2307/1967604 ، JSTOR 1967604 .
  12. ↑ تشيكرينغ، ديفيد م.؛ غايغر، دان؛ هيكرمان، ديفيد (1995)، "حول إيجاد أساس دوري بأقصر دورة قصوى"، رسائل معالجة المعلومات ، 54 (1): 55-58 ، CiteSeerX 10.1.1.650.8218 ، doi : 10.1016/0020-0190(94)00231-M ، MR 1332422  .
  13. ↑ هورتون، جيه دي (1987)، "خوارزمية زمنية متعددة الحدود لإيجاد أقصر أساس دوري للرسم البياني"، مجلة SIAM للحوسبة ، 16 (2): 358-366 ، doi : 10.1137/0216026.
  14. ^ بيرغر، فرانزيسكا؛ جريتزمان، بيتر. دي فريس، سفين (2004)، “قواعد الدورة الدنيا للرسوم البيانية للشبكة”، الخوارزمية ، 40 (1): 51–62 ، دوى : 10.1007/s00453-004-1098-x ، MR 2071255 ، S2CID 9386078  .
  15. ↑ ميلهورن، كورت ؛ ميخائيل، ديميتريوس (2006)، "تنفيذ خوارزميات أساس الدورة الدنيا" ، مجلة ACM للخوارزميات التجريبية ، 11 : 2.5، CiteSeerX 10.1.1.60.1087 ، doi : 10.1145/1187436.1216582 ، S2CID 6198296  .
  16. ^ كافيثا، تليكبالي ؛ الأماكن القريبة : ميخائيل، ديميتريوس؛ بالوش، كاتارزينا إي. (2008)، “Anيا~(م2ن){\displaystyle {\tilde {O}}(m^{2}n)}"خوارزمية لأساس الدورة الدنيا للرسوم البيانية"، Algorithmica ، 52 (3): 333-349 ، doi : 10.1007/s00453-007-9064-z ، MR 2452919 .
  17. ↑ كافيتا، تيليكابالي؛ ليبشن، كريستيان؛ ميلهورن، كورت ؛ ميخائيل، ديميتريوس؛ ريتزي، روميو؛ أوكيردت، تورستن؛ زفايغ، كاتارينا أ. (2009)، "قواعد الدورة في الرسوم البيانية: التوصيف، والخوارزميات، والتعقيد، والتطبيقات" ، مجلة مراجعة علوم الحاسوب ، 3 (4): 199-243 ، doi : 10.1016/j.cosrev.2009.08.001.
  18. ↑ أمالدي، إدواردو؛ إيوليانو، كلاوديو؛ ريتزي، روميو (2010)، "خوارزميات حتمية فعالة لإيجاد أساس دورة دنيا في الرسوم البيانية غير الموجهة"، البرمجة العددية والتحسين التوافقي: المؤتمر الدولي الرابع عشر، IPCO 2010، لوزان، سويسرا، 9-11 يونيو 2010، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد 6080، سبرينغر، الصفحات 397-410 ، Bibcode : 2010LNCS.6080..397A ، doi : 10.1007/978-3-642-13036-6_30 ، ISBN   978-3-642-13035-9MR 2661113​ .
  19. ↑ ديو، نارسينغ؛ برابهو، جي إم؛ كريشنامورثي، إم إس (1982)، "خوارزميات لتوليد الدورات الأساسية في الرسم البياني"، معاملات ACM في البرمجيات الرياضية ، 8 (1): 26-42 ، doi : 10.1145/355984.355988 ، MR 0661120 ، S2CID 2260051  .
  20. ↑ غالبياتي، جوليا؛ أمالدي، إدواردو (2004)، "حول إمكانية تقريب مسألة أساس الدورة الأساسية الدنيا"، التقريب والخوارزميات عبر الإنترنت: ورشة العمل الدولية الأولى، WAOA 2003، بودابست، المجر، 16-18 سبتمبر 2003، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 2909، برلين: سبرينغر، الصفحات 151-164 ، doi : 10.1007/978-3-540-24592-6_12 ، ISBN   978-3-540-21079-5MR 2089904​ .
  21. ↑ هارتفيغسن، ديفيد؛ ماردون، راسل (1994)، "مسألة القطع الأدنى لجميع الأزواج ومسألة أساس الدورة الأدنى على الرسوم البيانية المستوية"، مجلة SIAM للرياضيات المتقطعة ، 7 (3): 403-418 ، doi : 10.1137/S0895480190177042 ، MR 1285579 .
  22. ↑ بوراديل، غلينكورا؛ إبشتاين، ديفيد ؛ نايري، أمير؛ وولف-نيلسن، كريستيان (2016)، "القطع الدنيا لجميع الأزواج في وقت شبه خطي للرسوم البيانية المضمنة في السطح"، وقائع الندوة الدولية الثانية والثلاثين للهندسة الحسابية ، وقائع لايبنتز الدولية في المعلوماتية (LIPIcs)، المجلد 51، شلوس داغشتول، الصفحات 22:1–22:16، arXiv : 1411.7055 ، doi : 10.4230/LIPIcs.SoCG.2016.22 ، ISBN   978-3-95977-009-5، S2CID 215762172 .
  23. ↑ ليبشن، كريستيان (2007)، "تحسين الجداول الزمنية الدورية في النقل العام"، وقائع بحوث العمليات 2006 ، المجلد 2006، الصفحات 29-36 ، doi : 10.1007/978-3-540-69995-8_5 ، ISBN   978-3-540-69994-1.
  24. ↑ كاسيل، أ.س.؛ دي هندرسون، ج.س.؛ كافيه، أ. (1974)، "قواعد الدورة لتحليل مرونة الهياكل"، المجلة الدولية للطرق العددية في الهندسة ، 8 (3): 521-528 ، رمز Bibcode : 1974IJNME...8..521C ، doi : 10.1002/nme.1620080308.
  25. ↑ بولينييه، كريستيان؛ بيتي، فرانك؛ فيلان، فنسنت (2004)، "عندما تساعد نظرية الرسم البياني في تحقيق الاستقرار الذاتي"، وقائع الندوة السنوية الثالثة والعشرين لجمعية ACM حول مبادئ الحوسبة الموزعة (PODC '04) ، نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM، الصفحات 150-159 ، CiteSeerX 10.1.1.79.2190 ، doi : 10.1145/1011767.1011790 ، ISBN   978-1581138023، S2CID 14936510 .
  26. ↑ أغيار، ديريك؛ إستريل، سورين (2012)، "HapCompass: خوارزمية سريعة تعتمد على أساس الدورة لتجميع النمط الفرداني بدقة لبيانات التسلسل"، مجلة علم الأحياء الحاسوبي ، 19 (6): 577-590 ، doi : 10.1089/cmb.2012.0084 ، PMC 3375639 ، PMID 22697235  .
  27. ↑ ليميو، سيباستيان؛ ماجور، فرانسوا (2006)، "الاستخلاص والتصنيف الآلي للوحدات الحلقية في البنية الثلاثية للحمض النووي الريبي"، مجلة أبحاث الأحماض النووية ، 34 (8): 2340-2346 ، doi : 10.1093/nar/gkl120 ، PMC 1458283 ، PMID 16679452  .
  28. ^ جوتسمان ، كريج. كاليجوسي، كانيلا؛ الأماكن القريبة : ميخائيل، ديميتريوس؛ بيرجا، إيفانجيليا (2007)، “قواعد دورة الرسوم البيانية ومشعبات العينات”، التصميم الهندسي بمساعدة الكمبيوتر ، 24 ( 8– 9): 464–480 ، CiteSeerX 10.1.1.298.9661 ، دوى : 10.1016/j.cagd.2006.07.001 ، MR 2359763  .
  29. ↑ ماي، جون دبليو؛ شتاينبك، كريستوف (2014)، "إدراك الحلقة بكفاءة لمجموعة أدوات تطوير الكيمياء"، مجلة المعلوماتية الكيميائية ، 6 (3): 3، doi : 10.1186/1758-2946-6-3 ، PMC 3922685 ، PMID 24479757  
  30. ↑ داونز، جي إم؛ جيليه، في جيه؛ هوليداي، جي دي؛ لينش، إم إف (1989)، "مراجعة لخوارزميات إدراك الحلقات للرسوم البيانية الكيميائية"، مجلة المعلومات الكيميائية وعلوم الحاسوب ، 29 (3): 172-187 ، doi : 10.1021/ci00063a007
  31. ↑ زامورا، أ. (1979)، "خوارزمية لإيجاد أصغر مجموعة من أصغر الحلقات"، مجلة المعلومات الكيميائية وعلوم الحاسوب ، 16 (1): 40-43 ، doi : 10.1021/ci60005a013