اختبار التسطيح الأيسر-الأيمن

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

في نظرية المخططات ، وهي فرع من فروع الرياضيات ، يُعد اختبار التسطح من اليسار إلى اليمين، أو معيار دي فرايسكس-روزنستيل للتسطح [ 1 ] ، وصفًا للمخططات المستوية استنادًا إلى خصائص أشجار البحث العميق أولًا ، وقد نشره دي فرايسكس وروزنستيل ( 1982 ، 1985 ) [ 2 ] [ 3 ] ، واستخدماه مع باتريس أوسونا دي مينديز لتطوير خوارزمية اختبار تسطح خطية الزمن . [ 4 ] [ 5 ] وفي مقارنة تجريبية أجريت عام 2003 لست خوارزميات لاختبار التسطح، كانت هذه الخوارزمية من أسرع الخوارزميات التي تم اختبارها. [ 6 ] 

حواف متشابهة على شكل حرف T وحواف متقابلة على شكل حرف T

في أي عملية بحث في العمق أولاً في الرسم البياني G ، تُحدد الحواف التي تُصادف عند اكتشاف رأس لأول مرة شجرة بحث في العمق أولاً T للرسم البياني G. هذه شجرة تريموكس ، أي أن الحواف المتبقية (الشجرة المشتركة ) تربط كل منها زوجًا من الرؤوس التي تربطها علاقة سلف وفرع في T. يمكن استخدام ثلاثة أنواع من الأنماط لتحديد علاقتين بين أزواج حواف الشجرة المشتركة، تُسميان علاقة التشابه T وعلاقة التقابل T. 

في الأشكال التالية، تمثل العقد الدائرية البسيطة رؤوس الشجرة، وتمثل العقد الدائرية المزدوجة الأشجار الفرعية، وتمثل القطع الملتوية مسارات الشجرة، وتمثل الأقواس المنحنية حواف الشجرة المشتركة. يظهر جذر كل شجرة في أسفل الشكل. في الشكل الأول، الحواف المسماةα{\displaystyle \alpha }وβ{\displaystyle \beta }في الشكلين التاليين، تكون الحواف ذات التسميات المتشابهة متقابلة، أي أنها تقع على نفس جانب الشجرة في كل رسم ثنائي الأبعاد. أما في الشكلين التاليين، فتكون الحواف ذات التسميات المتشابهة متقابلة ، أي أنها تقع على جانبين مختلفين من الشجرة في كل رسم ثنائي الأبعاد.

α{\displaystyle \alpha }وβ{\displaystyle \beta }متشابهون مع تي
α{\displaystyle \alpha }وβ{\displaystyle \beta }هي عكس حرف T
α{\displaystyle \alpha }وβ{\displaystyle \beta }هي عكس حرف T

التوصيف

ليكن G رسمًا بيانيًا، وليكن T شجرة تريموكس للرسم البياني G. يكون الرسم البياني G مستويًا إذا وفقط إذا وُجد تقسيم لحواف الشجرة المشتركة للرسم البياني G إلى فئتين بحيث تنتمي أي حافتين إلى نفس الفئة إذا كانتا متشابهتين بالنسبة لـ T، وتنتمي أي حافتين إلى فئتين مختلفتين إذا كانتا متقابلتين بالنسبة لـ T.

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

مراجع

  1. ↑ أوير، كريستوفر؛ غلايسنر، أندرياس؛ هاناور، كاثرين؛ فيتر، سيباستيان (2013)، "اختبار التسطيح عن طريق تبديل القطارات"، رسم المخططات: الندوة الدولية العشرون، GD 2012، ريدموند، واشنطن، الولايات المتحدة الأمريكية، 19-21 سبتمبر 2012، أوراق مختارة منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد  7704، برلين: سبرينغر، الصفحات 557-558 ، doi : 10.1007/978-3-642-36763-2_51 .
  2. ↑ دي فرايسيكس، هـ .؛ روزنستيل، ب. (1982)، "توصيف التسطح باستخدام البحث العميق أولاً"، نظرية الرسم البياني (كامبريدج، 1981) ، حوليات الرياضيات المتقطعة، المجلد 13، نورث هولاند، أمستردام-نيويورك، الصفحات 75-80 ، MR 0671906   .
  3. ↑ دي فرايسيكس، هـ.؛ روزنستيل، ب. (1985)، "توصيف الرسوم البيانية المستوية بواسطة رتب تريموكس"، كومبيناتوريكا ، 5 (2): 127-135 ، doi : 10.1007/BF02579375 ، MR 0815578 ، S2CID 35423242  .
  4. ↑ دي فرايسيكس، هوبرت؛ أوسونا دي مينديز، باتريس ؛ روزنستيل، بيير (2006)، "أشجار تريموكس والتسطيح"، المجلة الدولية لأسس علوم الحاسوب ، 17 (5): 1017-1029 ، arXiv : math.CO/0610935 ، doi : 10.1142/S0129054106004248 ، MR 2270949 .
  5. ^ دي فرايسيس ، هوبيرت. أوسونا دي مينديز، باتريس (2012)، “أشجار Trémaux and Planarity”، المجلة الأوروبية للتوافقيات ، 33 (3): 279–293 ، أرخايف : math/0610935 ، دوى : 10.1016/j.ejc.2011.09.012 ، MR 2864415 .
  6. ↑ بوير، جون م.؛ كورتيز، بيير فرانشيسكو؛ باترينياني، ماوريتسيو؛ دي باتيستا، جوزيبي (2004)، "توقف عن الاهتمام بـ P و Q: تطبيق خوارزمية سريعة وبسيطة لاختبار التسطح والتضمين تعتمد على DFS"، رسم الرسوم البيانية: الندوة الدولية الحادية عشرة، GD 2003، بيروجيا، إيطاليا، 21-24 سبتمبر 2003، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 2912، برلين: سبرينغر، الصفحات 25-36 ، doi : 10.1007/978-3-540-24595-7_3 ، MR 2177580   .

للمزيد من القراءة