رسم جزئي مولد

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

تعريف

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

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

أمثلة

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

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

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

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

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

المطابقات المولدة تعتبر أيضا رسومات جزئية مولدة والتي هي عبارة عن مطابقات.

مجموعة الجوار لرأس ما تمثل رسم جزئي مولد لكل الرؤوس المجاورة لهذا الرأس.

حساب

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

مراجع

Diestel, Reinhard (2006)، Graph Theory، Graduate texts in mathematics، Springer-Verlag، ج. 173، ص. 3–4، ISBN 9783540261834، مؤرشف من الأصل في 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.
Chudnovsky, Maria؛ Robertson, Neil؛ Seymour, Paul؛ Thomas, Robin (2006)، "The strong perfect graph theorem"، حوليات الرياضيات، 164 (1): 51–229، arXiv:math/0212070، doi:10.4007/annals.2006.164.51، MR 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.

بوابة رياضيات

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Diestel, Reinhard (2006)، Graph Theory، Graduate texts in mathematics، Springer-Verlag، ج. 173، ص. 3–4، ISBN 9783540261834، مؤرشف من الأصل في 25 يناير 2020

[2] 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.

[3] Chudnovsky, Maria؛ Robertson, Neil؛ Seymour, Paul؛ Thomas, Robin (2006)، "The strong perfect graph theorem"، حوليات الرياضيات، 164 (1): 51–229، arXiv:math/0212070، doi:10.4007/annals.2006.164.51، MR 2233847، مؤرشف من الأصل في 18 يونيو 2010.

[4] 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.