العثور على دورة صغيرة في الرسم البياني المستوي

Question

لدي هندسية غير موجهة رسم بياني مستو, ، وهو رسم بياني حيث يكون لكل عقدة موقع ولا تتقاطع فيه حافتان، وأريد العثور على جميع الدورات التي ليس لها حواف تتقاطع معها.

هل هناك أي حلول جيدة معروفة لهذه المشكلة؟

---

ما أخطط للقيام به هو نوع من A* مثل الحل:

• أدخل كل حافة في كومة دقيقة كمسار
• تمديد أقصر طريق مع كل خيار
• مسارات الإعدام التي تعود إلى مكان آخر غير البداية (قد لا تكون هناك حاجة إليها)
• مسارات الإعدام التي ستكون الثالثة لاستخدام حافة معينة

هل يرى أحد مشكلة في هذا؟هل ستنجح حتى؟

Answer 1

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

Answer 2

تُعرف "حافة العبور"، كما تسميها، عمومًا باسم أ وتر.وبالتالي، مشكلتك هي العثور على جميع الدورات الوترية.

هذه الورقة يبدو أنه قد يساعد.

Answer 3

والطريقة البسيطة للقيام بذلك هي ببساطة الخروج وتعداد كل وجه.المبدأ بسيط:

• نحتفظ بإعلام "α-visited" و"β-visited" لكل حافة، وزوج من القوائم المرتبطة بشكل مزدوج للحواف غير التي تمت زيارتها لكل علامة من هذا القبيل.يجب أن يتوافق القسمان 'α' و'β' مع قسم من المستوى على الخط المقابل للحافة المعنية؛أي جانب هو α وأي جانب هو β هو أمر تعسفي.
• لكل قمة V:
  • لكل زوج متجاور من الحواف E = (V_1, V)، E'=(V_2، V) (على سبيل المثال، قم بالفرز حسب الزاوية، وخذ الأزواج المتجاورة، بالإضافة إلى الأول + الأخير):
  • حدد الجانب S من E (S=α أو β) V_2 الذي يقع عليه.
  • قم بتحريك البلاط بدءًا من V باستخدام الجانب S من E، كما هو موضح أدناه:

يتم تنفيذ المشي على البلاط عن طريق:

• دع V = V_init
• حلقة:
  • V_next = قمة E التي ليست V
  • E' = الحافة المجاورة لـ E من V_next الموجودة على الجانب الحالي من E
  • S' = جانب E' الذي يحتوي على V
  • إذا كان V_next = V، فقد وجدنا حلقة؛قم بتسجيل جميع الحواف التي مررنا بها في الطريق، وقم بوضع علامة على أزواج الحواف هذه على أنها تمت زيارتها.
  • إذا كانت E' = E (هناك حافة واحدة فقط)، فقد وصلنا إلى طريق مسدود؛إجهاض هذه المسيرة
  • بخلاف ذلك، دع V = V_next، E = E'، S = S' واستمر.

آمل أن يكون هذا الشعور بها؛ربما يحتاج إلى بعض الرسوم البيانية لتوضيح ...