الرسم البياني لقمة الهرم

في نظرية المخططات ، وهي فرع من الرياضيات، يُعرف مخطط القمة بأنه مخطط يمكن جعله مستويًا بإزالة رأس واحد . يُسمى الرأس المحذوف قمة المخطط. وهو قمة ، وليس القمة الوحيدة، لأن مخطط القمة قد يحتوي على أكثر من قمة واحدة؛ على سبيل المثال، في المخططات غير المستوية الدنيا K₅ أو _K₃ , _₃ ، كل رأس هو قمة. تشمل مخططات القمة مخططات مستوية، وفي هذه الحالة أيضًا كل رأس هو قمة. يُعتبر المخطط الصفري أيضًا مخطط قمة حتى لو لم يكن لديه رأس لإزالته.

تُعتبر الرسوم البيانية ذات القمة مغلقة تحت عملية أخذ القاصرين ، وتلعب دورًا في العديد من الجوانب الأخرى لنظرية القاصرين في الرسوم البيانية: التضمين بدون روابط ، ^{[ 1 ]} حدسية هادويجر ، ^{[ 2 ]} الرسوم البيانية القابلة للاختزال YΔY، ^{[ 3 ]} والعلاقات بين عرض الشجرة وقطر الرسم البياني . ^{[ 4 ]}

تُعتبر الرسوم البيانية الرأسية مغلقةً عند تطبيق عملية أخذ الرؤوس الصغرى : إذ يؤدي تقليص أي حافة، أو إزالة أي حافة أو رأس، إلى رسم بياني رأسي آخر. فإذا كان G رسمًا بيانيًا رأسيًا برأس v ، فإن أي تقليص أو إزالة لا يشمل v يحافظ على استواء الرسم البياني المتبقي، وكذلك إزالة أي حافة متصلة بـ v . وإذا تم تقليص حافة متصلة بـ v ، فإن تأثير ذلك على الرسم البياني المتبقي يُعادل إزالة الطرف الآخر للحافة. ​​وإذا تمت إزالة v نفسها، فيمكن اختيار أي رأس آخر كرأس. ^{[ 5 ]}

بحسب نظرية روبرتسون-سيمور ، ولأنها تُشكّل عائلةً من الرسوم البيانية المغلقة جزئيًا، فإنّ الرسوم البيانية الرأسية تتمتّع بخاصية الرسوم البيانية المحظورة . يوجد عدد محدود فقط من الرسوم البيانية التي لا تُصنّف كرسوم بيانية رأسية، ولا تحتوي على رسم بياني آخر غير رأسي كرسم بياني جزئي. تُعتبر هذه الرسوم البيانية رسومًا بيانية جزئية محظورة لخاصية كونها رسومًا بيانية رأسية. أي رسم بياني آخر G يكون رسمًا بيانيًا رأسيًا إذا وفقط إذا لم يكن أيٌّ من الرسوم البيانية الجزئية المحظورة رسمًا بيانيًا جزئيًا لـ G. تشمل هذه الرسوم البيانية الجزئية المحظورة الرسوم البيانية السبعة لعائلة بيترسن ، وثلاثة رسوم بيانية منفصلة مُشكّلة من اتحادين منفصلين لاثنين من K₅ و K₃ _{, ₃} ، والعديد من الرسوم البيانية الأخرى. مع ذلك، لا يزال وصفها الكامل غير معروف. ^{[ 5 ] [ 6 ]}

على الرغم من أن المجموعة الكاملة للمجموعات الصغرى المحظورة لا تزال مجهولة، فإنه من الممكن اختبار ما إذا كان رسم بياني معين رسمًا بيانيًا للرأس، وإذا كان كذلك، فمن الممكن إيجاد رأس لهذا الرسم البياني، وذلك في زمن خطي . وبشكل أعم، لأي ثابت k ، من الممكن التعرف في زمن خطي على الرسوم البيانية ذات k رأس ، وهي الرسوم البيانية التي يؤدي فيها حذف مجموعة مختارة بعناية من k رأس على الأكثر إلى رسم بياني مستوٍ. ^{[ 7 ]} أما إذا كان k متغيرًا، فإن المسألة تصبح مسألة NP-كاملة . ^{[ 8 ]}

