مخطط ثنائي

مخطط ثنائي

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

عند نمذجة العلاقات بين تصنيفين مختلفين من الاشياء فمن الممكن تمثيلها باستعمال المخططات الثنائية التجزئة. على سبيل المثال، مخطط لاعبي كرة القدم والاندية مع وجور ضلع بين لاعب ما ونادي معين في حالة كان اللاعب ينتمي لهذا النادي، وهو مثال بسيط لشبكة الانتماء (affiliation network). هذا النوع من المخططات ثنائية التجزئة التي تستعمل في تحليل الشبكات الاجتماعية. مثال آخر يبين استعمال المخططات ثنائية التجزئة في مسألة نمذجة السكك الحديدية، والتي مدخلاتها هي جدولة القطارات ومحطات وقوفها. الهدف من هذا النموذج هو إيجاد أصغر مجموعة ممكنه من محطات القطارات حيث كل قطار يعبر عالأقل محطة واحدة من مجموعة المحطات المختارة. هذه المسألة ممكن نمذجتها كمخطط ثنائي التجزئة الذي كل رأس بهذا المخطط يمثل محطة قطار وكل ضلع فيه يربط بين محطة الانطلاق والتوقف لقطار ما.

هنا مثال ثالث من المجال الاكاديمي المتعلق بالعملات (numismatics). العملات القديمه تصنع باستعمال طابعين ايجابين من التصاميم (وجة العملة وخلفها). المخطط المستعمل في إنتاج هذه العملات هو مخطط ثنائي التجزئة.

يوجد الكثير من الامثلة النظرية والتي منها

كل شجرة هي ثنائية التجزئة.

الرسومات ذو الدارات والتي بها عدد زوجي من الرؤوس هي ثنائية التجزئة.

كل مخطط مستو الذي جميع أوجهه لها طول زوجي هي ثنائية التجزئة. حالات خاصة من هذا المخطط هو grid graphs وsquaregraphs حيث كل وجه داخلي مكون من 4 أضلاع وكل رأس داخلي له أربعة أو أكثر من الرؤوس المجاورة.

نوع قريب جدا من هذا النوع هي crown graphs والمستخلصه من المخطط المكتمل ثنائي التجزئة بحذف أضلاع المطابقة المكتملة (perfect matching).

خواص المخطط ثنائي التجزئة

مميزات

المخططات ثنائية التجزئة ممكن ان تميز بعدة طرق مختلفة منها:

المخطط يكون ثنائي التجزئة إذا وفقط إذا كان لايحتوي على دارة فردية.

المخطط يكون ثنائي التجزئة إذا وفقط إذا كان 2-colorable ( أي أن عدد كروم chromatic number أقل من أو يساوي 2 ).

مجموعة القيم الذاتية (spectrum) لمخطط هو متماثل إذا وفقط إذا كان مخطط ثنائي التجزئة.

 

المراجع

areq.net

التصانيف

نظرية المخططات   العلوم التطبيقية   فيزياء