هل هناك خوارزمية للعثور على أفضل مجموعة من الأزواج من الرموز في رسم بياني مرجح دون تكرار؟

Question

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

• تحتوي المجموعة على أصغر وزن حافة أقصى لأي مجموعة تتسرب من المعايير الأخرى الممكنة
• يتم توصيل كل قمة الرأس بحافة واحدة بالضبط في المجموعة

جميع الأوزان إيجابية

لا يمكن أن يفكر DI في قوة أفضل من القوة الغاشمة ، لكنني لا أدركها على أنها NP بشدة.

Answer 1

طريقة واحدة لحل هذه المشكلة في وقت الحدود هي كما يلي:

1. فرز الأوزان الحافة في وقت O (e log e)
2. لكل حافة ، قم بتعيينه على وزن زائف E '= 2^{الموضع في الطلب} في ~ o (e) الوقت
3. ابحث عن الحد الأدنى لمطابقة الوزن المثالي بين الأوزان الزائفة في وقت مثل O (v^3) (اعتمادًا على الخوارزمية التي تختارها ، قد تكون أبطأ أو أسرع)

هذا يقلل من أكبر حافة تحتوي على المطابقة المثالية ، وهو بالضبط ما تبحث عنه في وقت مثل O (v^3).

وترد أدناه مصادر لكيفية القيام الجزء 3 أدناه
[1] http://www2.isye.gatech.edu/~wcook/papers/match_ijoc.pdf
[2] http://www.cs.illinois.edu/class/sp10/cs598csc/lectures/lecture11.pdf
[3] http://www.cs.ucl.ac.uk/staff/v.kolmogorov/papers/blossom5.ps

مع Sample C ++ مصدر متاح في http://ciju.wordpress.com/2008/08/10/min-cost-perfect-gatching/

Answer 2

جرب هذا (لقد اعتقدت هذا الأمر فقط ، لذا لم أحصل على دليل على أنه سيعطي إجابة مثالية أو ما إذا كان سيؤدي إلى حل في كل حالات):

1. ابحث عن أثقل رؤوس V (A ، B)
2. إزالة Vertice V من الرسم البياني
3. إذا كان A متصلاً فقط بفيروس واحد آخر T (A ، C) ، فقم بإزالة جميع الحواف الأخرى المتصلة بـ C ، كرر الخطوة 3 مع تلك الحواف أيضًا
4. إذا كان B متصلاً فقط بدفتر واحد آخر (B ، D) ، فقم بإزالة جميع الحواف الأخرى المتصلة بـ D ، كرر الخطوة 4 مع تلك الحواف أيضًا
5. كرر من الخطوة رقم 1