إتقان موضوع بيان شطراني

في نظرية البيان في الرياضيات، يكون البيان شطرانيًا أو ذا فرعين (بالإنجليزية: Bipartite Graph) إذا أمكن تقسيم رؤوسه إلى مجموعتين







U





{\displaystyle U}



و







V





{\displaystyle V}



حيث يكون أحد رؤوس أي ضلع في







U





{\displaystyle U}



والرأس الآخر في







V





{\displaystyle V}



. مجموعات الرؤوس







U





{\displaystyle U}



و







V





{\displaystyle V}



عادة تسمى اجزاء الرسم.

بصيغه أخرى، البيان الشطراني هو الرسم الذي لايحتوي على أي دارات فرديه. أي مجموعتين







U





{\displaystyle U}



و







V





{\displaystyle V}



ممكن ان تلون بلونين حسب مسألة تلوين البيان عن طريق تلوين رؤوس الجزء







U





{\displaystyle U}



بالأزرق مثلا وجميع رؤوس الجزء







V





{\displaystyle V}



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

بالعادة الرمز







G

=

(

U

∪

V

,

E

)





{\displaystyle G=(U\cup V,E)}



يرمز لبيان شطراني والذي له التجزئة







U





{\displaystyle U}



و







V





{\displaystyle V}



في حين المجموعة







E





{\displaystyle E}



ترمز لمجموعة اضلاع الرسم. إذا كان البيان شطرانيًا غير مترابط، فمن الممكن أن يكون له أكثر من تجزئة. في هذه الحالة الرمز







G

=

(

U

∪

V

,

E

)





{\displaystyle G=(U\cup V,E)}



مفيد لتوضيح تجزئة معينه والتي ممكن ان تكون مهمه في تطبيق ما.

إذا كان









|



U



|



=



|



V



|







{\displaystyle |U|=|V|}



والذي يعني مجموعتين جزئيتين لهما نفس عدد العناصر (cardinality) فإن







G





{\displaystyle G}



تسمى البيان المتوازن الشطراني (balanced bipartite graph). إذا كانت جميع الرؤوس في جانب معين من التجزئة لها نفس الدرجة، فإن







G





{\displaystyle G}



تسمى ثنائي منتظم (biregular).