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

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

لمعانٍ أخرى، انظر دورة (توضيح).

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

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

تعاريف

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

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

ليكن $G=(V,E)$ رسم. الدارة هي الممر الغير خالي $(e_{1},e_{2},\ldots ,e_{n})$ والذي متتابعة رؤوسه هي $(v_{1},v_{2},\ldots ,v_{n},v_{1})$ [1] .

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

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

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

ليكن

G=(V,E)

رسم موجه. الدارة الموجهه هي الطريق موجه غير خالي المعرف بالمتتابعة

(e_{1},e_{2},\ldots ,e_{n})

والذي متتابعة الرؤوس له هي

(v_{1},v_{2},\ldots ,v_{n},v_{1})

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

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

في هذا الرسم موضح دورة باللون الأخضر (

A-B-C-D-E-F-A

) هي دورة بدون وتر . بينما الدورة باللون الأحمر (

G-H-I-J-K-L-G

) ليست وذلك بسبب إحتوائها على الوتر

K-I

.

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

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

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

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

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

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

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

مراجع

Bender & Williamson 2010، صفحة 164.

بوابة رياضيات
بوابة علم الحاسوب

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[FOOTNOTEBenderWilliamson2010164-1] Bender & Williamson 2010، صفحة 164.