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

شرح مفصل

لتصور شجرة الامتداد ، قم أولاً بتصوير رسم بياني غير موجه: على سبيل المثال ، مجموعة عشوائية من النقاط المتصلة بواسطة خطوط. يجب أن تكون الاتصالات غير موجهة ؛ وهذا يعني أنه يمكنك السفر في أي اتجاه على الخطوط للانتقال من نقطة إلى أخرى. يجب توصيل كل نقطة بالباقي بطريقة ما ، وقد يكون لكل نقطة اتصالات متعددة.

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

الرسم البياني ، شروط الشبكة ، بروتوكول شجرة الامتداد