دائما مع دروس بحوث العمليات للأستاذ كعــرار يوســــف ,مع الدرس الثالث لمادة Recherche Opérationnelle االدرس بعنوان المسارات في نظرية البيانات.
الموضوع :المسارات في نظرية البيانات
1. تعاريف :
- مسلك(chaine ) :مسلك من x0 الى xP هو متتالية متناوبة من العقد و الاضلاع او الاقواس بحيث مهما يكن i اطراف ei هما xi و xi-1 , و العقد x0 و xP هما اطراف المسلك
- حلقة(cycle ) :هي مسلك بحيث اطرافه متساوية (نفسها)
- مسار(chemin ):مسار منx0 الى xP هو متتالية متناوبة من العقد والاقواس بحيث مهما يكنi I(ui)= xi-1و T(ui)= xi, و العقد x0 و xP هما اطراف المسار
- الدورة(circuit ) :هي مسار بحيث اطرافه متساوية
- مسلك(مسار,حلقة,دورة)هي بسيطة simple اذا كانت لا تستعمل نفس الاضلاع (اقواس) مرتين
- مسلك(مسار,حلقة,دورة)هي جزئية élémentaireاذا كانت لا تستعمل نفس العقدة مرتين
ملاحظة : مسلك جزئية هي مسلك بسيط
لنفرض ان العقدX x ,المجموعة التى يرمز لها بـA(x) (D(x) ) للعقد y ,x≠y بحيث يوجد مسار من y الى )x من x الى (y تدعى مجموعة اصول او خارج(ascendants))فروع او داخل (descendants)(
مثال: A(3)={1,2,6,4,7,5} ,D(3)={2,1,4,6,7}.D(5)={6,7,4,3,2,1}A(5)=
2. الاتصال في البيان (connexité d’un graphe) :
ليكن البيان G(X,U) ولتكن R علاقة ثنائية معرفة على Xبـ
y Rx x= yóاو يوجد مسلك من y الى x, R علاقة تكافؤ تقسم مجموعة X الى اقسام متكافئة , كل قسم هو مجموعة جزئية تولد بيان جزئي يدعى مركبة الاتصال(composante connexe) من G
3. الاتصال بشدة (Forte connexité):
ليكن البيان G(X,U) ولتكن R علاقة ثنائية معرفة على Xبـ
y Rx x= yóاو يوجد مسلك من y الى x و مسلك من x الى y, R علاقة تكافؤ تقسم مجموعة X الى اقسام متكافئة , كل قسم هو مجموعة العقد ينتج عنها بيان جزئي يدعى مركبة الاتصال بشدة للبيان
- G هو اتصال بشدة اذا كان يحتوى على مركبة واحدة من F.C
- ليكنX a ونرمز لها بC(a) لـC.F.C يحتوى على العقدة :a
4. خوارزمية البحث على مركبة الاتصال بشدة تحتوى على العقدة:a
ليكن G(X,U) بيان موجه ونعرف كل عقدة x بمجموعتين
- مجموعة الفروع ل D(x)={y
- مجموعة الاصول ل A(x)={y
مبدأها:
انطلاقا من العقدة a نحسب c.f.c الذي ينتمي اليه a :- حساب مجموعة فروع (D) a
- حساب مجموعة اصول (A)a
- c.f.c هو
المعطيات:
مدخلات:
- X مجموعة n تمثل العقد
- U مجموعة m بشكل (i,j)تمثل الاقواس او
- a تعرف عقدة من X تدعى الجذر
مخرجات :
- C.F.C مجموعة جزئيةX . البيان الجزئي يولد من هذه المجموعة التي تمثل مركبة المصلة بشدة
بالاضافة :
- I,j متغيرات العقد
- Marque جدول لـ nعنصر منطقي
- A,Dمجموعات جزئية لـ X تمثل مجموعة الفروع و الاصول للجدز a
