مخطط ثنائي

في نظرية المخططات في الرياضيات , يكون المخطط او الرسم البياني ثنائي التجزئة (بالإنجليزية: Bipartite Graph) إذا أمكن تقسيم رؤوسه إلى مجموعتين $U$ و $V$ حيث يكون أحد رؤوس اي ضلع في $U$ والرأس الاخر في $V$ . مجموعات الرؤوس $U$ و $V$ عادة تسمى اجزاء الرسم.

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

بصيغه اخرى، الرسم ثنائي التجزئة هو الرسم الذي لايحتوي على اي دارات فرديه.^[1]^[2]

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

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

محتويات

1 أمثلة
- 1.1 يوجد العديد من الامثلة النظرية والتي منها
2 خواص المخطط ثنائي التجزئة
3 خوارزميات
4 تطبيقات إضافية
5 المزيد
6 مراجع

أمثلة[عدل]

مخطط ثنائي التجزئة جزء منه يحتوي على 5 رأس والجزء الاخر به 3 رأس.

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

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

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

كل شجرة هي ثنائية التجزئة.^[3]
الرسومات ذو الدارات والتي بها عدد زوجي من الرؤوس هي ثنائية التجزئة.^[3]
كل مخطط مستو الذي جميع أوجهه لها طول زوجي هي ثنائية التجزئة.^[9] حالات خاصة من هذا المخطط هو grid graphs وsquaregraphs حيث كل وجه داخلي مكون من ٤ أضلاع وكل رأس داخلي له أربعة او أكثر من الرؤوس المجاورة.^[10]
المخطط المكتمل ثنائي التجزئة والذي به $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).^[11]
hypercube graphs و partial cubes و mediam graphs هي ثنائية التجزئة. في هذه المخططات، ممكن تسمية الرؤوس حسب bitvectors ، بحيث يكون كل رأسين متجاورين إذا وفقط إذا كان bivectors المقابلة مختلف بموضع وحيد فقط.

خواص المخطط ثنائي التجزئة[عدل]

مميزات[عدل]

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

المخطط يكون ثنائي التجزئة إذا وفقط إذا كان لايحتوي على دارة فردية.^[12]
المخطط يكون ثنائي التجزئة إذا وفقط إذا كان 2-colorable ( أي أن عدد كروم chromatic number أقل من أو يساوي 2 ).^[4]
مجموعة القيم الذاتية (spectrum) لمخطط هو متماثل إذا وفقط إذا كان مخطط ثنائي التجزئة.^[13]

نظرية 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 هي مسألة إيجاد مخطط ثنائي التجزئة بسيط له متتابعة درجات تكون قائمتين معطاه من الاعداد الطبيعية.

العلاقة مع المخططات الزائدي و المخططات الموجة[عدل]

خوارزميات[عدل]

اختبار التجزئة الثنائية[عدل]

إنتقالية الدارات الفردية Odd cycle transveral[عدل]

المطابقة Matching[عدل]

تطبيقات إضافية[عدل]

مراجع[عدل]

^ 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، 131، Cambridge University Press، ISBN 9780521593458
↑ ^أ ^ب ^ت Scheinerman، Edward R. (2012)، Mathematics: A Discrete Introduction (الطبعة 3rd)، Cengage Learning، صفحة 363، ISBN 9780840049421 .
↑ ^أ ^ب ^ت Asratian, Denley & Häggkvist (1998), p. 7.
^ Chartrand، Gary؛ Zhang، Ping (2008)، Chromatic Graph Theory، Discrete Mathematics And Its Applications، 53، CRC Press، صفحة 223، ISBN 9781584888000 .
^ Wasserman، Stanley؛ Faust، Katherine (1994)، Social Network Analysis: Methods and Applications، Structural Analysis in the Social Sciences، 8، Cambridge University Press، صفحات 299–302، ISBN 9780521387071 .
^ 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 (1–3): 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 .

في كومنز صور وملفات عن: مخطط ثنائي

هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. شارك في تحريرها.

[1] Reinard Diestel، Reinard (2005). Graph Theory, Grad. Texts in maths. Springer – عبر http://diestel-graph-theory.com/.

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

[:0-3] أ ^ب ^ت Scheinerman، Edward R. (2012)، Mathematics: A Discrete Introduction (الطبعة 3rd)، Cengage Learning، صفحة 363، ISBN 9780840049421 .

[:1-4] أ ^ب ^ت Asratian, Denley & Häggkvist (1998), p. 7.

[5] Chartrand، Gary؛ Zhang، Ping (2008)، Chromatic Graph Theory، Discrete Mathematics And Its Applications، 53، CRC Press، صفحة 223، ISBN 9781584888000 .

[6] Wasserman، Stanley؛ Faust، Katherine (1994)، Social Network Analysis: Methods and Applications، Structural Analysis in the Social Sciences، 8، Cambridge University Press، صفحات 299–302، ISBN 9780521387071 .

[7] 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.

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

[9] 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.

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

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

[12] 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.

[13] Biggs، Norman (1994)، Algebraic Graph Theory، Cambridge Mathematical Library (الطبعة 2nd)، Cambridge University Press، صفحة 53، ISBN 9780521458979 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

مخطط ثنائي

محتويات

أمثلة[عدل]

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

خواص المخطط ثنائي التجزئة[عدل]

مميزات[عدل]

نظرية König's و المخطط ثنائي التجزئة[عدل]

الدرجة[عدل]

العلاقة مع المخططات الزائدي و المخططات الموجة[عدل]

خوارزميات[عدل]

اختبار التجزئة الثنائية[عدل]

إنتقالية الدارات الفردية Odd cycle transveral[عدل]

المطابقة Matching[عدل]

تطبيقات إضافية[عدل]

المزيد[عدل]

مراجع[عدل]

قائمة التصفح

أدوات شخصية

نطاقات

المتغيرات

معاينة

المزيد

بحث

الموسوعة

تصفح

مشاركة

أدوات

في مشاريع أخرى

طباعة/تصدير

لغات