التسطيح

الموسوعة الحرة

في مجال نظرية المخططات الرياضية ، يُعدّ التسطيح طريقةً لتوسيع أساليب رسم المخططات من المخططات المستوية إلى المخططات غير المستوية، وذلك عن طريق تضمين المخططات غير المستوية داخل مخطط مستوٍ أكبر. [ 1 ] [ 2 ]

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

في عملية التسطيح التدريجي ، تُقسّم العملية إلى مرحلتين. أولًا، يتم إيجاد رسم بياني فرعي مستوٍ كبير ضمن الرسم البياني المُعطى. ثم، تُضاف الحواف المتبقية التي لم تُشكّل جزءًا من هذا الرسم البياني الفرعي، واحدة تلو الأخرى، وتُوجّه عبر تضمين الرسم البياني الفرعي المستوي. عندما يتقاطع أحد هذه الحواف مع حافة مُضمّنة مسبقًا، تُستبدل الحافتان المتقاطعتان بمسارين ثنائيي الحواف، مع رأس اصطناعي جديد يُمثّل نقطة التقاطع، ويقع في منتصف كلا المسارين. [ 1 ] [ 2 ] في بعض الحالات، تُضاف مرحلة تحسين محلية ثالثة إلى عملية التسطيح، حيث تُزال الحواف ذات التقاطعات الكثيرة وتُضاف مرة أخرى في محاولة لتحسين عملية التسطيح. [ 1 ]

إيجاد أكبر رسم بياني فرعي مستوٍ

يُعدّ استخدام التسطيح التدريجي لرسم الرسوم البيانية أكثر فعالية عندما تُحدّد الخطوة الأولى من العملية أكبر رسم بياني مستوٍ ممكن. مع ذلك، فإنّ إيجاد الرسم البياني الفرعي المستوي ذي أكبر عدد ممكن من الحواف ( مسألة الرسم البياني الفرعي المستوي الأقصى [ 3 ] ) يُصنّف ضمن المسائل الصعبة من نوع NP ، وكذلك ضمن المسائل الصعبة من نوع MaxSNP ، مما يعني أنه من غير المحتمل وجود خوارزمية ذات زمن متعدد الحدود تُحلّ المسألة بدقة أو تُقاربها بدقة تامة. [ 4 ]

في رسم بياني متصل ذي n رأس ، يحتوي أكبر رسم بياني فرعي مستوٍ على 3n - 6 حواف على الأكثر ، وتشكل أي شجرة ممتدة رسمًا بيانيًا فرعيًا مستويًا بعدد n - 1 حواف. بالتالي، من السهل تقريب أكبر رسم بياني فرعي مستوٍ بنسبة تقريب تبلغ الثلث، وذلك ببساطة عن طريق إيجاد شجرة ممتدة. وهناك نسبة تقريب أفضل، وهي 9/4، معروفة، استنادًا إلى طريقة لإيجاد شجرة جزئية كبيرة ثنائية الأبعاد كرسم بياني فرعي للرسم البياني المعطى. [ 1 ] [ 4 ] بدلاً من ذلك، إذا كان من المتوقع أن يشمل الرسم البياني الفرعي المستوي جميع حواف الرسم البياني المعطى تقريبًا، تاركًا عددًا صغيرًا k فقط من الحواف غير المستوية لعملية التسطيح التدريجي، فيمكن حل المشكلة بدقة باستخدام خوارزمية قابلة للتطبيق ذات معلمات ثابتة ، يكون زمن تشغيلها خطيًا بالنسبة لحجم الرسم البياني، ولكنه غير متعدد الحدود بالنسبة للمعلمة k . [ 5 ] يمكن أيضًا حل المشكلة بدقة باستخدام خوارزمية التفرع والقطع ، دون ضمانات على وقت التشغيل، ولكن بأداء جيد عمليًا. [ 1 ] [ 6 ] يُعرف هذا المعامل k باسم انحراف الرسم البياني. [ 3 ] [ 7 ]     

كما أُجريت بعض الدراسات حول مشكلة ذات صلة، وهي إيجاد أكبر رسم بياني فرعي مُستحث مُستوي لرسم بياني مُعطى. وهذه المشكلة، كما ذكرنا، تُصنف ضمن فئة NP-hard، ولكنها قابلة للحل باستخدام مُعاملات ثابتة عندما تنتمي جميع الرؤوس، باستثناء عدد قليل منها، إلى الرسم البياني الفرعي المُستحث. [ 8 ] أثبت إدواردز وفار (2002) حدًا دقيقًا قدره 3n / (Δ  +  1) لحجم أكبر رسم بياني فرعي مُستحث مُستوي، كدالة لـ n ، وهو عدد الرؤوس في الرسم البياني المُعطى، وΔ، وهي درجته القصوى ؛ ويؤدي برهانهما إلى خوارزمية زمنية متعددة الحدود لإيجاد رسم بياني فرعي مُستحث بهذا الحجم. [ 9 ]

إضافة حواف إلى عملية التسوية

بمجرد العثور على رسم بياني فرعي مستوٍ كبير، تستمر عملية التسطيح التدريجي بمعالجة الحواف المتبقية واحدة تلو الأخرى. وخلال ذلك، تحافظ على تسطيح الرسم البياني الفرعي المُشكَّل من الحواف التي سبق معالجتها. تُضاف كل حافة جديدة إلى تمثيل مستوٍ لهذا الرسم البياني الفرعي، مُشكِّلةً رسمًا بنقاط تقاطع، ثم تُستبدل كل نقطة تقاطع برأس اصطناعي جديد يقسم الحافتين المتقاطعتين. [ 1 ] [ 2 ] في بعض إصدارات هذه العملية، يكون ترتيب إضافة الحواف عشوائيًا، ولكن من الممكن أيضًا اختيار ترتيب عشوائي ، وتشغيل الخوارزمية نفسها عدة مرات وإرجاع أفضل تسطيح يتم العثور عليه. [ 1 ]

