شجرة ممتدة مقيدة بالدرجة

في نظرية المخططات ، تُعرف الشجرة الممتدة المقيدة بالدرجة بأنها شجرة ممتدة تكون فيها درجة الرأس القصوى محدودة بثابت معين k . وتتمثل مشكلة الشجرة الممتدة المقيدة بالدرجة في تحديد ما إذا كان لمخطط معين شجرة ممتدة من هذا النوع لقيمة معينة لـ k .

المدخلات: رسم بياني غير موجه مكون من n عقدة G(V,E)؛ عدد صحيح موجب k < n .

السؤال: هل تحتوي G على شجرة ممتدة لا يوجد فيها عقدة بدرجة أكبر من k ؟

هذه المسألة مصنفة ضمن فئة NP-complete ( غاري وجونسون ، 1979 ) . ويمكن إثبات ذلك من خلال اختزالها من مسألة المسار الهاميلتوني . وتبقى المسألة مصنفة ضمن فئة NP-complete حتى لو تم تثبيت قيمة k  عند ≥ 2. إذا عُرّفت المسألة بأن الدرجة يجب أن تكون ≤ k ، فإن حالة k = 2 للشجرة الممتدة ذات الدرجة المحدودة هي مسألة المسار الهاميلتوني. 

في الرسم البياني الموزون، تُعرف الشجرة الممتدة الدنيا المقيدة بالدرجة (DCMST) بأنها شجرة ممتدة مقيدة بالدرجة يكون مجموع حوافها هو الأدنى الممكن. ويُعد إيجاد شجرة ممتدة دنيا مقيدة بالدرجة مسألة صعبة الحل (NP-Hard). ^{[ 1 ]}

تم اقتراح خوارزميات استدلالية يمكنها حل المشكلة في وقت متعدد الحدود، بما في ذلك الخوارزميات الجينية والخوارزميات القائمة على النمل.

قدم فورر وراغافاتشاري (1994) خوارزمية تكرارية ذات وقت متعدد الحدود، والتي، عند إعطائها رسمًا بيانيًا${\displaystyle G}$، تُرجع شجرة ممتدة لا تتجاوز درجتها القصوى${\displaystyle \Delta ^{*}+1}$، أين${\displaystyle \Delta ^{*}}$يمثل الحد الأدنى والحد الأقصى الممكنين للدرجة على جميع الأشجار الممتدة. وبالتالي، إذا${\displaystyle k=\Delta ^{*}}$، ستُعيد هذه الخوارزمية إما شجرة ممتدة ذات درجة قصوى${\displaystyle k}$أو${\displaystyle k+1}$.

للحصول على الرسم البياني الثنائي الكامل${\displaystyle K_{m,n}}$أين${\displaystyle m\leq n}$:

${\displaystyle \Delta ^{*}(K_{m,n})=1+\left\lceil {\frac {n-1}{m}}\right\rceil }$

• غاري، مايكل ر.؛ جونسون ، ديفيد س. (1979)، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، دبليو إتش فريمان، ISBN 978-0-7167-1045-5. A2.1: ND1، ص  206.{{citation}}: CS1 maint: postscript ( link )
• Fürer, Martin; Raghavachari, Balaji (1994), "تقريب شجرة شتاينر ذات الدرجة الدنيا إلى ما يقارب الدرجة المثلى"، مجلة الخوارزميات ، 17 (3): 409-423 ، CiteSeerX 10.1.1.136.1089 ، doi : 10.1006/jagm.1994.1042 .