قم بفرز الرسم البياني لجعل أكبر عدد ممكن من الأسهم

Question

أحتاج إلى فرز عقد الرسم البياني الموجه بحيث يكون عدد الأسهم الذي يتدفق إلى الوراء (مقابل ترتيب الفرز) ضئيلا.

أستطيع أن أفكر في الخوارزميات (مثل الحفاظ على خلط العقد حتى لا تحسن أي مبادلة الأشياء) لكنني لست متأكدا مدى سرعة تشغيلها أو ما إذا كانوا يصلون إلى أفضل حل.

ما هو اسم وتعقيد هذه المشكلة؟

Answer 1

بعد بعض التفكير، أدركت أن المشكلة يمكن تقسيمها في اثنين:

1. تحديد أكبر مجموعة فرعية أكريكليكليك من الرسم البياني (الذي هو np-hard)
2. علم طوبولوجيا (وهو أسهل كثيرا)

Answer 2

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

إذا كنت تقوم بهذا لأغراض التصور هناك مكتبة تقديم الرسم البياني graphviz. هذا يفعل شيئا مشابها للغاية لما تصفه ثم يضع العقد. من السهل دمج واستخدام وستجعل الشاشة أو مجموعة متنوعة من تنسيقات الإخراج المختلفة.