عالقة على حل مشكلة الحد الأدنى مشكلة شجرة

Question

لقد خفضت مشكلتي للعثور على الحد الأدنى من الشجرة الممتدة في الرسم البياني. لكنني أريد أن يكون هناك عقبة أخرى وهو ذلك لا ينبغي أن تتجاوز الدرجة الكلية لكل Vertex عامل ثابت معين. وبعد كيف يمكنني نموذج مشكلتي؟ هل MST المسار الخطأ؟ هل تعرف أي خوارزميات ستساعدني؟

مشكلة أخرى: الرسم البياني الخاص بي يحتوي على أوزان حافة مكررة، فهل هناك طريقة لحساب عدد MSTS الفريد؟ هل توجد خوارزميات تفعل هذا؟

شكرا.

تحرير: حسب الدرجة، أعني إجمالي عدد الحواف التي تربط قمة الرأس. عن طريق تكرار وزن الحافة أقصد أن اثنين من الحواف لها نفس الوزن.

Answer 1

توضح هذه الورقة كيفية العثور عليها، في وقت متعدد الحدود، شجرة ممتد من الحد الأقصى درجة D + 1 على الأقل جيدة مثل أي تمتد شجرة الحد الأقصى درجة D: http://www.andrew.cmu.edu/user/mohits/mbdst.pdf.

/ / تحرير الرابط الأصلي غير نشط حاليا، حاول http://research.microsoft.com/pubs/80193/mbdst.pdf. في حين أن.

Answer 2

حسنا، من السهل إثبات أنه قد لا يكون هناك حل: ما عليك سوى إجراء رسم بياني المدخلات شجرة لها قمة أعلى درجة أعلى من الحد الخاص بك ..

Answer 3

كان لدى Garey Johnson هذه المشكلة تقلل إلى هاميلتون :( لذلك ساعد هذا واحد. تقريب أول واحد: http://caislab.icu.ac.ac.kr/lecture/data/2003/spring/itice514/project/m03.ppt.ومع ذلك، فإن نماذج عمل أفضل موضع تقدير ...

عد: http://mathworld.wolfram.com/spanningtree.html. وبعد وفقا لهذا، فإن الرياضيات لديها وظيفة. أي اقتراحات في هذا واحد؟