كل رسم بياني رأسي له عدد لوني لا يتجاوز خمسة: يتطلب الرسم البياني المستوي الأساسي أربعة ألوان على الأكثر وفقًا لنظرية الألوان الأربعة ، ويحتاج الرأس المتبقي إلى لون إضافي واحد على الأكثر. استخدم روبرتسون وسيمور وتوماس (1993أ) هذه الحقيقة في برهانهم للحالة k = 6 من حدسية هادويجر ، التي تنص على أن كل رسم بياني سداسي الألوان له الرسم البياني الكامل K ₆ كرسم بياني جزئي: لقد أظهروا أن أي مثال مضاد أدنى للحدسية يجب أن يكون رسمًا بيانيًا رأسيًا، ولكن نظرًا لعدم وجود رسوم بيانية رأسية سداسية الألوان، فلا يمكن أن يوجد مثل هذا المثال المضاد.

افترض يورغنسن (1994) أن كل رسم بياني متصل بستة رؤوس ولا يحتوي على K ₆ كجزيء فرعي، يجب أن يكون رسمًا بيانيًا رأسيًا. لو ثبت هذا الافتراض، لكانت نتيجة روبرتسون-سيمور-توماس المتعلقة بفرضية هادويغر نتيجة مباشرة لذلك. ^{[ 2 ]} لا تزال فرضية يورغنسن غير مثبتة. ^{[ 9 ]} مع ذلك، إذا كانت خاطئة، فإن لها عددًا محدودًا فقط من الأمثلة المضادة. ^{[ 10 ]}

تتمتع عائلة الرسوم البيانية F بعرض شجري محلي محدود إذا كانت الرسوم البيانية في F تخضع لعلاقة دالية بين القطر وعرض الشجرة : توجد دالة f بحيث يكون عرض الشجرة لرسم بياني قطره d في F على الأكثر f ( d ) . لا تتمتع رسوم القمة بعرض شجري محلي محدود: رسوم القمة المتكونة من توصيل رأس قمة بكل رأس من رؤوس رسم بياني شبكي n × n لها عرض شجرة n وقطر 2، لذا فإن عرض الشجرة غير محدود بدالة قطر لهذه الرسوم البيانية. ومع ذلك، ترتبط رسوم القمة ارتباطًا وثيقًا بعرض الشجرة المحلي المحدود: عائلات الرسوم البيانية المغلقة جزئيًا F التي تتمتع بعرض شجري محلي محدود هي تحديدًا العائلات التي يكون فيها رسم القمة أحد رسومها القاصرة الممنوعة. ^{[ 4 ]} تُعرف عائلة الرسوم البيانية المغلقة جزئيًا التي يكون فيها رسم القمة أحد رسومها القاصرة الممنوعة باسم " خالية من رسوم القمة القاصرة" . باستخدام هذه المصطلحات، يمكن إعادة صياغة العلاقة بين الرسوم البيانية للقمة وعرض الشجرة المحلي على أنها حقيقة أن عائلات الرسوم البيانية الخالية من القمم الصغرى هي نفسها عائلات الرسوم البيانية المغلقة الصغرى ذات عرض الشجرة المحلي المحدود.

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

إذا كان G رسمًا بيانيًا رأسيًا رأسه v ، وكان τ هو الحد الأدنى لعدد الأوجه اللازمة لتغطية جميع جيران v في تمثيل مستوٍ لـ G \ { v }، فإنه يمكن تمثيل G على سطح ثنائي الأبعاد من الرتبة τ – 1 : ببساطة، أضف هذا العدد من الجسور إلى التمثيل المستوي، موصلًا جميع الأوجه التي يجب أن يتصل بها v . على سبيل المثال، إضافة رأس واحد إلى رسم بياني خارجي مستوٍ (رسم بياني برتبة τ = 1 ) ينتج عنه رسم بياني مستوٍ. عندما يكون G \ { v } متصلًا ثلاثيًا، يكون هذا الحد ضمن عامل ثابت من الأمثل: كل تمثيل سطحي لـ G يتطلب رتبة لا تقل عن τ / 160. ومع ذلك، فإن تحديد الرتبة المثلى لتمثيل سطحي لرسم بياني رأسي هو مسألة صعبة حسابيًا (NP-hard) . ^{[ 14 ]}

