بيان شطراني

في نظرية البيان في الرياضيات، يكون البيان شطرانيًا^[1]^[2] أو ذا فرعين^[1] (الإنجليزية: Bipartite Graph) إذا أمكن تقسيم رؤوسه إلى مجموعتين $U$ و $V$ حيث يكون أحد رؤوس أي ضلع في $U$ والرأس الآخر في $V$ . مجموعات الرؤوس $U$ و $V$ عادة تسمى اجزاء الرسم.

بصيغه أخرى، البيان الشطراني هو الرسم الذي لايحتوي على أي دارات فرديه.^[3]^[4] أي مجموعتين $U$ و $V$ ممكن ان تلون بلونين حسب مسألة تلوين البيان عن طريق تلوين رؤوس الجزء $U$ بالأزرق مثلا وجميع رؤوس الجزء $V$ باللون الأخضر. بالتالي كل ضلع له طرفين بلونين مختلفين وهو المطلوب في مسألة تلوين البيانات.^[5]^[6] بالمقابل، من المستحيل تلوين أي نوع اخر من البيانات الغير ثنائية التجزئة بلونين فقط. مثال على ذلك تلوين رؤوس المثلث، والتي يمكن تلوين أحد الرؤوس بالأزرق ورأس اخر بالاخضر لكن الراس الثالث مرتبط بالرأسين الازرق والاخضر مما يستحيل تلوينه بأحد هذين اللونين. بالعادة الرمز $G=(U\cup V,E)$ يرمز لبيان شطراني والذي له التجزئة $U$ و $V$ في حين المجموعة $E$ ترمز لمجموعة اضلاع الرسم. إذا كان البيان شطرانيًا غير مترابط، فمن الممكن أن يكون له أكثر من تجزئة.^[7] في هذه الحالة الرمز $G=(U\cup V,E)$ مفيد لتوضيح تجزئة معينه والتي ممكن ان تكون مهمه في تطبيق ما.

إذا كان $|U|=|V|$ والذي يعني مجموعتين جزئيتين لهما نفس عدد العناصر (cardinality) فإن $G$ تسمى البيان المتوازن الشطراني (balanced bipartite graph).^[6] إذا كانت جميع الرؤوس في جانب معين من التجزئة لها نفس الدرجة، فإن $G$ تسمى ثنائي منتظم (biregular).

أمثلة

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

هنا مثال ثالث من المجال الاكاديمي المتعلق بالعملات (numismatics). العملات القديمه تصنع باستخدام طابعين ايجابين من التصاميم (وجة العملة وخلفها). البيان المستخدم في إنتاج هذه العملات هو بيان شطراني.^[10]

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

كل شجرة هي ثنائية التجزئة.^[5]
الرسومات ذو الدارات والتي بها عدد زوجي من الرؤوس هي ثنائية التجزئة.^[5]
كل بيان مستو الذي جميع أوجهه لها طول زوجي هي ثنائية التجزئة.^[11] حالات خاصة من هذا البيان هو grid graphs وsquaregraphs حيث كل وجه داخلي مكون من 4 أضلاع وكل رأس داخلي له أربعة أو أكثر من الرؤوس المجاورة.^[12]
البيان المكتمل شطراني والذي به $m$ و $n$ من الرؤوس، يرمز لهذا البيان بالرمز $K_{n,m}$ هو البيان الشطراني $G=(U\cup V,E)$ حيث $U$ و $V$ هما مجموعات منفصلة من ذو الاحجام $n$ و $m$ على التوالي. مجموعة أضلاعه $E$ تربط كل رأس من $U$ مع جميع عناصر $V$ . بالتالي عدد اضلاع البيان $K_{n,m}$ هو $n\times m$ . نوع قريب جدا من هذا النوع هي crown graphs والمستخلصه من البيان المكتمل الشطراني بحذف أضلاع المطابقة المكتملة (perfect matching).^[13]
hypercube graphs و partial cubes و mediam graphs هي ثنائية التجزئة. في هذه البيانات، ممكن تسمية الرؤوس حسب bitvectors ، بحيث يكون كل رأسين متجاورين إذا وفقط إذا كان bivectors المقابلة مختلف بموضع وحيد فقط.

خواص البيان الشطراني

مميزات

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

