تضمين الرسم البياني

في نظرية الرسم البياني الطوبولوجية ، يُطلق مصطلح " التضمين" (أو "التضمين ") على تمثيل الرسم البياني. $G$ على سطح $\Sigma$ هو تمثيل لـ $G$ على $\Sigma$ في أي نقاط $\Sigma$ ترتبط بالرؤوس والأقواس البسيطة ( الصور المتماثلة لـ $[0,1]$ ترتبط ) بالحواف بطريقة تجعل:

نقاط نهاية القوس المرتبط بحافة $e$ النقاط المرتبطة برؤوس النهاية لـ $e,$
لا تتضمن الأقواس نقاطًا مرتبطة برؤوس أخرى،
لا يتقاطع قوسان أبدًا عند نقطة تقع داخل أي من القوسين.

هنا السطح عبارة عن سطح متصل $2$ - متعدد الشعب .

بصورة غير رسمية، يُقصد بتضمين رسم بياني في سطح ما رسم هذا الرسم على السطح بحيث لا تتقاطع حوافه إلا عند نقاط نهايتها. ومن المعروف أن أي رسم بياني محدود يمكن تضمينه في الفضاء الإقليدي ثلاثي الأبعاد. $\mathbb {R} ^{3}$ [ ^{1 ]} الرسم البياني المستوي هو الرسم ^{البياني} الذي يمكن تضمينه في الفضاء الإقليدي ثنائي الأبعاد $\mathbb {R} ^{2}.$

غالباً ما يُنظر إلى التضمين على أنه فئة تكافؤ (تحت التشاكلات المتماثلة لـ $\Sigma$ ) من التمثيلات من النوع الموصوف للتو.

يُعرّف بعض المؤلفين صيغةً أضعف لتعريف "تضمين الرسم البياني" بحذف شرط عدم التقاطع للحواف. وفي هذه السياقات، يُوصف التعريف الأكثر صرامة بأنه "تضمين الرسم البياني غير المتقاطع". ^{[ 2 ]}

تتناول هذه المقالة التعريف الدقيق لتضمين الرسم البياني فقط. أما التعريف الأقل دقة فيتم مناقشته في مقالتي " رسم الرسم البياني " و" عدد التقاطعات ".

مصطلحات

إذا كان الرسم البياني $G$ مثبتة على سطح مغلق $\Sigma$ ، مكمل اتحاد النقاط والأقواس المرتبطة برؤوس وحواف $G$ هي مجموعة من المناطق (أو الأوجه ). ^{[ 3 ]} التضمين ثنائي الخلايا ، أو التضمين الخلوي ، أو الخريطة، هو تضمين يكون فيه كل وجه متماثلًا شكليًا مع قرص مفتوح. ^{[ 4 ]} التضمين ثنائي الخلايا المغلق هو تضمين يكون فيه إغلاق كل وجه متماثلًا شكليًا مع قرص مغلق.

جنس الرسم البياني هو أصغر عدد صحيح $n$ بحيث يمكن تضمين الرسم البياني في سطح من جنس $n$ . على وجه الخصوص، يمتلك الرسم البياني المستوي جنسًا $0$ لأنه يمكن رسمه على سطح كروي دون أن يتقاطع مع نفسه. يُطلق على الرسم البياني الذي يمكن تضمينه على سطح حلقي اسم الرسم البياني الحلقي .

الجنس غير القابل للتوجيه للرسم البياني هو أصغر عدد صحيح $n$ بحيث يمكن تضمين الرسم البياني في سطح غير قابل للتوجيه من جنس (غير قابل للتوجيه) $n$ [ ³^]

جنس أويلر للرسم البياني هو أصغر عدد صحيح $n$ بحيث يمكن تضمين الرسم البياني في سطح قابل للتوجيه من جنس (قابل للتوجيه) $n/2$ أو في سطح غير قابل للتوجيه من جنس (غير قابل للتوجيه). $n$ . يكون الرسم البياني بسيطًا قابلًا للتوجيه إذا كان جنس أويلر الخاص به أصغر من جنسه غير القابل للتوجيه.

أكبر جنس للرسم البياني هو أكبر عدد صحيح $n$ بحيث يمكن أن يكون الرسم البياني $2$ خلية مضمنة في سطح قابل للتوجيه من جنس $n$ .

التضمين التوافقي

