نبدا على بركة الله بنشر سلسلة جديدة من دروس بحوث العمليات للاستاذ للأستاذ كعــرار يوســــف

الدرس الأول لمادة بحوث العمليات لاختصاص تقني سامي قواعد البيانات

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

مقدمة:

نظرية المخططات أو نظرية البيانات هي نظرية في الرياضيات وعلوم الحاسب، تدرس خواص المخططات حيث يتم تمثيل مجموعة كائنات تدعى رؤوسا، ترتبط ببعضها بأضلاع وتدعى أحيانا أقواسا، يمكن أن تكون موجهة أي مزودة باتجاه (تستخدم الأسهم بدل الأضلاع) أو بدون اتجاه (أضلاع فقط).أصبحت هذه النظرية وسيلة مفضلة لنمدجة وحل المسائل.

أمثلة حالات نستطيع تمثيلها ببيان:

شبكة سكة حديدية.
شبكة هاتفية.
شبكة احياء مدينة.
شبكة تبادل تجاري.......الخ

تعريف البيان او الرسم (Graph):

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

رياضيا :

البيان (G) هو ثنائية (X,E) بشكل مجموعتين منفصلتين X={x1,x2,x3,……..xn}بحيث n>=1

وE={e1,e2,e3,....,em} بحيثm>=0 مثلا مهما يكنi , ei هو الزوج من X يعرف علاقة ثنائية تناظرية منX في X

مجموعة X تدعى مجموعة العقد Sommets و مجموعة E تدعى مجموعة وصلات أو أقواس أو أضلاع arêtes

2. تطبيقات نظرية البيانات :

لدينا ملتقى يحتوى على 6 محاضرات معنيين بهم 5 حضور مختصين وكل محاضرة مدتها يوم و وكل محاضرة مشتركة في مجموعة حضور مخصصة كما يلي :

من اجل حل اقتصادي منظمو الملتقى يسعون الى تقليص مدة الملتقى فهل يمكن ذلك؟

يمكننا تمثيل هذه الحالة ببيان بطريقة التالية :

كل عقدة تمثل محاضرة (6 عقد) ونربط عقدتين ببعض إذا كان للمؤتمرين حضور واحد على الأقل مشترك

3. مفاهيم أساسية:

بعض المفاهيم:

لدينا الضلع e (e=xy) العقد x,y تسمى أطراف الضلع e
اذا كان x=y يسمى حلقة

يسمى الضلعين متوازيين Parallèles اذا كان لهما نفس الأطراف , مجموعة الأضلاع المتوازية تسمى الأضلاع المتعددة arêtes multiple وفي هذه الحالة يسمى G بيان متعدد Multigraph

يسمى البيان بسيط إذا لم يحتوى على حلقات و لا أضلاع المتعددة

عدد العقد في البيان تسمى رتبة البيان Ordre du Graphe

البيان التام Graphe Complet ذو الرتبة n هو بيان بسيط و يحتوى على ضلع بين كل زوج من العقد يرمز لها بkn

العقدة xÎX واقعة (incident ) على الضلع eÎE اذا كان x هو طرف e

عقدتين(ضلعين) يقال متجاورين adjacent لأنهما يرتكزان على نفس ضلع (نفس العقدة)

مجموعة العقد المجاورة للعقدة x تسمى مجموعة voisins جيران x و نرمزلها بــ v(x)

المجموعة الجزئية للعقد المتجاورة زوجا زوجا تدعى مستقر stable

المجموعة الجزئية للعقد غير المتجاورة زوجا زوجا تدعى العصبة clique

مجموعة الجزئية للأضلاع غير المجاورة زوجا زوجا تدعى الازواج couplage

مثال:

3.2. تمثيل بالمصفوفة :
يمكننا تمثيل البيان بمصفوفة معرفة كما يلي :
أ. مصفوفة التجاور:
لتكن المصفوفة ] n x n A(G)=[aij حيث aij هو عدد الأضلاع متعلقة ب xiو yj كأطراف
e2

ب. مصفوفة الوقوع :
هي المصفوفة n x m يرمز لها بB(G) حيث B(G)=[bij]حيث bij هو عدد مرات ارتكاز العقدة xi على الضلعej

3.3. درجة عقدة X:
يرمز لها ب dg(x) وهي عدد الأضلاع المرتكزة علىx و حيث يتم احتساب الحلقة مرتين ويعرف بـ

ملاحظات:
إذا كان G بسيط معناه اكبر درجة

إذا كان d(x)=0 معناه x يدعى عقدة معزولة isolé
إذا كان d(x)=1 معناه x يدعى عقدة متعلقة Pendant
نقول بيان منظم اذا كان البيان يدعى منتظم-Kبديهية: من أجل كل بيان G(X,E) اذن

خلاصة :
في بيان عدد العقد ذات الدرجة الفردية هو زوجي
1.4. البيان المتمم :

G بيان بسيط المتمم ل G يرمز له بـ
خلاصة :

5.3. مفهمم البين الجزئي
ليكن G(X,E) هو بيان و مرافق بمجموعة جزئية
- نقول H(Y,F) هو بيان جزئي لـGاذا اطراف موجودة في Y
- إذا كان F يشكل كل أضلاع للاطراف الموجودة في Y معناه H يدعى البيان الجزئي المختزل لـG من Y ويرمز له بـ
- Gyونفس الشئ يدعى البيان الجزئي المختزل من F ويرمز له ب G[F] , البيان الجزئي لــGمن مجموعة الأضلاع F
- و مجموعة العقد مشكل بأطراف الأضلاع F