في أبسط صور هذه العملية، لا يُسمح بتغيير التمثيل المستوي للرسم البياني الفرعي المُسطّح أثناء إضافة حواف جديدة. ولإضافة كل حافة جديدة بطريقة تُقلل عدد التقاطعات التي تُشكّلها، يُمكن استخدام خوارزمية أقصر مسار في الرسم البياني الثنائي للتمثيل الحالي، وذلك لإيجاد أقصر تسلسل من أوجه التمثيل والحواف التي يجب عبورها والتي تربط نهايتي الحافة الجديدة ببعضهما. تستغرق هذه العملية وقتًا متعدد الحدود لكل حافة. ​​[ 2 ]

لا يُعدّ تثبيت تمثيل الرسم البياني الفرعي المُسطّح بالضرورة الأمثل من حيث عدد التقاطعات الناتجة. في الواقع، توجد رسوم بيانية تتشكل بإضافة حافة واحدة إلى رسم بياني فرعي مُسطّح، حيث يحتوي الرسم الأمثل على تقاطعين فقط، ولكن تثبيت التمثيل المُسطّح للرسم البياني الفرعي يُجبر على إنشاء عدد خطي من التقاطعات. [ 1 ] كحل وسط بين إيجاد التسطيح الأمثل لرسم بياني فرعي مُسطّح مُضاف إليه حافة واحدة، والحفاظ على تمثيل ثابت، يُمكن البحث في جميع تمثيلات الرسم البياني الفرعي المُسطّح وإيجاد التمثيل الذي يُقلل عدد التقاطعات الناتجة عن الحافة الجديدة. [ 1 ] [ 10 ]

مراجع

  1. 1 2 3 4 5 6 7 8 9 بوخهايم، كريستوف؛ شيماني، ماركوس؛ غوتفينغر، كارستن؛ يونغر، مايكل؛ موتزل، بيترا (2014)، "التقاطعات والتسوية"، في تاماسيا، روبرتو (محرر)، دليل رسم وتصوير الرسوم البيانية ، الرياضيات المتقطعة وتطبيقاتها (بوكا راتون)، مطبعة سي آر سي، بوكا راتون، فلوريدا.
  2. 1 2 3 4 دي باتيستا، جوزيبي؛ إيدز، بيتر ؛ تاماسيا، روبرتو ؛ توليس، يوانيس ج. (1998)، رسم الرسوم البيانية: خوارزميات لتصور الرسوم البيانية ( الطبعة الأولى)، برنتيس هول، ص 215-218 ، ISBN   0133016153.
  3. 1 2 شيماني، ماركوس (2008)، حساب أعداد التقاطع (ملف PDF) ، أطروحة دكتوراه، جامعة دورتموند التقنية ، القسم 4.3.1، مؤرشفة من الأصل (ملف PDF) بتاريخ 16-11-2015.
  4. 1 2 كالينيسكو، جرويا؛ فرنانديز، كريستينا G.؛ فينكلر، أولريش. كارلوف، هوارد (1998)، “خوارزمية تقريب أفضل للعثور على الرسوم البيانية الفرعية المستوية”، مجلة الخوارزميات ، 27 (2): 269–302 ، CiteSeerX 10.1.1.37.4317 ، دوى : 10.1006/jagm.1997.0920 ، MR 1622397 ، S2CID 8329680   .
  5. ↑ كاواراباياشي، كين-إيتشي ؛ ريد، بروس (2007)، "حساب عدد التقاطعات في زمن خطي"، وقائع الندوة السنوية التاسعة والثلاثين لجمعية آلات الحوسبة حول نظرية الحوسبة (STOC '07) ، الصفحات 382-390 ، doi : 10.1145/1250790.1250848 ، ISBN  978-1-59593-631-8، MR 2402463 ، S2CID 13000831  .
  6. ↑ يونغر، م.؛ موتزل، ب. (1996)، "الرسوم البيانية المستوية القصوى والتضمينات الجيدة: أدوات تخطيط عملية" (ملف PDF) ، Algorithmica ، 16 (1): 33-59 ، doi : 10.1007/s004539900036 ، MR 1394493 .
  7. ↑ وايسشتاين، إريك دبليو. "انحراف الرسم البياني" . عالم الرياضيات .
  8. ↑ كاواراباياشي، كين-إيتشي (2009)، "التسطيح الذي يسمح بوجود عدد قليل من رؤوس الخطأ في وقت خطي"، المؤتمر السنوي الخمسون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب (FOCS '09) (ملف PDF) ، الصفحات 639-648 ، doi : 10.1109/FOCS.2009.45 ، ISBN  978-1-4244-5116-6، MR 2648441 ، S2CID 11647021  .
  9. ↑ إدواردز، كيث؛ فار، غراهام (2002)، "خوارزمية لإيجاد الرسوم البيانية المستوية المستحثة الكبيرة"، رسم الرسوم البيانية: الندوة الدولية التاسعة، GD 2001 فيينا، النمسا، 23-26 سبتمبر 2001، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 2265، سبرينغر، الصفحات 75-80 ، doi : 10.1007/3-540-45848-4_6 ، ISBN   978-3-540-43309-5، MR 1962420 .
  10. ↑ غوتفينغر، كارستن؛ موتزل، بيترا ؛ فايسكيرشر، رينيه (2005)، "إدراج حافة في رسم بياني مستوٍ"، Algorithmica ، 41 (4): 289-308 ، doi : 10.1007/s00453-004-1128-8 ، MR 2122529 ، S2CID 6441726  .