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

== تعريف ==
بصيغة رياضية، ليكن {{تعبير رياضي|1=''G'' = (''V'', ''E'')}} أي رسم ما، ولتكون {{تعبير رياضي|''S'' ⊂ ''V''}} أي مجموعة جزئية من رؤوس ''{{mvar|G}}'' . بالتالي فإن الرسم الجزئي المولد {{تعبير رياضي|''G''[''S'']}} هو الرسم الذي مجموعة رؤوسه هي المجموعة ''{{mvar|S}}'' ومجموعة أضلاعه هي أضلاع من المجموعة ''{{mvar|E}}'' والتي تكون كلتا نهايتيه عناصر من ''{{mvar|S}}''.<ref>{{استشهاد|عنوان=Graph Theory|المجلد=173|سلسلة=Graduate texts in mathematics|الأول=Reinhard|الأخير=Diestel|ناشر=Springer-Verlag|سنة=2006|isbn=9783540261834|صفحات=3–4|مسار= https://books.google.com/books?id=aR2TMYQr2CMC&pg=PA3|مسار أرشيف= https://web.archive.org/web/20200125220037/https://books.google.com/books?id=aR2TMYQr2CMC&pg=PA3|تاريخ أرشيف=2020-01-25}}</ref> نفس التعريف ينطبق أيضا على الرسم الموجه والرسم الغير موجه وأيضا الرسم المتعدد الأضلاع.

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

== أمثلة ==
[[ملف:Snake in the box.svg|تصغير|مسألة [[:en:Snake-in-the-box|snake-in-the-box]] والتي تهتم بأطول ممر مولد ف الرسومات [[:en:Hypercube graph|Hypercube]] . ]]هنا أنواع مهمه من الرسم الجزئي المولد منها:

* ممرات مولده: وهي رسومات جزئية مولده تمثل ممر نظرية الرسومات. أقصر ممر بين أي رأسين في أي رسم غير موزون هو دائما ممر مولد لأن أي أضلاع إضافية بين أي رأسين ممكن أن تجعله غير مولد ولا أقصر ممر أيضا. بالمقابل، في الرسم [[:en:Distance-hereditary graph|distance-hereditary]] كل ممر مولد هو أيضا أقصر ممر بهذا الرسم.<ref>{{استشهاد|الأخير=Howorka|الأول=Edward|عنوان=A characterization of distance-hereditary graphs|صحيفة=The Quarterly Journal of Mathematics. Oxford. Second Series|المجلد=28|العدد=112|سنة=1977|صفحات=417–420|mr=0485544|مسار= http://qjmath.oxfordjournals.org/cgi/reprint/28/4/417|doi=10.1093/qmath/28.4.417|مسار أرشيف= https://archive.today/20130415154039/http://qjmath.oxfordjournals.org/cgi/reprint/28/4/417|تاريخ أرشيف=2013-04-15}}.</ref>
* [[:en:Induced path|الدورات المولده]] ([[:en:Induced path|Induced paths]]) هي أيضا رسومات جزئية مولده أو دورات. مصطلح [[:en:Girth (graph theory)|girth]] لأي رسم هو طول أقصر دوره في هذا الرسم والتي هي دائما دورة مولدة. بناء على [[:en:Strong perfect graph theorem|نظرية الرسم التام القويه]] فإن الدورات المولدة ومكملاتها تلعب دورا مهما في خواص [[:en:Perfect graph|الرسومات التامه]].<ref>{{استشهاد|الأخير1=Chudnovsky|الأول1=Maria|مؤلف1-وصلة=Maria Chudnovsky|الأخير2=Robertson|الأول2=Neil|مؤلف2-وصلة=Neil Robertson (mathematician)|الأخير3=Seymour|الأول3=Paul|مؤلف3-وصلة=Paul Seymour (mathematician)|الأخير4=Thomas|الأول4=Robin|مؤلف4-وصلة=Robin Thomas (mathematician)|doi=10.4007/annals.2006.164.51|العدد=1|صحيفة=[[حوليات الرياضيات]]|صفحات=51–229|عنوان=The strong perfect graph theorem|مسار= http://annals.princeton.edu/annals/2006/164-1/p02.xhtml|المجلد=164|سنة=2006|mr=2233847|arxiv=math/0212070|مسار أرشيف= https://web.archive.org/web/20100618172636/http://annals.princeton.edu/annals/2006/164-1/p02.xhtml|تاريخ أرشيف=2010-06-18}}.</ref>
* الرسم [[:en:Clique (graph theory)|Cliques]] والمجموعات المستقلة ([[:en:Independent set (graph theory)|independent sets]] ) هما أيضا رسومات جزئية مولدة، حيث يمثل الأول [[رسم بياني كامل|رسومات تامة]] والأخر [[:en:Null graph#Edgeless graph|رسومات بدون أضلاع]].
* [[:en:Induced matching|المطابقات المولدة]] تعتبر أيضا رسومات جزئية مولدة والتي هي عبارة عن [[المطابقة (نظرية الرسوم البيانية)|مطابقات]].
* [[:en:Neighbourhood (graph theory)|مجموعة الجوار]] لرأس ما تمثل رسم جزئي مولد لكل الرؤوس المجاورة لهذا الرأس.
*

== حساب ==
[[:en:Induced subgraph isomorphism problem|مسألة تشاكل الرسم الجزئي]] المولد هي نوع من [[:en:Subgraph isomorphism problem|مسألة تشاكل الرسم الجزئي]] التي تهدف لإختبار ماإذا كان من الممكن إثبات أن أحد الرسمين هو عبارة عن رسم جزئي مولد لرسم آخر. تعتبر هذه المسألة [[مسألة كثيرة حدود غير قطعية كاملة|كثيرة حدود غير قطعية كاملة]] لأنها حالة خاصة من مسألة مسألة [[مشكلة المخطط الكامل ضمن مخطط|clique problem]].<ref>{{استشهاد|الأخير=Johnson|الأول=David S.|doi=10.1016/0196-6774(85)90012-4|العدد=3|صحيفة=Journal of Algorithms|mr=800733|صفحات=434–451|عنوان=The NP-completeness column: an ongoing guide|المجلد=6|سنة=1985}}.</ref>

== مراجع ==
{{مراجع}}
{{شريط بوابات|رياضيات}}

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

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

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

 أمثلة 
تصغير|مسألة snake-in-the-box والتي تهتم بأطول ممر مولد ف الرسومات Hypercube . هنا أنواع مهمه من الرسم الجزئي المولد منها:

 ممرات مولده: وهي رسومات جزئية مولده تمثل ممر نظرية الرسومات. أقصر ممر بين أي رأسين في أي رسم غير موزون هو دائما ممر مولد لأن أي أضلاع إضافية بين أي رأسين ممكن أن تجعله غير مولد ولا أقصر ممر أيضا. بالمقابل، في الرسم distance-hereditary كل ممر مولد هو أيضا أقصر ممر بهذا الرسم..
 الدورات المولده (Induced paths) هي أيضا رسومات جزئية مولده أو دورات. مصطلح girth لأي رسم هو طول أقصر دوره في هذا الرسم والتي هي دائما دورة مولدة. بناء على نظرية الرسم التام القويه فإن الدورات المولدة ومكملاتها تلعب دورا مهما في خواص الرسومات التامه..
 الرسم Cliques والمجموعات المستقلة (independent sets ) هما أيضا رسومات جزئية مولدة، حيث يمثل الأول رسومات تامة والأخر رسومات بدون أضلاع.
 المطابقات المولدة تعتبر أيضا رسومات جزئية مولدة والتي هي عبارة عن مطابقات.
 مجموعة الجوار لرأس ما تمثل رسم جزئي مولد لكل الرؤوس المجاورة لهذا الرأس.

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

 مراجع 

تصنيف:رياضيات
تصنيف:نظرية البيان