خوارزميات لصناعة الرسم البياني متعدد الهيكلية (مخطط مخطط 3 متصل) Isomorphism؟

Question

لقد وضعت بعض الأبحاث حول موضوع ISOMorphism الرسم البياني للرسوم البيانية المتصلة بالكتاب 3، ولكن هناك وفرة من خوارزميات من تقييد مختلف، والتعقيد النظري، وتيرة الاستخدام وأواجه مشكلة في العثور على واحدة تقفخارج:

• من السهل فهم
يمكن تنفيذ
• بأقصى قدر من الوضوح
• أداء عملي جيد على الرسوم البيانية الصغيرة (حتى القمم في العشرات)

من الصعب أن نعرف دون فهم الخوارزميات المختلفة لنفسي ما إذا كنت أفضل مع أحد الخوارزميات القديمة والمتخصصة لهذه المشكلة أو الأحدث والأكثر العامة. بين جميع المرشحين المحتملين، أي واحد هو / تلك هي أفضل ملاءمة؟

Answer 1

أعتقد أن خوارزمية Weinberg تناسب الفاتورة.

• يسهل فهمها: حساب أنظمة الدوران for g و h كما هو بمناسبة خوارزمية اختبار النوايا. نظرا لأن G و H. هي 3 متصلات، فإن أنظمة الدوران هذه هي Isomorphic لتبادل عقارب الساعة وعكس اتجاه عقارب الساعة إذا وفقط إذا كانت G و H isomorphic. اختر DART (= EDGE مع اتجاه مشار إليه) D في G ومحاولة تعيينه إلى جميع السهام E في H (وكرر الاتجاه الآخر من H). نظرا لأن G متصل، يمكن الوصول إلى جميع السهام الأخرى D 'من D من D من خلال تأليف العمليات لنظام الدوران ل G. تطبيق العمليات المقابلة إلى E وتحقق مما إذا كانت هناك إزدرام.

• أقصى الوضوح: بصرف النظر عن اختبار النوايا، ما سبق هو صفحة من التعليمات البرمجية. ربما يمكنك إعادة استخدام اختبار حويث شخص آخر؟ هناك واحد في دفعة، على سبيل المثال. إذا لم يكن الأمر كذلك، ما زلت أعتقد تنفيذ نفسك أسهل من إعادة كتابة Nauty.

• الأداء العملي الجيد على الرسوم البيانية الصغيرة: بعد اختبار النوايا، فإن خوارزمية Weinberg هي أساسا اجتيازات عمق متزامنة أولا لكل دارت. إجمالي وقت التشغيل هو O (| V | ^{2 ) مع عدم وجود ثوابت كبيرة كامنة.}