هذه المقالة يتيمة. ساعد بإضافة وصلة إليها في مقالة متعلقة بها

دورة (نظرية الرسومات)

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
رسم به أضلاع ملونه لتوضيح المسار (بالأخضر)، طريق مغلق أو مسار مع رؤوس مكرره (بالأزرق) وداره بدون تكرار للأضلاع او الرؤوس (بالأحمر).

في نظرية الرسومات، دورة (بالإنجليزية: cycle)‏ في الرسم هي عبارة عن طريق ( trail ) غير خالي والذي لايحتوي على رؤوس مكرره عدا عند بداية ونهاية الممر، أي ان الدوره هي عبارة عن طريق مغلق. الدورة الموجهه في رسم موجه هي طريق موجه والذي به رأس مكرر فقط عند أول رأس بالطريق وآخر رأس.

الرسم الذي لايحتوي على أي دورات يسمى acyclic graph . الرسم الموجه الذي لايحتوي على أي دورات موجهه يسمى directed acyclic graph .

تعاريف[عدل]

الدارة والدورة[عدل]

  • الدارة هي عبارة عن طريق غير خالي والذي به أول رأس هي نفس الرأس الأخير (هنا ممكن أن تحتوي على رؤوس مكررة أو أضلاع مكررة).

ليكن رسم. الدارة هي الممر الغير خالي والذي متتابعة رؤوسه هي [1] .

  • الدورة أو الدارة البسيطة هي دارة التي بها جميع رؤوسها مختلفة عدا عند أول رأس وآخر رأس.[1]

دارة موجهه ودورة موجهة[عدل]

  • الدارة الموجهه هي طريق موجه ( directed trail ) غير خالي والذي به أول رأس هي نفسها آخر رأس بالطريق.[1]
ليكن رسم موجه. الدارة الموجهه هي الطريق موجه غير خالي المعرف بالمتتابعة والذي متتابعة الرؤوس له هي
  • الدورة الموجهه أو الدارة الموجهه البسيطة هي دارة موجهه والتي لاتحتوي على أي رؤوس مكررة عدا فقط أول رأس واخر رأس.[1]

دورات بدون أوتار (Chordless cycles )[عدل]

في هذا الرسم موضح دورة باللون الأخضر ( ) هي دورة بدون وتر . بينما الدورة باللون الأحمر ( ) ليست وذلك بسبب إحتوائها على الوتر .

دورة بدون وتر في الرسم هي عبارة عن دورة والتي لايوجد رأسين مرتبطين بواسطة ضلع لاينتمي إلى الدورة نفسها. الدورة بدون وتر تسمى أيضا hole أو دورة مولدة. المكمل او المتمم لهذه الدورة يسمى antihole. يستخدم مفهوم الدورة بدون وتر في تمييز الرسومات المكتملة أو التامة ( perfect graphs). فحسب نظرية الرسم المكتمل القويه فإن الرسم يكون مكتمل إذا وفقط إذا كان لايحتوي على دورة بدون وتر والتي بها رؤوس فردية أكبر من . الرسم ذو وتر ( chordal graph ) هو نوع خاص من الرسم المكتمل والذي لايحتوي على دورة بدون وتر بحجم أكبر من .

مصطلح girth للرسم هو عبارة عن طول أقصر دورة فيه. هذه الدورة التي لها أقصر طول في الرسم لابد أن تكون دورة بدون وتر.

يعرف Cages بأنه أصغر رسم منتظم والذي يحتوي على أقل عدد ممكن من الرؤوس وبه أقصر دورة.

فضاء الدورة ( Cycle space )[عدل]

إيجاد دورة (Cycle detection )[عدل]

غطاء الرسومات بإستخدام الدورات (Covering graphs by cycles)[عدل]

أصناف الرسومات حسب الدورات[عدل]

يوجد أنواع عديده مهمه من الرسومات والتي ممكن تعريفها حسب الدورات الموجوده بتلك الرسومات، ومن هذه الأنواع مايلي:

  • رسم ثنائي التجزئة: وهو رسم لايحتوي على أي دورة فردية. ويقصد بالدورة فرديه إذا كان عدد رؤوسها هو عدد فردي.

مراجع[عدل]

  1. أ ب ت ث Bender & Williamson 2010، صفحة 164.