نصف ثنائي الأجزاء

الموسوعة الحرة
الرسم البياني للمكعب المقسم إلى نصفين من الرتبة 4، والذي تم الحصول عليه كنصف ثنائي الأجزاء من رسم بياني للمكعب الفائق من الرتبة 4

في نظرية المخططات ، يُعرف النصف الثنائي أو نصف المربع للمخطط الثنائي G = ( U , V , E ) بأنه مخطط تكون مجموعة رؤوسه أحد جانبي التقسيم الثنائي ( بدون فقدان للعمومية ، U )، ويوجد فيه ضلع u <sub> i </sub> u<sub> j </sub> لكل زوج من الرؤوس u <sub>i</sub> و u <sub> j </sub> في U والمسافة بينهما في G هي اثنان . [ 1 ] أي، بصيغة أكثر اختصارًا، يكون النصف الثنائي هو G<sub> 2</sub> [ U ] حيث يشير الرمز العلوي 2 إلى مربع المخطط ، وتشير الأقواس المربعة إلى مخطط فرعي مستحث .

أمثلة

على سبيل المثال، النصف الثنائي للرسم البياني الثنائي الكامل K <sub>n , n</sub> هو الرسم البياني الكامل K<sub> n </sub>، والنصف الثنائي للرسم البياني للمكعب الفائق هو الرسم البياني للمكعب المقسم إلى نصفين . عندما يكون G رسمًا بيانيًا منتظم المسافة ، فإن نصفيه الثنائيين يكونان منتظمي المسافة أيضًا. [ 2 ] على سبيل المثال، يُعد الرسم البياني المقسم إلى نصفين من فوستر واحدًا من عدد محدود من الرسوم البيانية الخطية المحلية المنتظمة المسافة من الدرجة 6. [ 3 ]

التمثيل والصلابة

كل رسم بياني G هو النصف الثنائي لرسم بياني آخر، ويتكون من تقسيم حواف G إلى مسارات ثنائية الحواف. وبشكل أعم، يمكن إيجاد تمثيل لـ G كنصف ثنائي بأخذ أي غطاء حواف من الزمر لـ G واستبدال كل زمرة بنجمة . [ 4 ] ينشأ كل تمثيل بهذه الطريقة. وبما أن إيجاد أصغر غطاء حواف من الزمر مسألة صعبة حسابيًا (NP-hard)، فإن إيجاد الرسم البياني الذي يحتوي على أقل عدد من الرؤوس والذي يكون G نصفه الثنائي هو أيضًا مسألة صعبة حسابيًا. [ 5 ]

حالات خاصة

إن مخططات الخرائط ، أي مخططات التقاطع للمناطق المتصلة ببساطة والمنفصلة داخليًا في المستوى، هي بالضبط أنصاف المخططات المستوية ثنائية الأجزاء . [ 6 ]

انظر أيضاً

مراجع

  1. ↑ ويلسون، روبن ج. (2004)، موضوعات في نظرية الرسم البياني الجبرية ، موسوعة الرياضيات وتطبيقاتها، المجلد  102، مطبعة جامعة كامبريدج، ص  188، ISBN 9780521801973.
  2. ↑ تشيهارا، لورا؛ ستانتون، دينيس (1986)، "مخططات الارتباط والتحويلات التربيعية لكثيرات الحدود المتعامدة"، الرسوم البيانية والتوافقية ، 2 (2): 101-112 ، doi : 10.1007/BF01788084 ، MR 0932118 ، S2CID 28803214  .
  3. ↑ هيراكي، أكيرا؛ نومورا، كازوماسا؛ سوزوكي، هيروشي (2000)، "الرسوم البيانية المنتظمة المسافة ذات التكافؤ 6 وأ1=1{\displaystyle a_{1}=1}"، مجلة التوافقية الجبرية ، 11 (2): 101-134 ، doi : 10.1023/A:1008776031839 ، MR 1761910 
  4. ^ لو، هوانج أوانه؛ لو، فان بانغ (2019)، “التمثيلات المقيدة للرسوم البيانية للخرائط وأنصاف المربعات”، في بيتر روسمانيث؛ هيجرنيس، بينار؛ كاتوين، جوست بيتر (محرران)، الندوة الدولية الرابعة والأربعون حول الأسس الرياضية لعلوم الكمبيوتر، MFCS 2019، 26-30 أغسطس 2019، آخن، ألمانيا ، LIPIcs، المجلد. 138، شلوس داغستوهل - Leibniz-Zentrum für Informatik، الصفحات 13:1–13:15، دوى : 10.4230/LIPIcs.MFCS.2019.13 ، ISBN   9783959771177
  5. ↑ غاري، مايكل ر .؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . سلسلة كتب في العلوم الرياضية ( الطبعة الأولى). نيويورك: دبليو إتش فريمان وشركاه . ISBN  9780716710455MR 0519066 . OCLC 247570676 .​  ، المشكلة GT59.
  6. ^ تشين ، تشي تشونغ. غريني، مايكل أنجلو؛ Papadimitriou، Christos H. (2002)، “Map graphs”، مجلة ACM ، 49 (2): 127–138 ، أرخايف : cs/9910013 ، دوى : 10.1145/506147.506148 ، السيد 2147819 ، S2CID 2657838  .