في نظرية الرسومات، الرسم الجزئي المولد من رسم آخر هو عبارة عن مجموعة جزئية من رؤوس الرسم (الأكبر) وجميع الأضلاع التي تربط كل زوج من رؤوس المجموعة الجزئية.
تعريف
بصيغة رياضية، ليكن G = (V, E) أي رسم ما، ولتكون S ⊂ V أي مجموعة جزئية من رؤوس G . بالتالي فإن الرسم الجزئي المولد G[S] هو الرسم الذي مجموعة رؤوسه هي المجموعة S ومجموعة أضلاعه هي أضلاع من المجموعة E والتي تكون كلتا نهايتيه عناصر من S [1] . نفس التعريف ينطبق ايضا على الرسم الموجه والرسم الغير موجه وأيضا الرسم المتعدد الأضلاع.
ممكن أيضا تسمية الرسم الجزئي المولد بالرسم الجزئي المولد لـ بالمجموعة .
أمثلة
هنا أنواع مهمه من الرسم الجزئي المولد منها:
- ممرات مولده : وهي رسومات جزئية مولده تمثل ممر نظرية الرسومات . أقصر ممر بين أي رأسين في أي رسم غير موزون هو دائما ممر مولد لأن أي أضلاع إضافية بين أي رأسين ممكن أن تجعله غير مولد ولا أقصر ممر أيضا. بالمقابل، في الرسم distance-hereditary كل ممر مولد هو أيضا أقصر ممر بهذا الرسم [2].
- الدورات المولده (Induced paths) هي أيضا رسومات جزئية مولده أو دورات. مصطلح girth لأي رسم هو طول أقصر دوره في هذا الرسم والتي هي دائما دورة مولدة. بناء على نظرية الرسم التام القويه فإن الدورات المولدة ومكملاتها تلعب دورا مهما في خواص الرسومات التامه[3].
- الرسم Cliques والمجموعات المستقلة ( independent sets ) هما أيضا رسومات جزئية مولدة، حيث يمثل الأول رسومات تامة والأخر رسومات بدون أضلاع.
- المطابقات المولدة تعتبر أيضا رسومات جزئية مولدة والتي هي عبارة عن مطابقات .
- مجموعة الجوار لرأس ما تمثل رسم جزئي مولد لكل الرؤوس المجاورة لهذا الرأس.
حساب
مسألة تشاكل الرسم الجزئي المولد هي نوع من مسألة تشاكل الرسم الجزئي التي تهدف لإختبار ماإذا كان من الممكن إثبات أن احد الرسمين هو عبارة عن رسم جزئي مولد لرسم آخر. تعتبر هذه المسألة كثيرة حدود غير قطعية كاملة لأنها حالة خاصة من مسألة مسألة clique problem[4].
مراجع
- Diestel, Reinhard (2006), Graph Theory, 173, Springer-Verlag, صفحات 3–4, , مؤرشف من الأصل في 25 يناير 2020
- Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics. Oxford. Second Series, 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR = 0485544 0485544 .
- Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, arXiv:, doi:10.4007/annals.2006.164.51, MR = 2233847 2233847, مؤرشف من الأصل في 18 يونيو 2010 .
- Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms, 6 (3): 434–451, doi:10.1016/0196-6774(85)90012-4, MR = 0800733 0800733 .