ما هو الرسم البياني ثنائي الأطراف؟ - تعريف من techopedia

التعريف - ماذا يعني Bipartite Graph؟

الرسم البياني ثنائي الأطراف هو رسم بياني يمكن فيه تقسيم مجموعة من رؤوس الرسم البياني إلى مجموعتين مستقلتين ، ولا يوجد رأسان للرسم البياني داخل نفس المجموعة. بمعنى آخر ، يمكن اعتبار الرسوم البيانية ثنائية الأطراف مساوية لرسوم بيانية ملونة. غالبًا ما تستخدم الرسوم البيانية ثنائية القطبية في علاقات النمذجة ، خاصة بين فئتين منفصلتين بالكامل من الكائنات.

يُعرف الرسم البياني ثنائي الأطراف أيضًا باسم الرسم البياني.

يوضح Techopedia Bipartite Graph

يحتوي الرسم البياني ثنائي الأطراف على مجموعتين من الرؤوس ، على سبيل المثال A و B ، مع إمكانية أنه عند رسم حافة ، يجب أن يكون الاتصال قادراً على الاتصال بين أي قمة في A إلى أي قمة في B. إذا كان الرسم البياني لا يحتوي على أي دورة فردية (عدد القمم في الرسم البياني غريب) ، ثم طيفه متماثل. يجب أن يكون الرقم اللوني ، وهو الحد الأدنى لعدد الألوان المطلوبة لتلوين القمم بدون رؤوس متجاورة تشترك في نفس الألوان ، أقل من أو يساوي اثنين في حالة رسم بياني ثنائي الأطراف. جميع أنواع الرسوم البيانية الحلقية (الرسوم البيانية التي لا تحتوي على دورات بيانية) ، هي أمثلة على الرسوم البيانية ثنائية القطب. يُعتبر الرسم البياني الدوري ثنائي الطرف إذا كانت جميع الدورات المعنية ذات طول متساوٍ. وفقًا لنظرية تلوين خط Koning ، فإن جميع الرسوم البيانية ثنائية الأطراف هي رسوم بيانية من الدرجة الأولى.

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