مرجع
آخر الزيارات

دورة (نظرية البيان)

389 كلمة•0 مشاهدة•🗒️ منذ 7 أيام
باختصار: في نظرية البيان، دورة البيان هي عبارة عن طريق (trail ) غير خالي والذي لايحتوي على رؤوس مكرره عدا عند بداية ونهاية الممر، أي ان الدوره هي عبارة عن طريق مغلق. في هذه المقالة 4 أقسام: «Cactus graph»، «دارة موجهه ودورة موجهة» و«أصناف الرسومات حسب الدورات» وغيرها.
المحتويات
  1. Cactus graph
  2. دارة موجهه ودورة موجهة
  3. أصناف الرسومات حسب الدورات
  4. الدارة والدورة
دورة (نظرية البيان)

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

في هذا الإطار، البيان الذي لايحتوي على أي دورات يسمى acyclic graph . الرسم الموجه الذي لايحتوي على أي دورات موجهه يسمى directed acyclic graph .

تعاريف

Cactus graph

رسم بدورة (Cycle graph ) وهو رسم مكون من دائرة واحدة.

رسم

دارة موجهه ودورة موجهة

ومن جهة أخرى، ليكن رسم موجه. الدارة الموجهه هي الطريق موجه غير خالي المعرف بالمتتابعة والذي متتابعة الرؤوس له هي

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

دورات بدون أوتار (Chordless cycles)

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

كذلك، الدارة الموجهه هي طريق موجه (directed trail ) غير خالي والذي به أول رأس هي نفسها آخر رأس بالطريق.

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

كذلك، الدورة الموجهه أو الدارة الموجهه البسيطة هي دارة موجهه والتي لاتحتوي على أي رؤوس مكررة عدا فقط أول رأس واخر رأس.

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

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

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

الدارة والدورة

وفي هذا الصدد، الدورة أو الدارة البسيطة هي دارة التي بها جميع رؤوسها مختلفة عدا عند أول رأس وآخر رأس.

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

إضافةً إلى ذلك، ليكن رسم. الدارة هي الممر الغير خالي والذي متتابعة رؤوسه هي .

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.