نوع طوبولوجي ، ولكن بنوع معين من التجمعات

Question

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

بالنظر إلى بعض التبعيات ، على سبيل المثال Genacodicetagpre

قد تكون هناك حلول متعددة لنوع طوبولوجي: Genacodicetagpre

كلاهما حلين.

أحتاج إلى خوارزمية تُرجع هذا: Genacodicetagpre

أي ، قم بإجراء "أ" ، ثم كل "ب" و "ج" ، ثم يمكنك إجراء "د". يتم تجميع جميع نقاط الالتباس أو عدم الاهتمام.

أعتقد أن الخوارزميات مثل تلك الموجودة في التصنيف الطبولوجي مع التجميع لن تتعامل مع الحالات بشكل صحيح مثل ما يلي. Genacodicetagpre

لهذا ، يجب أن تعود الخوارزمية Genacodicetagpre

هذا Genacodicetagpre يجب أن يعود

Genacodicetagpre

أثناء هذا Genacodicetagpre يجب أن يعود

Genacodicetagpre

وهذا Genacodicetagpre يجب أن يعود

Genacodicetagpre

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

تعديل للإجابة على الطلبات للحصول على مزيد من الأمثلة:

Genacodicetagpre يجب أن يعود

Genacodicetagpre

و Genacodicetagpre يجب أن يعود

Genacodicetagpre

و Genacodicetagpre يجب أن يعود

Genacodicetagpre

Answer 1

لنفترض أن G هو الإغلاق الانتقالي للرسم البياني.دع G 'هو الرسم البياني غير الموجه الذي ينتج عن إزالة الاتجاه من G وأخذ التكملة.المكونات المتصلة لـ G 'هي المجموعات التي تبحث عنها.