باستخدام أشجار SPQR لترميز التمثيلات الممكنة للجزء المستوي من رسم بياني رأسي، يُمكن حساب رسم بياني في المستوى بحيث تقتصر التقاطعات على الرأس، مما يُقلل العدد الإجمالي للتقاطعات، وذلك في وقت متعدد الحدود. ^{[ 15 ]} مع ذلك، إذا سُمح بتقاطعات عشوائية، يصبح تقليل عدد التقاطعات مسألة صعبة حسابيًا (NP-hard)، حتى في الحالة الخاصة للرسوم البيانية الرأسية المُشكّلة بإضافة حافة واحدة إلى رسم بياني مستوٍ. ^{[ 16 ]}

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

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

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

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

إذا كان الرسم البياني رسمًا رأسيًا، فليس بالضرورة أن يكون له رأس فريد. على سبيل المثال، في الرسمين البيانيين غير المستويين الأدنى K₅ و _K₃ , _₃ ، يمكن اختيار أي رأس كرأس. عرّف فاغنر ( 1967 ، 1970 ) الرسم البياني شبه المستوي بأنه رسم بياني رأسي غير مستوٍ يتميز بخاصية أن جميع رؤوسه يمكن أن تكون رأسًا للرسم البياني؛ وبالتالي، فإن _K₅ و K₃ , _₃ شبه مستويين. وقدّم تصنيفًا لهذه الرسوم البيانية إلى أربع مجموعات فرعية، إحداها تتكون من الرسوم البيانية التي (مثل سلالم موبيوس ) يمكن تضمينها على شريط موبيوس بطريقة تتطابق فيها الحافة الوحيدة للشريط مع دورة هاميلتونية للرسم البياني. قبل إثبات نظرية الألوان الأربعة ، أثبت أن كل رسم بياني شبه مستوٍ يمكن تلوينه بأربعة ألوان على الأكثر، باستثناء الرسوم البيانية المُشكَّلة من رسم بياني دائري ذي حلقة خارجية فردية باستبدال رأس المحور برأسين متجاورين، والتي تتطلب خمسة ألوان. بالإضافة إلى ذلك، أثبت أنه باستثناء حالة واحدة (الرسم البياني المُكمِّل للمكعب ذي الرؤوس الثمانية )، فإن كل رسم بياني شبه مستوٍ له تمثيل مُضمَّن على المستوى الإسقاطي . 

ومع ذلك، فإن عبارة "الرسم البياني شبه المستوي" غامضة للغاية: فقد تم استخدامها أيضًا للإشارة إلى الرسوم البيانية الرأسية، ^{[ 18 ]} والرسوم البيانية التي تم تشكيلها عن طريق إضافة حافة واحدة إلى رسم بياني مستو، ^{[ 19 ]} والرسوم البيانية التي تم تشكيلها من رسم بياني مستو مضمن عن طريق استبدال عدد محدود من الوجوه بـ "دوامات" ذات عرض مسار محدود ، ^{[ 20 ]} بالإضافة إلى مجموعات أخرى من الرسوم البيانية أقل تحديدًا بدقة.

يُقال عن الرسم البياني المجرد أنه ذو n قمة إذا أمكن جعله مستوياً بحذف n رأس أو أقل. ويُقال أيضاً عن الرسم البياني ذي 1 قمة أنه ذو قمة.

بحسب ليبتون وآخرون (2018) ، يُقال عن الرسم البياني أنه ذو رأس حافة إذا كان هناك ضلع فيه يمكن حذفه ليصبح الرسم البياني مستوياً. ويُقال عن الرسم البياني أنه ذو رأس انكماش إذا كان هناك ضلع فيه يمكن تقليصه ليصبح الرسم البياني مستوياً.

بشكل عام، إذا كانت X فئة من الرسوم البيانية، فإن الرسم البياني "الرأسي- X " هو رسم بياني يمكن إضافته إلى الفئة X بحذف رأس واحد. على سبيل المثال، الرسم البياني "الرأسي-المكمل " هو رسم بياني G يحتوي على رأس v بحيث يكون G-v رسمًا بيانيًا مكملًا.

• الهرم متعدد السطوح ، وهو شكل متعدد السطوح رباعي الأبعاد تشكل رؤوسه وحوافه رسمًا بيانيًا للرأس، حيث يكون الرأس مجاورًا لكل رأس من رؤوس الرسم البياني متعدد السطوح.