البيان يكون شطرانيًا إذا وفقط إذا كان لايحتوي على دارة فردية.^[14]
البيان يكون شطرانيًا إذا وفقط إذا كان 2-colorable (أي أن عدد كروم chromatic number أقل من أو يساوي 2).^[6]
مجموعة القيم الذاتية (spectrum) لبيان هو متماثل إذا وفقط إذا كان بيان شطرانيًا.^[15]

نظرية König's والبيان الشطراني

الدرجة

لكل رأس $v$ عدد من الرؤوس المجاورة له وهذا العدد هو درجة الرأس والتي يرمز له بالرمز $deg(v)$ . معادلة مجموع درجات رؤوس البيان الشطراني هي

$\sum _{v\in V}deg(v)=\sum _{u\in U}deg(u)=|E|.$

متتابعة الدرجة لبيان شطراني هي متتابعتين مرتبة تحتوي على درجات رؤوس $U$ و $V$ . على سبيل المثال في البيان المكتمل الشطراني $K_{3,5}$ له متتابعة الدرجة $(5,5,5)$ و $(3,3,3,3,3)$ . البيانات ثنائية التجزئة الاحادية التشاكل لها نفس متتابعة الدرجات، لكن بالمقابل متتابعة الدرجات بصفة عامة ليست مرتبطة بشكل خاص لبيان ثنائي تجزئة معين. في بعض الحالات من الممكن أن تكون البيانات ثنائية التجزئة الغير احادية التشاكل لها نفس متتابعة الدرجة.

مسألة bipartite realization problem هي مسألة إيجاد بيان شطراني بسيط له متتابعة درجات تكون قائمتين معطاه من الاعداد الطبيعية.

مراجع

1 2 موفق دعبول؛ بشير قابيل؛ مروان البواب؛ خضر الأحمد (2018)، معجم مصطلحات الرياضيات (بالعربية والإنجليزية)، دمشق: مجمع اللغة العربية بدمشق، ص. 61، OCLC:1369254291، QID:Q108593221
↑ أفرام بوروفسكي؛ جوناثان بوروين (1995)، معجم الرياضيات: إنكليزي - فرنسي - عربي، المعاجم الأكاديمية المتخصصة (بالعربية والإنجليزية والفرنسية)، ترجمة: علي مصطفى بن الأشهر، مراجعة: محمد الدبس، بيروت: أكاديميا إنترناشيونال، ص. 69، OCLC:822262215، QID:Q121833036
↑ Reinard Diestel، Reinard (2005). Graph Theory, Grad. Texts in maths. Springer – عبر http://diestel-graph-theory.com/. {{استشهاد بكتاب}}: روابط خارجية في |عبر= (مساعدة)
↑ Asratian، Armen S.؛ Denley، Tristan M. J.؛ Häggkvist، Roland (1998)، Bipartite Graphs and their Applications، Cambridge Tracts in Mathematics، Cambridge University Press، ج. 131، ISBN:9780521593458
1 2 3 Scheinerman، Edward R. (2012)، Mathematics: A Discrete Introduction (ط. 3rd)، Cengage Learning، ص. 363، ISBN:9780840049421، مؤرشف من الأصل في 2023-03-26.
1 2 3 Asratian, Denley & Häggkvist (1998), p. 7.
↑ Chartrand، Gary؛ Zhang، Ping (2008)، Chromatic Graph Theory، Discrete Mathematics And Its Applications، CRC Press، ج. 53، ص. 223، ISBN:9781584888000، مؤرشف من الأصل في 2023-03-26.
↑ Wasserman، Stanley؛ Faust، Katherine (1994)، Social Network Analysis: Methods and Applications، Structural Analysis in the Social Sciences، Cambridge University Press، ج. 8، ص. 299–302، ISBN:9780521387071، مؤرشف من الأصل في 2025-02-15.
↑ Niedermeier، Rolf (2006). Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications). Oxford. ص. 20-21. ISBN:978-0-19-856607-6.
↑ Bracey، Robert (2012). "On the Graphical Interpreation of Herod's Coinage in Judaea and Rome in Coins". ص. 65–84.
↑ Soifer، Alexander (2008)، The Mathematical Coloring Book، Springer-Verlag، ص. 136–137، ISBN:978-0-387-74640-1. This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper of Alfred Kempe containing a false proof of the four color theorem.
↑ Asratian, Denley & Häggkvist (1998), p. 11.
↑ Archdeacon، D.؛ Debowsky، M.؛ Dinitz، J.؛ Gavlas، H. (2004)، "Cycle systems in the complete bipartite graph minus a one-factor"، Discrete Mathematics، ج. 284، ص. 37–43، DOI:10.1016/j.disc.2003.11.021.
↑ Asratian, Denley & Häggkvist (1998), Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by Dénes Kőnig. For infinite graphs, this result requires the axiom of choice.
↑ Biggs، Norman (1994)، Algebraic Graph Theory، Cambridge Mathematical Library (ط. 2nd)، Cambridge University Press، ص. 53، ISBN:9780521458979، مؤرشف من الأصل في 2024-06-13.