يُعرّف الرسم البياني المُضمّن ترتيبات دورية فريدة للحواف المتصلة بنفس الرأس. تُسمى مجموعة جميع هذه الترتيبات الدورية بنظام الدوران . تُعتبر التضمينات التي لها نفس نظام الدوران متكافئة، ويُطلق على فئة التكافؤ المقابلة للتضمينات اسم التضمين التوافقي (على عكس مصطلح التضمين الطوبولوجي ، الذي يشير إلى التعريف السابق من حيث النقاط والمنحنيات). في بعض الأحيان، يُطلق على نظام الدوران نفسه اسم "التضمين التوافقي". ^{[ 5 ]}^{[ 6 ]}^{[ 7 ]}

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

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

التعقيد الحسابي

تُعتبر مشكلة إيجاد جنس الرسم البياني من المسائل الصعبة من نوع NP (مشكلة تحديد ما إذا كان $n$ الرسم البياني ذو الرؤوس له جنس $g$ ( NP-complete ). ^{[ 8 ]}

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

حدث أول تقدم ملحوظ في هذا المجال عام 1979، عندما قُدِّمت خوارزميتان، إحداهما ذات تعقيد زمني O(nO(g))، بشكل مستقل إلى ندوة ACM السنوية ^حول نظرية الحوسبة : إحداهما ^من^إعداد^إ. فيلوتي وج. ل. ميلر، والأخرى من إعداد جون ريف . كانت مناهجهما مختلفة تمامًا، ولكن بناءً على اقتراح اللجنة المنظمة، قدّما ورقة بحثية مشتركة. ^[⁹^] مع ذلك، أثبتت ويندي ميرفولد وويليام كوكاي عام 2011 أن الخوارزمية التي قدمها فيلوتي وميلر وريف غير صحيحة. ^[¹⁰^]

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

تضمين الرسوم البيانية في فضاءات ذات أبعاد أعلى

من المعروف أنه يمكن تضمين أي رسم بياني محدود في فضاء ثلاثي الأبعاد. ^{[ 1 ]}

إحدى طرق القيام بذلك هي وضع النقاط على أي خط في الفضاء ورسم الحواف كمنحنيات، يقع كل منها في نصف مستوى مميز ، وتشترك جميع أنصاف المستويات في نفس الخط. يُطلق على هذا النوع من التضمين، حيث تُرسَم الحواف على أنصاف مستويات، اسم " تضمين الكتاب" للرسم البياني. يأتي هذا التشبيه من تخيل أن كل مستوى يُرسَم عليه حافة يُشبه صفحة من كتاب. وقد لوحظ أنه في الواقع، يمكن رسم عدة حواف في نفس "الصفحة"؛ وسُمك الكتاب للرسم البياني هو الحد الأدنى لعدد أنصاف المستويات اللازمة لمثل هذا الرسم.

بدلاً من ذلك، يمكن رسم أي رسم بياني محدود بحواف مستقيمة في ثلاثة أبعاد دون تقاطعات، وذلك بوضع رؤوسه في مواقع عامة بحيث لا تقع أي أربعة رؤوس ^في مستوى واحد. على سبيل المثال، يمكن تحقيق ذلك بوضع الرأس رقم i عند النقطة ( i , i2 , i3 ⁾ على منحنى العزم .

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

معرض

يُظهر الرسم البياني لبيترسن والخريطة المرتبطة به مُضمنين في المستوى الإسقاطي. يتم تحديد النقاط المتقابلة على الدائرة، مما ينتج عنه سطح مغلق من النوع 1 غير القابل للتوجيه.
الرسم البياني لبابوس والخريطة المرتبطة به مضمنة في الطارة.
الرسم البياني لكلاين من الدرجة 7 والخريطة المرتبطة به مضمنة في سطح قابل للتوجيه من النوع 3.

انظر أيضاً

التضمين ، لأنواع أخرى من التضمينات
سُمك الكتاب
سمك الرسم البياني
قائمة الحواف المتصلة ثنائياً ، وهي بنية بيانات لتمثيل تضمين الرسم البياني في المستوى
الخريطة المنتظمة (نظرية الرسم البياني)
تنص نظرية فاري على أن التضمين الخطي المستوي للرسم البياني المستوي ممكن دائمًا.
التثليث (الهندسة)

مراجع

1 2 كوهين، روبرت ف.؛ إيدز، بيتر ؛ لين، تاو؛ روسكي، فرانك (1995)، "رسم بياني ثلاثي الأبعاد"، في تاماسيا، روبرتو ؛ توليس، يوانيس ج. (محرران)، رسم بياني: ورشة عمل DIMACS الدولية، GD '94، برينستون، نيو جيرسي، الولايات المتحدة الأمريكية، 10-12 أكتوبر 1994، وقائع ، سلسلة محاضرات في علوم الحاسوب ، المجلد 894، سبرينغر، الصفحات 1-11 ، doi : 10.1007/3-540-58950-3_351 ، ISBN 978-3-540-58950-1.
↑ كاتوه، ناوكي؛ تانيغاوا، شين-إيتشي (2007)، "حصر الأشجار الممتدة الهندسية المقيدة غير المتقاطعة"، الحوسبة والتوافقية، المؤتمر الدولي السنوي الثالث عشر، COCOON 2007، بانف، كندا، 16-19 يوليو 2007، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب ، المجلد 4598، سبرينغر-فيرلاغ، الصفحات 243-253 ، CiteSeerX 10.1.1.483.874 ، doi : 10.1007/978-3-540-73545-8_25 ، ISBN 978-3-540-73544-1.
1 2 غروس، جوناثان؛ تاكر، توماس دبليو. (2001)، نظرية الرسم البياني الطوبولوجية ، منشورات دوفر، ISBN 978-0-486-41741-7.
↑ لاندو، سيرجي ك.؛ زفونكين، ألكسندر ك. (2004)، الرسوم البيانية على الأسطح وتطبيقاتها ، سبرينغر-فيرلاغ، ISBN 978-3-540-00203-1.
↑ موتزل، بيترا ؛ فايسكيرشر، رينيه (2000)، "حساب التضمينات المثلى للرسوم البيانية المستوية"، الحوسبة والتوافقية، المؤتمر الدولي السنوي السادس، COCOON 2000، سيدني، أستراليا، 26-28 يوليو 2000، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد 1858، سبرينغر-فيرلاغ، الصفحات 95-104 ، doi : 10.1007/3-540-44968-X_10 ، ISBN 978-3-540-67787-1.
↑ ديدجيف، هريستو ن. (1995)، "حول رسم بياني محدب في المستوى"، ورشة عمل رسم الرسوم البيانية الدولية DIMACS، GD '94، برينستون، نيو جيرسي، الولايات المتحدة الأمريكية، 10-12 أكتوبر 1994، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد 894، سبرينغر-فيرلاغ، الصفحات 76-83 ، doi : 10.1007/3-540-58950-3_358 ، ISBN 978-3-540-58950-1.
↑ دانكن، كريستيان؛ جودريتش، مايكل ت .؛ كوبوروف، ستيفن (2010)، "الرسومات المستوية للرسوم البيانية من الرتبة العليا"، رسم الرسوم البيانية، الندوة الدولية السابعة عشرة، GD 2009، شيكاغو، إلينوي، الولايات المتحدة الأمريكية، 22-25 سبتمبر 2009، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 5849، سبرينغر-فيرلاغ، الصفحات 45-56 ، arXiv : 0908.1608 ، doi : 10.1007/978-3-642-11805-0_7 ، ISBN 978-3-642-11804-3.
↑ توماسين، كارستن (1989)، "مسألة جنس الرسم البياني هي مسألة NP-كاملة"، مجلة الخوارزميات ، 10 (4): 568-576 ، doi : 10.1016/0196-6774(89)90006-0
↑ فيلوتي، آي إس؛ ميلر، غاري إل ؛ ريف، جون (1979)، "حول تحديد جنس الرسم البياني في O(v O(g)) خطوة (تقرير أولي)"، وقائع الندوة السنوية الحادية عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 27-37 ، doi : 10.1145/800135.804395 .
↑ ميرفولد، ويندي ؛ كوكاي، ويليام (1 مارس 2011). "أخطاء في خوارزميات تضمين الرسوم البيانية". مجلة علوم الحاسوب والأنظمة . 2 (77): 430-438 . doi : 10.1016/j.jcss.2010.06.002 .
↑ موهار، بوجان (1999)، "خوارزمية زمنية خطية لتضمين الرسوم البيانية في سطح عشوائي"، مجلة SIAM للرياضيات المتقطعة ، 12 (1): 6-26 ، CiteSeerX 10.1.1.97.9588 ، doi : 10.1137/S089548019529248X

[3d-gd-1] 1 2 كوهين، روبرت ف.؛ إيدز، بيتر ؛ لين، تاو؛ روسكي، فرانك (1995)، "رسم بياني ثلاثي الأبعاد"، في تاماسيا، روبرتو ؛ توليس، يوانيس ج. (محرران)، رسم بياني: ورشة عمل DIMACS الدولية، GD '94، برينستون، نيو جيرسي، الولايات المتحدة الأمريكية، 10-12 أكتوبر 1994، وقائع ، سلسلة محاضرات في علوم الحاسوب ، المجلد 894، سبرينغر، الصفحات 1-11 ، doi : 10.1007/3-540-58950-3_351 ، ISBN 978-3-540-58950-1.

[2] كاتوه، ناوكي؛ تانيغاوا، شين-إيتشي (2007)، "حصر الأشجار الممتدة الهندسية المقيدة غير المتقاطعة"، الحوسبة والتوافقية، المؤتمر الدولي السنوي الثالث عشر، COCOON 2007، بانف، كندا، 16-19 يوليو 2007، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب ، المجلد 4598، سبرينغر-فيرلاغ، الصفحات 243-253 ، CiteSeerX 10.1.1.483.874 ، doi : 10.1007/978-3-540-73545-8_25 ، ISBN 978-3-540-73544-1.

[gt01-3] 1 2 غروس، جوناثان؛ تاكر، توماس دبليو. (2001)، نظرية الرسم البياني الطوبولوجية ، منشورات دوفر، ISBN 978-0-486-41741-7.

[4] لاندو، سيرجي ك.؛ زفونكين، ألكسندر ك. (2004)، الرسوم البيانية على الأسطح وتطبيقاتها ، سبرينغر-فيرلاغ، ISBN 978-3-540-00203-1.

[5] موتزل، بيترا ؛ فايسكيرشر، رينيه (2000)، "حساب التضمينات المثلى للرسوم البيانية المستوية"، الحوسبة والتوافقية، المؤتمر الدولي السنوي السادس، COCOON 2000، سيدني، أستراليا، 26-28 يوليو 2000، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد 1858، سبرينغر-فيرلاغ، الصفحات 95-104 ، doi : 10.1007/3-540-44968-X_10 ، ISBN 978-3-540-67787-1.

[6] ديدجيف، هريستو ن. (1995)، "حول رسم بياني محدب في المستوى"، ورشة عمل رسم الرسوم البيانية الدولية DIMACS، GD '94، برينستون، نيو جيرسي، الولايات المتحدة الأمريكية، 10-12 أكتوبر 1994، وقائع المؤتمر ، سلسلة محاضرات في علوم الحاسوب، المجلد 894، سبرينغر-فيرلاغ، الصفحات 76-83 ، doi : 10.1007/3-540-58950-3_358 ، ISBN 978-3-540-58950-1.

[7] دانكن، كريستيان؛ جودريتش، مايكل ت .؛ كوبوروف، ستيفن (2010)، "الرسومات المستوية للرسوم البيانية من الرتبة العليا"، رسم الرسوم البيانية، الندوة الدولية السابعة عشرة، GD 2009، شيكاغو، إلينوي، الولايات المتحدة الأمريكية، 22-25 سبتمبر 2009، أوراق منقحة ، سلسلة محاضرات في علوم الحاسوب، المجلد 5849، سبرينغر-فيرلاغ، الصفحات 45-56 ، arXiv : 0908.1608 ، doi : 10.1007/978-3-642-11805-0_7 ، ISBN 978-3-642-11804-3.

[8] توماسين، كارستن (1989)، "مسألة جنس الرسم البياني هي مسألة NP-كاملة"، مجلة الخوارزميات ، 10 (4): 568-576 ، doi : 10.1016/0196-6774(89)90006-0

[9] فيلوتي، آي إس؛ ميلر، غاري إل ؛ ريف، جون (1979)، "حول تحديد جنس الرسم البياني في O(v O(g)) خطوة (تقرير أولي)"، وقائع الندوة السنوية الحادية عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة ، الصفحات 27-37 ، doi : 10.1145/800135.804395 .

[10] ميرفولد، ويندي ؛ كوكاي، ويليام (1 مارس 2011). "أخطاء في خوارزميات تضمين الرسوم البيانية". مجلة علوم الحاسوب والأنظمة . 2 (77): 430-438 . doi : 10.1016/j.jcss.2010.06.002 .

[11] موهار، بوجان (1999)، "خوارزمية زمنية خطية لتضمين الرسوم البيانية في سطح عشوائي"، مجلة SIAM للرياضيات المتقطعة ، 12 (1): 6-26 ، CiteSeerX 10.1.1.97.9588 ، doi : 10.1137/S089548019529248X

1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[

[

[ 11 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