دروس تكوين مهني عن بعد /دروس تقني سامي في تسيير الموارد البشرية cnepd

دائمًا مع دروس بحوث العمليات للأستاذ كعــرار يوســــف , مع الدرس الثالث لمادة Recherche Opérationnelle الدرس بعنوان المسارات في نظرية البيانات.

الموضوع: المسارات في نظرية البيانات

1. تعاريف أساسية:

في نظرية البيانات، نستخدم عدة مفاهيم لوصف العلاقات بين العناصر. إليك بعض التعريفات الأساسية:

• المسلك (Chaine):

هو سلسلة من العقد والأضلاع (أو الأقواس في حالة البيانات الموجهة). يبدأ المسلك من عقدة بداية (x0) وينتهي بعقدة نهاية (xP). الأضلاع تربط بين العقد المتتالية في المسلك. مثال: إذا كان لدينا العقد A, B, C والأضلاع AB, BC، فإن المسلك من A إلى C هو A -> B -> C.

• الحلقة (Cycle):

هي مسلك تبدأ وتنتهي بنفس العقدة. مثال: في المثال السابق، إذا أضفنا الضلع CA، فإن A -> B -> C -> A تُشكل حلقة.

• المسار (Chemin):

في البيانات الموجهة، المسار هو سلسلة من العقد والأقواس الموجهة. يختلف عن المسلك في أن الأقواس لها اتجاه محدد. يبدأ المسار من عقدة بداية (x0) وينتهي بعقدة نهاية (xP). القوس يربط بين العقدتين (xi-1) و (xi) في المسار. مثال: إذا كان لدينا العقد A, B, C والأقواس A -> B, B -> C، فإن المسار من A إلى C هو A -> B -> C.

• الدورة (Circuit):

هي مسار تبدأ وتنتهي بنفس العقدة. مثال: في المثال السابق، إذا أضفنا القوس C -> A، فإن A -> B -> C -> A تُشكل دورة.

• المسلك/المسار البسيط (Simple):

هو مسلك أو مسار لا يستخدم نفس الضلع (أو القوس) أكثر من مرة.

• المسلك/المسار الجزئي (Elémentaire):

هو مسلك أو مسار لا يستخدم نفس العقدة أكثر من مرة. (المسلك الجزئي هو دائمًا مسلك بسيط).

لنفترض أن لدينا عقدة (x) في بيان.

• A(x): مجموعة العقد التي يمكن الوصول إليها من العقدة (x). تسمى "مجموعة الأصول" أو "المصادر" أو "الأسلاف".
• D(x): مجموعة العقد التي يمكن الوصول إليها من العقدة (x) من خلال مسار. تسمى "مجموعة الفروع" أو "المصبات" أو "الأحفاد".

مثال: إذا كانت لدينا عقد (1, 2, 3, 4, 5, 6, 7) وكان لدينا مسارات: 1 -> 2, 2 -> 3, 3 -> 4, 4 -> 6, 4 -> 7, 6 -> 2, 5 -> 2, 5 -> 4, 6 -> 7، إذن:

• A(3) = {1, 2, 6, 4, 7, 5}
• D(3) = {4, 6, 7}
• D(5) = {2, 3, 4, 6, 7}
• A(5) = {}

2. الاتصال في البيان (Connexité d’un graphe):

لنفترض أن لدينا بيان G(X, U)، حيث X هي مجموعة العقد و U هي مجموعة الأضلاع (أو الأقواس). نعرّف العلاقة R على X كالتالي:

إعلان منتصف المقال

y R x إذا كان x = y أو يوجد مسلك من y إلى x.

R هي علاقة تكافؤ. هذه العلاقة تقسم مجموعة العقد X إلى أقسام متكافئة. كل قسم يمثل مجموعة جزئية من العقد التي تولد بيانًا جزئيًا يسمى مركبة الاتصال (composante connexe) من G.

3. الاتصال بشدة (Forte connexité):

نستخدم نفس البيان G(X, U) ونعرّف علاقة ثنائية جديدة R على X كالتالي:

y R x إذا كان x = y أو يوجد مسار من y إلى x و مسار من x إلى y.

R هي أيضًا علاقة تكافؤ. هذه العلاقة تقسم مجموعة X إلى أقسام متكافئة. كل قسم يمثل مجموعة عقد، وينتج عنه بيان جزئي يسمى مركبة الاتصال بشدة (composante fortement connexe) للبيان G.

• بيان متصل بشدة: هو بيان يحتوي على مركبة اتصال بشدة واحدة فقط.
• C(a): نرمز إلى مركبة الاتصال بشدة التي تحتوي على العقدة a.

4. خوارزمية البحث عن مركبة الاتصال بشدة تحتوي على العقدة a

لدينا بيان موجه G(X, U). لكل عقدة x، نحدد مجموعتين:

• D(x): مجموعة الفروع (العقد التي يمكن الوصول إليها من x).
• A(x): مجموعة الأصول (العقد التي يمكن الوصول إلى x منها).

مبدأ الخوارزمية:

من العقدة a، نحسب مركبة الاتصال بشدة (CFC) التي تنتمي إليها a:

• احسب مجموعة الفروع (D(a)).
• احسب مجموعة الأصول (A(a)).
• CFC هي تقاطع D(a) و A(a). ( أي العقد الموجودة في كلا المجموعتين).

المعطيات:

مدخلات:

• X: مجموعة العقد (n عقدة).
• U: مجموعة الأقواس (m قوسًا).
• a: عقدة من X (تسمى الجذر).

مخرجات:

• CFC: مجموعة جزئية من X. البيان الجزئي الناتج يمثل مركبة الاتصال بشدة.

بالإضافة إلى:

• i, j: متغيرات للعقد.
• Marque: جدول من n عنصر منطقي (يستخدم لتمييز العقد التي تمت زيارتها).
• A, D: مجموعات جزئية من X، تمثل مجموعات الفروع والأصول للجذر a.

الخوارزمية (سوف تحتاج إلى إدراج الخوارزمية هنا بشكل مفصل - مثلاً: بشكل نقاط أو كود شبهي)