[:2-1] 1 2 موفق دعبول؛ بشير قابيل؛ مروان البواب؛ خضر الأحمد (2018)، معجم مصطلحات الرياضيات (بالعربية والإنجليزية)، دمشق: مجمع اللغة العربية بدمشق، ص. 61، OCLC:1369254291، QID:Q108593221

[2] أفرام بوروفسكي؛ جوناثان بوروين (1995)، معجم الرياضيات: إنكليزي - فرنسي - عربي، المعاجم الأكاديمية المتخصصة (بالعربية والإنجليزية والفرنسية)، ترجمة: علي مصطفى بن الأشهر، مراجعة: محمد الدبس، بيروت: أكاديميا إنترناشيونال، ص. 69، OCLC:822262215، QID:Q121833036

[3] Reinard Diestel، Reinard (2005). Graph Theory, Grad. Texts in maths. Springer – عبر http://diestel-graph-theory.com/. {{استشهاد بكتاب}}: روابط خارجية في |عبر= (مساعدة)

[4] Asratian، Armen S.؛ Denley، Tristan M. J.؛ Häggkvist، Roland (1998)، Bipartite Graphs and their Applications، Cambridge Tracts in Mathematics، Cambridge University Press، ج. 131، ISBN:9780521593458

[:0-5] 1 2 3 Scheinerman، Edward R. (2012)، Mathematics: A Discrete Introduction (ط. 3rd)، Cengage Learning، ص. 363، ISBN:9780840049421، مؤرشف من الأصل في 2023-03-26.

[:1-6] 1 2 3 Asratian, Denley & Häggkvist (1998), p. 7.

[7] Chartrand، Gary؛ Zhang، Ping (2008)، Chromatic Graph Theory، Discrete Mathematics And Its Applications، CRC Press، ج. 53، ص. 223، ISBN:9781584888000، مؤرشف من الأصل في 2023-03-26.

[8] Wasserman، Stanley؛ Faust، Katherine (1994)، Social Network Analysis: Methods and Applications، Structural Analysis in the Social Sciences، Cambridge University Press، ج. 8، ص. 299–302، ISBN:9780521387071، مؤرشف من الأصل في 2025-02-15.

[9] Niedermeier، Rolf (2006). Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications). Oxford. ص. 20-21. ISBN:978-0-19-856607-6.

[10] Bracey، Robert (2012). "On the Graphical Interpreation of Herod's Coinage in Judaea and Rome in Coins". ص. 65–84.

[11] Soifer، Alexander (2008)، The Mathematical Coloring Book، Springer-Verlag، ص. 136–137، ISBN:978-0-387-74640-1. This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper of Alfred Kempe containing a false proof of the four color theorem.

[12] Asratian, Denley & Häggkvist (1998), p. 11.

[13] Archdeacon، D.؛ Debowsky، M.؛ Dinitz، J.؛ Gavlas، H. (2004)، "Cycle systems in the complete bipartite graph minus a one-factor"، Discrete Mathematics، ج. 284، ص. 37–43، DOI:10.1016/j.disc.2003.11.021.

[14] Asratian, Denley & Häggkvist (1998), Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by Dénes Kőnig. For infinite graphs, this result requires the axiom of choice.

[15] Biggs، Norman (1994)، Algebraic Graph Theory، Cambridge Mathematical Library (ط. 2nd)، Cambridge University Press، ص. 53، ISBN:9780521458979، مؤرشف من الأصل في 2024-06-13.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]