Degree-constrained spanning tree
گراف تھیوری میں، ڈگری سے محدود پھیلا ہوا درخت ایک پھیلا ہوا درخت ہے جہاں زیادہ سے زیادہ ورٹیکس ڈگری ایک خاص مستقل k تک محدود ہوتی ہے۔ ڈگری سے محدود پھیلا ہوا درخت کا مسئلہ اس بات کا تعین کرنا ہے کہ آیا کسی خاص گراف میں کسی خاص k کے لیے ایسا پھیلا ہوا درخت ہے۔ رسمی تعریف ان پٹ: n-نوڈ غیر ہدایت شدہ گراف G (V، E) ؛ مثبت عدد k <n۔ سوال: کیا G کا ایک پھیلا ہوا درخت ہے جس میں کسی نوڈ کی ڈگری k سے زیادہ نہیں ہے؟ این پی مکمل یہ مسئلہ این پی مکمل ہے۔ یہ ہیملٹنین راستے کے مسئلے میں کمی سے ظاہر کیا جا سکتا ہے۔ یہ NP-مکمل رہتا ہے یہاں تک کہ اگر k کو ≤2 کی قدر پر مقرر کیا جائے۔ اگر مسئلہ کی تعریف اس طرح کی جاتی ہے کہ ڈگری ≤ k ہونی چاہیے، تو ڈگری سے محدود پھیلے ہوئے درخت کا k = 2 معاملہ ہیملٹنین پاتھ کا مسئلہ ہے۔ ڈگری سے محدود کم از کم پھیلا ہوا درخت وزن والے گراف پر، ڈگری سے محدود کم از کم پھیلا ہوا درخت (ڈی سی ایم ایس ٹی) ایک ڈگری سے محدود پھیلا ہوا درخت ہے جس میں اس کے کناروں کے مجموعے میں کم از کم ممکنہ رقم ہوتی ہے۔ ڈی سی ایم ایس ٹی تلاش کرنا این پی ہارڈ کا مسئلہ ہے۔ ہیورسٹک الگورتھم جو کثیر الجہتی وقت میں مسئلے کو حل کر سکتے ہیں، تجویز کیے گئے ہیں، جن میں جینیاتی اور چیونٹی پر مبنی الگورتھم شامل ہیں۔ تخمینہ الگورتھم ایک تکراری کثیر الجہتی وقت الگورتھم دیتا ہے جو، ایک گراف دیا گیا ہے، ایک پھیلا ہوا درخت واپس کرتا ہے جس کی زیادہ سے زیادہ ڈگری اس سے بڑی نہیں ہوتی ہے، جہاں تمام پھیلا ہوا درختوں پر کم سے کم ممکنہ زیادہ سے زیادہ ڈگری ہوتی ہے۔ اس طرح، اگر، اس طرح کا الگورتھم یا تو زیادہ سے زیادہ ڈگری کا پھیلا ہوا درخت واپس کرے گا یا۔ حوالہ جات پھیلے ہوئے درخت NP-مکمل مسائل