ما هو الفرق بين الغابة والغابة الممتدة في نظرية الرسم البياني؟


الاجابه 1:

الغابة هي أي مجموعة من الأشجار.

"الغابة الممتدة" هي مجموعة من الأشجار تشمل ("الامتداد" أو "الغطاء") كل قمة في الرسم البياني. هناك نوعان من التفسيرات المتنافسة:

  • "غابة ممتدة بالكامل" أو "غابة ممتدة قصوى": تتم تغطية كل مكون متصل من الرسم البياني بشجرة ممتدة. أي أنه يوجد العديد من الأشجار التي توجد بها مكونات متصلة وليس أكثر. أو أي مجموعة من الأشجار تغطي القمم ، حتى لو كانت مجموعة أصغر من الأشجار تفعل ذلك. قد يكون هناك أشجار أكثر من المكونات المتصلة.

على سبيل المثال ، ضع في اعتبارك هذا الرسم البياني:

إليك غابة على الرسم البياني (العقد والحواف الخضراء) ، وتتألف من شجرتين ولكن مع حذف بعض القمم.

إليك غابة ممتدة (جميع القمم) تحتوي على شجرة واحدة لكل مكون متصل ، "غابة ممتدة بالكامل".

فيما يلي غابة ممتدة مختلفة ، تستخدم ثلاثة أشجار بدلاً من ذلك لتغطية جميع القمم: