الحد الأدنى للشجرة الممتدة أو الشجرة الممتدة للوزن الأدنى عبارة عن مجموعة فرعية من حواف رسم بياني غير موجه متصل ومرجح بالحافة يربط جميع الرؤوس معًا ، بدون أي دورات وبأقل وزن إجمالي ممكن للحافة. أي أنها شجرة ممتدة مجموع أوزان حوافها أصغر ما يمكن.
ما هو الحد الأدنى للشجرة الممتدة مع المثال؟
الحد الأدنى للشجرة الممتدة هو نوع خاص من الشجرة يقلل أطوال (أو "أوزان") حواف الشجرة. مثال على ذلكشركة كبلات تريد وضع خط لأحياء متعددة؛ من خلال تقليل كمية الكابلات الموضوعة ، ستوفر شركة الكابلات المال. الشجرة لها مسار واحد يربط أي رأسين.
كيف تجد الحد الأدنى للشجرة الممتدة؟
ابحث عنأقرب جار غير ملون للرسم الفرعي الأحمر(أي ، أقرب قمة إلى أي رأس أحمر). قم بتمييزه والحافة التي تربط الرأس بالرسم الفرعي الأحمر باللون الأحمر. كرر الخطوة 2 حتى يتم تمييز جميع الرؤوس باللون الأحمر. الرسم البياني الأحمر هو الحد الأدنى من الشجرة الممتدة.
ماذا تقصد بامتداد الشجرة والحد الأدنى للشجرة الممتدة؟
الشجرة الممتدة للرسم البياني عبارة عن مجموعة من الحواف المتصلة التي تتضمن كل رأس في الرسم البياني ، ولكنها لا تشكل دورة. … الحد الأدنى لشجرة الامتداد هوالشجرة التي يكون لأوزانها التراكمية أصغر قيمة ، ولكن.
ما هو الفرق بين الشجرة الممتدة والحد الأدنى للشجرة الممتدة؟
إذا كان الرسم البيانيمرجحًا بالحافة ، يمكننا تحديدالوزنللشجرة الممتدة كمجموع أوزان جميع حوافها. الحد الأدنى للشجرة الممتدة هو الشجرة الممتدة التي يكون وزنها هو الأصغر بين جميع الأشجار الممتدة الممكنة.
