في نظرية الرسومات، الرسم الجزئي المولد من رسم آخر هو عبارة عن مجموعة جزئية من رؤوس الرسم (الأكبر) وجميع الأضلاع التي تربط كل زوج من رؤوس المجموعة الجزئية.

تعريف

بصيغة رياضية، ليكن G = (V, E) أي رسم ما، ولتكون SV أي مجموعة جزئية من رؤوس G . بالتالي فإن الرسم الجزئي المولد G[S] هو الرسم الذي مجموعة رؤوسه هي المجموعة S ومجموعة أضلاعه هي أضلاع من المجموعة E والتي تكون كلتا نهايتيه عناصر من S.[1] نفس التعريف ينطبق أيضا على الرسم الموجه والرسم الغير موجه وأيضا الرسم المتعدد الأضلاع.

ممكن أيضا تسمية الرسم الجزئي المولد بالرسم الجزئي المولد لـ بالمجموعة.

أمثلة

 
مسألة snake-in-the-box والتي تهتم بأطول ممر مولد ف الرسومات Hypercube .

هنا أنواع مهمه من الرسم الجزئي المولد منها:

حساب

مسألة تشاكل الرسم الجزئي المولد هي نوع من مسألة تشاكل الرسم الجزئي التي تهدف لإختبار ماإذا كان من الممكن إثبات أن أحد الرسمين هو عبارة عن رسم جزئي مولد لرسم آخر. تعتبر هذه المسألة كثيرة حدود غير قطعية كاملة لأنها حالة خاصة من مسألة مسألة clique problem.[4]

مراجع

  1. ^ Diestel، Reinhard (2006)، Graph Theory، Graduate texts in mathematics، Springer-Verlag، ج. 173، ص. 3–4، ISBN:9783540261834، مؤرشف من الأصل في 2020-01-25
  2. ^ Howorka، Edward (1977)، "A characterization of distance-hereditary graphs"، The Quarterly Journal of Mathematics. Oxford. Second Series، ج. 28، ص. 417–420، DOI:10.1093/qmath/28.4.417، MR:0485544.
  3. ^ Chudnovsky، Maria؛ Robertson، Neil؛ Seymour، Paul؛ Thomas، Robin (2006)، "The strong perfect graph theorem"، حوليات الرياضيات، ج. 164، ص. 51–229، arXiv:math/0212070، DOI:10.4007/annals.2006.164.51، MR:2233847، مؤرشف من الأصل في 2010-06-18.
  4. ^ Johnson، David S. (1985)، "The NP-completeness column: an ongoing guide"، Journal of Algorithms، ج. 6، ص. 434–451، DOI:10.1016/0196-6774(85)90012-4، MR:0800733.