الرسم البياني الخارجي المستوي
في نظرية الرسم البياني ، الرسم البياني الخارجي المستوي هو رسم بياني له رسم مستوٍ تنتمي جميع رؤوسه إلى الوجه الخارجي للرسم.
يمكن وصف الرسوم البيانية الخارجية المستوية (بشكل مماثل لنظرية فاغنر للرسوم البيانية المستوية) بواسطة المحددَين الفرعيين الممنوعَين K₄ و K₂ , ₃ ، أو بواسطة ثوابت كولين دي فيرديير الخاصة بها . تحتوي هذه الرسوم البيانية على دورات هاميلتونية إذا وفقط إذا كانت ثنائية الاتصال، وفي هذه الحالة يشكل الوجه الخارجي الدورة الهاميلتونية الوحيدة. كل رسم بياني خارجي مستوٍ قابل للتلوين بثلاثة ألوان، وله انحلال وعرض شجري لا يتجاوز 2.
تُعدّ الرسوم البيانية الخارجية المستوية مجموعة فرعية من الرسوم البيانية المستوية ، والرسوم البيانية الفرعية للرسوم البيانية المتسلسلة المتوازية ، والرسوم البيانية الدائرية . كما تُعتبر الرسوم البيانية الخارجية المستوية القصوى ، أي تلك التي لا يمكن إضافة المزيد من الحواف إليها مع الحفاظ على استوائها الخارجي، رسومًا بيانية وترية ورسومًا بيانية للرؤية .
تاريخ
درس تشارتراند وهاراري (1967) الرسوم البيانية الخارجية المستوية وأطلقوا عليها هذا الاسم لأول مرة ، وذلك في سياق بحثهما عن مسألة تحديد استواء الرسوم البيانية المُشكَّلة باستخدام مطابقة تامة لربط نسختين من رسم بياني أساسي (على سبيل المثال، يتم تشكيل العديد من رسوم بيترسن المعممة بهذه الطريقة من نسختين من رسم بياني دوري ). وكما أوضحا، عندما يكون الرسم البياني الأساسي ثنائي الاتصال ، يكون الرسم البياني المُنشأ بهذه الطريقة مستويًا إذا وفقط إذا كان رسمه البياني الأساسي خارجيًا مستويًا، وكانت المطابقة تُشكِّل تبديلًا ثنائي السطوح لدورته الخارجية. كما أثبت تشارتراند وهاراري نظيرًا لنظرية كوراتوفسكي للرسوم البيانية الخارجية المستوية، وهي أن الرسم البياني يكون خارجيًا مستويًا إذا وفقط إذا لم يحتوِ على تقسيم فرعي لأحد الرسمين البيانيين K₄ أو K₂ , ₃ .
التعريفات والخصائص
الرسم البياني الخارجي المستوي هو رسم بياني غير موجه يمكن رسمه في المستوى دون تقاطعات ، بحيث تنتمي جميع رؤوسه إلى الوجه غير المحدود للرسم. أي أنه لا يوجد رأس محاط بالكامل بحواف. وبعبارة أخرى، يكون الرسم البياني G خارجيًا مستويًا إذا كان الرسم البياني الناتج عنه بإضافة رأس جديد، مع حواف تربطه بجميع الرؤوس الأخرى، رسمًا بيانيًا مستويًا . [ 1 ] [ 2 ]
الرسم البياني الخارجي المستوي الأقصى هو رسم بياني خارجي مستوي لا يمكن إضافة أي حواف إليه مع الحفاظ على خاصية الاستواء الخارجي. كل رسم بياني خارجي مستوي أقصى ذو n رأسًا يحتوي على 2n - 3 حواف بالضبط ، وكل وجه محدود في الرسم البياني الخارجي المستوي الأقصى هو مثلث.
الرسوم البيانية المحظورة
تتميز الرسوم البيانية الخارجية المستوية بخاصية الرسوم البيانية المحظورة، وهي خاصية مماثلة لنظرية كوراتوفسكي ونظرية فاغنر للرسوم البيانية المستوية: يكون الرسم البياني خارجيًا مستويًا إذا وفقط إذا لم يحتوِ على أي تقسيم فرعي للرسم البياني الكامل K₄ أو الرسم البياني الثنائي الكامل K₂ ,₃ . [ 3 ] وبعبارة أخرى، يكون الرسم البياني خارجيًا مستويًا إذا وفقط إذا لم يحتوِ على K₄ أو K₂ , ₃ كرسم بياني فرعي ، وهو رسم بياني مُشتق منه عن طريق حذف وتقليص الحواف. [ 4 ]
يكون الرسم البياني الخالي من المثلثات خارجيًا مستويًا إذا وفقط إذا لم يكن يحتوي على تقسيم فرعي لـ K 2,3 . [ 5 ]
كولين دي فيرديير ثابت
يكون الرسم البياني خارجيًا مستويًا إذا وفقط إذا كان ثابت كولين دي فيرديير الخاص به لا يتجاوز اثنين. أما الرسوم البيانية التي تتميز بطريقة مماثلة، حيث يكون ثابت كولين دي فيرديير الخاص بها لا يتجاوز واحدًا أو ثلاثة أو أربعة، فهي على التوالي الغابات الخطية، والرسوم البيانية المستوية ، والرسوم البيانية القابلة للتضمين بدون روابط .
ملكيات
الاتصالية الثنائية والهاملتونية
يكون الرسم البياني الخارجي ثنائي الاتصال إذا وفقط إذا كان وجهه الخارجي يشكل دورة بسيطة بدون رؤوس مكررة. ويكون الرسم البياني الخارجي هاميلتونيًا إذا وفقط إذا كان ثنائي الاتصال؛ في هذه الحالة، يشكل الوجه الخارجي دورة هاميلتونية فريدة. [ 6 ] وبشكل أعم، يكون حجم أطول دورة في الرسم البياني الخارجي مساويًا لعدد الرؤوس في أكبر مكون ثنائي الاتصال فيه . لهذا السبب، يمكن حل مسألة إيجاد الدورات الهاميلتونية وأطول الدورات في الرسوم البيانية الخارجية في وقت خطي ، على عكس مسألة NP-completeness لهذه المسائل بالنسبة للرسوم البيانية العشوائية.
كل رسم بياني خارجي مستوٍ أقصى يحقق شرطًا أقوى من شرط الهاميلتونية: فهو شامل العقد ، بمعنى أنه لكل رأس v ولكل قيمة k في النطاق من ثلاثة إلى عدد رؤوس الرسم البياني، توجد دورة طولها k تحتوي على v . يمكن إيجاد دورة بهذا الطول عن طريق إزالة مثلث متصل ببقية الرسم البياني بحافة واحدة بشكل متكرر، بحيث لا يكون الرأس المُزال هو v ، حتى يصبح طول الوجه الخارجي للرسم البياني المتبقي k . [ 7 ]
يكون الرسم البياني المستوي خارجيًا مستويًا إذا وفقط إذا كان كل مكون من مكوناته ثنائية الاتصال خارجيًا مستويًا. [ 5 ]
تلوين
يمكن تلوين جميع الرسوم البيانية الخارجية المستوية الخالية من الحلقات باستخدام ثلاثة ألوان فقط؛ [ 8 ] تبرز هذه الحقيقة بشكل واضح في البرهان المبسط لنظرية معرض تشفاتال الفنية الذي قدمه فيسك (1978) . يمكن إيجاد تلوين ثلاثي في وقت خطي باستخدام خوارزمية تلوين جشعة تزيل أي رأس من الدرجة الثانية على الأكثر، ثم تلون الرسم البياني المتبقي بشكل متكرر، ثم تضيف الرأس المُزال بلون مختلف عن لوني جاريه.
وفقًا لنظرية فيزينغ ، فإنّ مؤشر التلوين لأي رسم بياني (أي الحد الأدنى لعدد الألوان اللازمة لتلوين حوافه بحيث لا يكون لأي حافتين متجاورتين اللون نفسه) يساوي إما أعلى درجة لأي رأس في الرسم البياني أو واحدًا زائد أعلى درجة. مع ذلك، في الرسم البياني الخارجي المتصل، يكون مؤشر التلوين مساويًا لأعلى درجة باستثناء حالة تشكيل الرسم البياني لدورة ذات طول فردي. [ 9 ] يمكن إيجاد تلوين الحواف بالعدد الأمثل من الألوان في زمن خطي بالاعتماد على اجتياز الشجرة الثنائية الضعيفة بالعرض أولًا . [ 8 ]
خصائص أخرى
تحتوي الرسوم البيانية الخارجية المستوية على انحلال لا يتجاوز اثنين: كل رسم بياني فرعي من رسم بياني خارجي مستوي يحتوي على رأس بدرجة لا تتجاوز اثنين. [ 10 ]
تتميز الرسوم البيانية الخارجية المستوية بعرض شجري لا يتجاوز اثنين، مما يعني إمكانية حل العديد من مسائل تحسين الرسوم البيانية المصنفة ضمن فئة NP-complete لأي نوع من الرسوم البيانية في وقت متعدد الحدود باستخدام البرمجة الديناميكية عندما تكون المدخلات خارجية مستوية. وبشكل أعم، تتميز الرسوم البيانية الخارجية المستوية من الرتبة k بعرض شجري من الرتبة O( k ). [ 11 ]
يمكن تمثيل كل رسم بياني خارجي مستوي كرسم بياني تقاطع لمستطيلات محاذية للمحاور في المستوى، لذا فإن الرسوم البيانية الخارجية المستوية لها خاصية الصندوقية على الأكثر اثنين. [ 12 ]
عائلات الرسوم البيانية ذات الصلة
كل رسم بياني خارجي مستوٍ هو رسم بياني مستوٍ . وكل رسم بياني خارجي مستوٍ هو أيضًا رسم بياني فرعي من رسم بياني متسلسل متوازي . [ 13 ] مع ذلك، ليست كل الرسوم البيانية المتسلسلة المتوازية المستوية رسومًا بيانية خارجية مستوية. فالرسم البياني الثنائي الكامل K 2,3 مستوٍ ومتسلسل متوازي ولكنه ليس خارجيًا مستويًا. من ناحية أخرى، فإن الرسم البياني الكامل K 4 مستوٍ ولكنه ليس متسلسلًا متوازيًا ولا خارجيًا مستويًا. كل رسم بياني للغابة وكل رسم بياني للصبار رسوم بيانية خارجية مستوية. [ 14 ]
الرسم البياني الثنائي المستوي الضعيف لرسم بياني خارجي مستوي مُضمّن (الرسم البياني الذي يحتوي على رأس لكل وجه محدود من أوجه التضمين، وحافة لكل زوج من الوجوه المحدودة المتجاورة) هو غابة، والرسم البياني الثنائي المستوي الضعيف لرسم بياني هالين هو رسم بياني خارجي مستوي. يكون الرسم البياني المستوي خارجيًا مستويًا إذا وفقط إذا كان ثنائيه الضعيف غابة، ويكون هالين إذا وفقط إذا كان ثنائيه الضعيف ثنائي الاتصال وخارجيًا مستويًا. [ 15 ]
يوجد مفهوم لدرجة التسطح الخارجي. يُعتبر التضمين الخارجي ذو الدرجة 1 للرسم البياني مماثلاً للتضمين الخارجي. بالنسبة لـ k > 1، يُقال إن التضمين المستوي هو k- خارجي إذا أدى حذف الرؤوس على الوجه الخارجي إلى تضمين خارجي ( k - 1). يكون الرسم البياني k- خارجي إذا كان له k- خارجي. [ 16 ]
يمكن رسم الرسم البياني الخارجي ذو المستوى 1 ، على غرار الرسوم البيانية ذات المستوى 1 ، في قرص، مع وجود الرؤوس على حدود القرص، وبحد أقصى تقاطع واحد لكل حافة.
كل رسم بياني خارجي مستوٍ أقصى هو رسم بياني وتري . كل رسم بياني خارجي مستوٍ أقصى هو رسم بياني لرؤية مضلع بسيط . [ 17 ] تتشكل الرسوم البيانية الخارجية المستوية القصوى أيضًا كرسوم بيانية لتثليثات المضلعات . وهي أمثلة على الأشجار الثنائية ، والرسوم البيانية المتسلسلة المتوازية ، والرسوم البيانية الوترية .
كل رسم بياني خارجي مستوي هو رسم بياني دائري ، وهو رسم بياني لتقاطع مجموعة من أوتار دائرة. [ 18 ]
ملحوظات
- ↑ ويجرز (1986)
- ↑ فيلسنر (2004) .
- ^ تشارتراند وهراري (1967) ؛ سيسلو (1979) ; Brandstädt، Le & Spinrad (1999) ، الاقتراح 7.3.1، ص. 117؛ فيلسنر (2004) .
- ↑ ديستل (2000) .
- 1 2 Sysło (1979) .
- ^ تشارتراند وهراري (1967) ؛ سيسلو (1979) .
- ↑ لي، كورنيل ومندلسون (2000) ، الاقتراح 2.5.
- 1 2 بروسكوروفسكي وسيسلو (1986) .
- ↑ فيوريني (1975) .
- ↑ ليك آند وايت (1970) .
- ↑ بيكر (1994) .
- ^ شاينرمان (1984) ؛ براندستات، لو وسبينراد (1999) ، ص. 54.
- ^ براندستات، لو وسبينراد (1999) ، ص. 174.
- ^ براندستات، لو وسبينراد (1999) ، ص. 169.
- ↑ سيسلو وبروسكوروفسكي (1983) .
- ^ كين وباسو (1976) ; سيسلو (1979) .
- ^ الجندي (1985) ؛ لين وسكينا (1995) ; براندستات، لو وسبينراد (1999) ، النظرية 4.10.3، ص. 65.
- ^ فيسيل وبوشيل (1985) ؛ أنغر (1988) .
مراجع
- بيكر، بريندا س. (1994)، "خوارزميات تقريبية لمسائل NP-كاملة على الرسوم البيانية المستوية"، مجلة ACM ، 41 (1): 153-180 ، doi : 10.1145/174644.174650 ، S2CID 9706753 .
- بوزا، لويس؛ فيدرياني، أوجينيو م.؛ نونيز ، خوان (2004)، “مشكلة التضمين الخارجي في الأسطح الزائفة”، آرس كومبيناتوريا ، 71 : 79– 91.
- بوزا، لويس؛ فيدرياني، أوجينيو م.؛ نونيز ، خوان (2004)، “مجموعات العوائق للرسوم البيانية لسطح الموز الخارجي”، آرس كومبيناتوريا ، 73 : 65– 77.
- بوزا، لويس؛ فيدرياني، يوجينيو م.؛ نونيز، خوان (2006)، "الرسوم البيانية غير القابلة للعد التي تقع جميع رؤوسها في وجه واحد"، مجلة أكتا ماتيماتيكا هنغاريكا ، 112 (4): 307-313 ، doi : 10.1007/s10474-006-0082-0 ، hdl : 11441/163886 ، S2CID 123241658 .
- بوزا، لويس؛ فيدرياني، يوجينيو م.؛ نونيز، خوان (2010)، "إمكانية التضمين الخارجي في بعض الأسطح الزائفة الناشئة عن ثلاث كرات"، الرياضيات المتقطعة ، 310 (23): 3359-3367 ، doi : 10.1016/j.disc.2010.07.027.
- براندشتات، أندرياس ؛ لي، فان بانغ؛ سبينراد، جيريمي (1999)، فئات الرسوم البيانية: دراسة استقصائية ، سلسلة دراسات SIAM في الرياضيات المتقطعة وتطبيقاتها، جمعية الرياضيات الصناعية والتطبيقية ، ISBN 0-89871-432-X.
- الأماكن القريبة : هاراري ، فرانك (1967)، “الرسوم البيانية التقليب المستوية” ، حوليات معهد هنري بوانكاريه ب ، 3 (4): 433–438 ، MR 0227041 .
- ديستل، راينهارد (2000)، نظرية الرسم البياني ، نصوص الدراسات العليا في الرياضيات ، المجلد 173، سبرينغر-فيرلاغ، ص 107، ISBN 0-387-98976-5.
- الجندي، ح. (1985)، التفكيك الهرمي للمضلعات مع تطبيقات ، أطروحة دكتوراه، جامعة ماكجيلكما ورد في براندشتات، لي وسبينراد (1999) .
- فيلسنر، ستيفان (2004)، الرسوم البيانية والترتيبات الهندسية: بعض الفصول من الهندسة التوافقية ، دار نشر فيويغ + توبنر، ص 6، رقم ISBN 978-3-528-06972-8.
- فيوريني، ستانلي (1975)، "حول المؤشر اللوني للرسوم البيانية الخارجية المستوية"، مجلة نظرية التوافيق ، السلسلة ب، 18 (1): 35-38 ، doi : 10.1016/0095-8956(75)90060-X.
- فيسك، ستيف (1978)، "برهان مختصر لنظرية الحارس لشفاتال"، مجلة نظرية التوافيق ، السلسلة ب، 24 (3): 374، doi : 10.1016/0095-8956(78)90059-X.
- فليشنر، هربرت جيه؛ جيلر، دي بي؛ هاراري، فرانك (1974)، "الرسوم البيانية الخارجية المستوية والثنائيات الضعيفة"، مجلة الجمعية الرياضية الهندية ، 38 : 215-219 ، MR 0389672 .
- كين، فيناي جي؛ باسو، سانات ك. (1976)، "حول عمق الرسم البياني المستوي"، الرياضيات المتقطعة ، 14 (1): 63-67 ، doi : 10.1016/0012-365X(76)90006-6.
- لي، مينغ-تشو؛ كورنيل، ديريك ج .؛ مندلسون، إريك (2000)، "الشمولية والاكتمال NP في الرسوم البيانية المستوية"، الرياضيات التطبيقية المنفصلة ، 98 (3): 219-225 ، doi : 10.1016/S0166-218X(99)00163-8.
- ليك، دون ر.؛ وايت، آرثر ت. (1970)، " الرسوم البيانية المنحلة من الرتبة k "، المجلة الكندية للرياضيات ، 22 (5): 1082-1096 ، doi : 10.4153/CJM-1970-125-1 ، S2CID 124609794 .
- لين، ياو-لينغ؛ سكينا، ستيفن س. (1995)، "جوانب التعقيد في رسوم بيانية الرؤية"، المجلة الدولية للهندسة الحسابية وتطبيقاتها ، 5 (3): 289-312 ، doi : 10.1142/S0218195995000179.
- بروسكوروفسكي، أندريه؛ سيسلو، ماتشي م. (1986)، "تلوين فعال للرؤوس والحواف في الرسوم البيانية الخارجية المستوية"، مجلة SIAM للأساليب الجبرية والمنفصلة ، 7 : 131-136 ، doi : 10.1137/0607016.
- شاينرمان، إي آر (1984)، فئات التقاطع ومعاملات التقاطع المتعددة للرسم البياني ، أطروحة دكتوراه، جامعة برينستونكما ورد في براندشتات، لي وسبينراد (1999) .
- سيسلو، ماتشي م. (1979)، "خصائص الرسوم البيانية الخارجية المستوية"، الرياضيات المتقطعة ، 26 (1): 47-53 ، doi : 10.1016/0012-365X(79)90060-8.
- سيسلو، ماتشي م.؛ بروسكوروفسكي، أندريه (1983)، "حول رسوم هالين البيانية"، نظرية الرسوم البيانية: وقائع مؤتمر عُقد في لاغوف، بولندا، 10-13 فبراير 1981 ، سلسلة محاضرات في الرياضيات ، المجلد 1018، سبرينغر-فيرلاغ، الصفحات 248-256 ، doi : 10.1007/BFb0071635 ، ISBN 978-3-540-12687-4.
- أونغر، والتر (1988)، "حول تلوين الرسوم البيانية الدائرية بـ k لونًا"، وقائع الندوة الخامسة حول الجوانب النظرية لعلوم الحاسوب (STACS '88) ، سلسلة محاضرات في علوم الحاسوب ، المجلد 294، دار نشر سبرينغر، الصفحات 61-72 ، doi : 10.1007/BFb0035832 ، ISBN 3-540-18834-7.
- ويسل، دبليو؛ بوشيل، آر. (1985)، "حول الرسوم البيانية الدائرية"، في ساكس، هورست (محرر)، الرسوم البيانية ، والرسوم البيانية الفائقة وتطبيقاتها: وقائع مؤتمر نظرية الرسوم البيانية الذي عُقد في إيبا، من 1 إلى 5 أكتوبر 1984 ، نصوص توبنر في الرياضيات، المجلد 73، بي جي توبنر، الصفحات 207-210 كما ورد في كتاب أونغر (1988) .
- ويغرز، مانفريد (1986)، "التعرف على الرسوم البيانية الخارجية المستوية في وقت خطي"، مفاهيم نظرية الرسوم البيانية في علوم الحاسوب ، سلسلة محاضرات في علوم الحاسوب ، المجلد 246، الصفحات 165-176 ، doi : 10.1007/3-540-17218-1_57 ، ISBN 978-3-540-17218-5.
روابط خارجية
- الرسوم البيانية المستوية
- عائلات الرسوم البيانية