التضمين المتزامن

التضمين المتزامن هو أسلوب في رسم المخططات وتصوير المعلومات لعرض مخططين أو أكثر مختلفين على نفس مجموعات الرؤوس المصنفة أو مجموعات متداخلة منها ، مع تجنب التقاطعات داخل كلا المخططين. يُسمح بالتقاطعات بين حافة أحد المخططين وحافة المخطط الآخر. ^{[ 1 ]}

إذا سُمح برسم الحواف كخطوط متعددة أو منحنيات ، فإنه يمكن رسم أي رسم بياني مستوٍ دون تقاطع مع رؤوسه في أي موضع في المستوى، حيث يوفر نفس موضع الرأس تضمينًا متزامنًا. ^{[ 1 ]}

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

التضمين المتزامن هو أسلوب في رسم المخططات وتصوير المعلومات يُستخدم لتصوير مخططين أو أكثر على نفس مجموعات الرؤوس المُصنفة أو مجموعات متداخلة منها ، مع تجنب التقاطعات داخل كلا المخططين. يُسمح بالتقاطعات بين حافة من أحد المخططين وحافة من المخطط الآخر؛ أما التقاطعات بين حافتين من نفس المخطط فهي غير مسموحة. ^{[ 1 ]}

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

يوجد نموذجان مقيدان: التضمين الهندسي المتزامن والتضمين المتزامن ذو الحواف الثابتة، حيث يُسمح بالمنحنيات أو الانحناءات في الحواف، ولكن يجب تمثيل أي حافة موجودة في كلا الرسمين البيانيين بنفس المنحنى في كليهما. عندما يوجد تضمين هندسي متزامن، فإنه يكون تلقائيًا تضمينًا متزامنًا ذو حواف ثابتة. ^{[ 1 ]}

في مسائل التضمين المتزامن لأكثر من رسمين بيانيين، من المعتاد افتراض أن جميع أزواج الرسوم البيانية المدخلة لها نفس التقاطع؛ أي أن مجموعات الحواف والرؤوس للرسوم البيانية تشكل شكل زهرة عباد الشمس . يُعرف هذا القيد باسم تقاطع زهرة عباد الشمس . ^{[ 1 ]}

يرتبط التضمين المتزامن ارتباطًا وثيقًا بالسماكة ، وهي الحد الأدنى لعدد الرسوم البيانية الفرعية المستوية التي يمكنها تغطية جميع حواف رسم بياني معين، والسماكة الهندسية، وهي الحد الأدنى لعدد ألوان الحواف اللازمة في رسم خطي مستقيم لرسم بياني معين دون تقاطع بين الحواف ذات اللون نفسه. على وجه الخصوص، تكون سماكة الرسم البياني المعطى اثنين إذا أمكن تقسيم حواف الرسم البياني إلى رسمين بيانيين فرعيين لهما تضمين متزامن، وتكون السماكة الهندسية اثنين إذا أمكن تقسيم الحواف إلى رسمين بيانيين فرعيين لتضمين هندسي متزامن. ^{[ 2 ]}

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

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

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

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

يبقى السؤال مطروحًا حول إمكانية اختبار وجود تمثيل متزامن ذي حواف ثابتة لرسمين بيانيين معطيين في زمن متعدد الحدود . مع ذلك، بالنسبة لثلاثة رسوم بيانية أو أكثر، تُصنَّف المسألة ضمن فئة NP-complete . عندما توجد تمثيلات متزامنة ذات حواف ثابتة، يمكن إيجادها في زمن متعدد الحدود لأزواج الرسوم البيانية الخارجية المستوية، وللرسوم البيانية ثنائية الاتصال ، أي أزواج الرسوم البيانية التي يكون تقاطعها ثنائي الاتصال. ^{[ 1 ] [ 10 ] [ 11 ] [ 12 ]}

يمكن تمثيل أي رسمين بيانيين مستويين في آن واحد. ويمكن القيام بذلك في شبكة ذات مساحة متعددة الحدود، مع انحناءين على الأكثر لكل حافة. ​​كما يمكن تمثيل أي رسمين بيانيين شبه هاميلتونيين في آن واحد مع انحناء واحد على الأكثر لكل حافة. ^{​​[ 1 ] [ 8 ] [ 13 ]}