الحد الأدنى لدرجة امتداد الشجرة

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

تتمثل مشكلة القرار فيما يلي: بالنظر إلى الرسم البياني G وعدد صحيح k ، هل يمتلك G شجرة ممتدة بحيث لا تزيد درجة أي رأس عن k ؟ تُعرف هذه المشكلة أيضًا باسم مشكلة الشجرة الممتدة المقيدة بالدرجة .

يُعدّ إيجاد الشجرة الممتدة ذات الدرجة الدنيا في رسم بياني غير موجه مسألةً صعبةً من نوع NP . ويمكن إثبات ذلك من خلال بناء اختزال من مسألة المسار الهاميلتوني . أما بالنسبة للرسوم البيانية الموجهة، فإن إيجاد الشجرة الممتدة ذات الدرجة الدنيا يُعدّ أيضاً مسألةً صعبةً من نوع NP. ^{[ 1 ]}

يقدم كل من ر. كريشمان وب. راغافاتشاري (2001) خوارزمية تقريبية ذات وقت شبه متعدد الحدود لحل المشكلة للرسوم البيانية الموجهة. ^{[ 1 ]}

وجد كل من م. حق، ومحمد ر. الدين، ومحمد أ. قاسم (2007) خوارزمية زمنية خطية يمكنها إيجاد الشجرة الممتدة ذات الدرجة الدنيا للرسوم البيانية المتسلسلة المتوازية ذات الدرجات الصغيرة. ^{[ 2 ]}

وجد كل من جي ياو، ودي تشو، وإتش لي، وإس ما (2008) خوارزمية زمنية متعددة الحدود يمكنها إيجاد الشجرة الممتدة ذات الدرجة الدنيا للرسوم البيانية الموجهة غير الدورية . ^{[ 3 ]}