بيان جزئي محدث

أمثلة

هنا أنواع مهمه من البيان الجزئي المحدَث منها:

علاوةً على ذلك، مجموعة الجوار لرأس ما تمثل بيان جزئي مُحدَث لكل الرؤوس المجاورة لهذا الرأس.

علاوةً على ذلك، المطابقات المولدة تعتبر كذلك رسومات جزئية مولدة والتي هي عبارة عن مطابقات.

من جهة ثانية، البيان Cliques والمجموعات المستقلة (independent sets ) هما كذلك بيانات جزئية مُحدَثة، حيث يمثل الأول بيانًا تامًا والأخر رسومات بدون أضلاع.

كذلك، الدورات المولده (Induced paths) هي كذلك رسومات جزئية مولده أو دورات. مصطلح girth لأي بيان هو طول أقصر دوره في هذا البيان والتي هي دائما دورة مولدة. بناء على نظرية البيان التام القويه فإن الدورات المولدة ومكملاتها تلعب دورا مهما في خواص الرسومات التامه.

علاوةً على ذلك، ممرات مولده: وهي رسومات جزئية مولده تمثل ممر نظرية الرسومات. أقصر ممر بين أي رأسين في أي بيان غير موزون هو دائما ممر مولد لأن أي أضلاع إضافية بين أي رأسين ممكن أن تجعله غير مولد ولا أقصر ممر كذلك. بالمقابل، في البيان distance-hereditary كل ممر مولد هو كذلك أقصر ممر بهذا البيان.

حساب

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

تعريف

من جانب آخر، بصيغة رياضية، ليكن أي بيان ما، ولتكون أي مجموعة جزئية من رؤوس . بالتالي فإن البيان الجزئي المُحدَث هو البيان الذي مجموعة رؤوسه هي المجموعة ومجموعة أضلاعه هي أضلاع من المجموعة والتي تكون كلتا نهايتيه عناصر من . نفس التعريف ينطبق كذلك على البيان الموجَّه والبيان غير الموجَّه وأيضًا البيان المتعدد الوصلات.

علاوةً على ذلك، ممكن كذلك تسمية البيان الجزئي المحدَث بالبيان الجزئي المحدَث بالمجموعة.