نواصل دروس بحوث العمليات للأستاذ كعــرار يوســــف ,مع الدرس الثاني لمادة Recherche Opérationnelle االدرس بعنوان البيانات Les graphes .
الموضوع: البيانات (Les Graphes)
مفهوم البيان
البيان G عبارة عن مجموعة Vمن العناصر تسمى رؤوس مع مجموعة E من الثنائيات(أزواج) من رؤوس البيان يطلق عليها اسم حواف.
- a,b,c,d,e تسمى رؤوس للبيان G1
- {𝑎, 𝑏}, {𝑎, 𝑐}, {𝑑, 𝑒}حواف
- الحافة {e,e} تسمى حلقة او لفة.
التجاور:
- نقول عن رأسين أنهما متجاوران إذا كانت هناك حافة واقعة عليهما، أي أن الرأسين 𝑎و𝑏 متجاوران
إذا كانت e ={e,e} حافة.
- نقول عن حافتين أنهما متجاورتان إذا كان لديهما رأس مشترك.
- كل الرؤوس المتصلة عبر حواف بالرأس 𝑎 تسمى جوار للرأس 𝑎 و يرمز له ب 𝑁(a) .
- نقول عن الرأس الذي لا يقع على أية حافة رأسا منعزلا.
الرتبة و الدرجة:
- § رتبة بيان هي عدد رؤوسه أي عدد عناصر المجموعة 𝑉.
- § تعرف درجة رأس بأنها عدد الحافات الواقعة على هذا الرأس مع احتساب اللفة مرتين و يرمز لها ب p(a)
أنواع البيان:هناك نوعان من البيان:
البيان المضاعف:
نقول عن بيان أنه مضاعف إذا وجدت أكثر من حافة تصل بين نفس الرأسين (حافة مضاعفة)
البيان البسيط (Graphe Simple):
البيان البسيط هو الذي كل حوافه بسيطة (ليست مضاعفة) ولا يحتوي على لفات.
البيان الموجه (Graphe Orienté):
- البيان الموجه هو البيان الذي حوافه موجهة أي حوافه عبارة عن زوج مرتب من الرؤوس.
- يطلق على الحافة الموجهة اسم قوس.
- يطلق على الحافة الموجهة 𝑒={a,a} لفة موجهة.
- إذا كانت 𝑒={a,a} حافة موجهة فإنه يطلق على الرأس 𝑎 رأس الابتداء و 𝑏 رأس الانتهاء.
- هندسيا، نضع سهم على كل حافة موجهة
يطلق على عدد الحافات الموجهة الخارجة من الرأس 𝑎 ب شبه الدرجة الخارجية و يرمز لها ب p+(a)، و يطلق على عدد الحافات الموجهة الداخلة إلى الرأس 𝑎 ب شبه الدرجة الداخلية و يرمز لها ب p-(a)و منه درجة 𝑎 تعطى ب:
P(a)=
p+(a)+ p-(a)ty
