نواصل دروس بحوث العمليات للأستاذ كعــرار يوســــف , مع الدرس الثاني لمادة Recherche Opérationnelle الدرس بعنوان البيانات Les graphes.
الموضوع: البيانات (Les Graphes)
مفهوم البيان (Graphe):
البيان (Graphe) هو تمثيل رياضي يتكون من:
- مجموعة من الرؤوس (Sommets)، والتي تمثل العناصر أو الكيانات.
- مجموعة من الحواف (Arêtes)، والتي تربط بين الرؤوس وتعبر عن العلاقات بينها.
مثال: في البيان G1:
- الرؤوس: a, b, c, d, e
- الحواف: {a, b}, {a, c}, {d, e}
- الحلقة (Boucle): الحافة {e, e} تسمى حلقة (أو لفة).
التجاور (Adjacence):
- الرؤوس المتجاورة: نقول عن رأسين أنهما متجاوران إذا كانت هناك حافة تربطهما. أي، الرأسين a و b متجاوران إذا كانت الحافة {a, b} موجودة.
- إذا كانت الحافة e = {e, e} حلقة، فإن الرأس e متجاور مع نفسه.
- الحواف المتجاورة: حافتان متجاورتان إذا كان لديهما رأس مشترك.
- جوار الرأس (Voisinage): كل الرؤوس المتصلة عبر حواف بالرأس a تسمى جوار الرأس a، ونرمز له بـ N(a).
- الرأس المعزول: هو الرأس الذي لا يقع على أية حافة.
الرتبة والدرجة:
- رتبة البيان (Ordre): هي عدد رؤوسه، أي عدد عناصر المجموعة V.
- درجة الرأس (Degré): هي عدد الحواف التي تقع على هذا الرأس. إذا كان هناك حلقة (لفة) على الرأس، يتم احتسابها مرتين. نرمز لدرجة الرأس a بـ p(a).
أنواع البيانات:
- البيان المضاعف (Graphe multiple): هو بيان توجد فيه أكثر من حافة تصل بين نفس الرأسين (حافة مضاعفة).
- البيان البسيط (Graphe Simple): هو بيان كل حوافه بسيطة (غير مضاعفة) ولا يحتوي على لفات (حلقات).
البيان الموجه (Graphe Orienté):
- البيان الموجه هو البيان الذي تكون حوافه موجهة، أي أن كل حافة عبارة عن زوج مرتب من الرؤوس.
- يُطلق على الحافة الموجهة اسم قوس (Arc).
- يُطلق على الحافة الموجهة 𝑒 = {a, a} لفة موجهة.
- إذا كانت 𝑒 = {a, b} حافة موجهة، فإن الرأس a هو رأس الانطلاق (Origine)، والرأس b هو رأس الوصول (Extrémité).
- هندسيًا، نضع سهمًا على كل حافة موجهة.
يطلق على عدد الحافات الموجهة الخارجة من الرأس a بشبه الدرجة الخارجية (p+(a))، ويطلق على عدد الحافات الموجهة الداخلة إلى الرأس a بشبه الدرجة الداخلية (p-(a)). إذن، درجة الرأس a تُعطى بـ:
P(a) = p+(a) + p-(a)
