طريقة سهلة لتحديد ما إذا كان رسم بياني معين هو رسم بياني فرعي لبعض الرسوم البيانية الأخرى؟

Question

أنا أبحث عن خوارزمية للتحقق مما إذا كان الرسم البياني المحدد هو رسم بياني فرعي لرسم بياني آخر.

لدي بعض الشروط لجعل مشكلة NP الكاملة هذه أكثر جدوى.

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

الرسم البياني الخطي A--B هو رسم بياني فرعي لـ A--B--A لكن A--A ليس رسمًا بيانيًا فرعيًا لـ A--B--A.

أي اقتراحات جيدة.هذا ليس سؤال الواجب المنزلي راجع للشغل.:د

Answer 1

إذا كانت الملصقات فريدة من نوعها ، للحصول على رسم بياني من الحجم N, ، هناك O(N^2) الحواف ، على افتراض عدم وجود حلقات ذاتية أو حواف متعددة بين كل زوج من القمم. لنستخدم E لعدد الحواف.

إذا قمت بتجميع الحواف المحددة في الرسم البياني الأصل ، فيمكنك المرور من خلال حواف الخريجة الفرعية ، والتحقق مما إذا كانت كل واحدة في جدول التجزئة (وفي الكمية الصحيحة ، إذا رغبت في ذلك). أنت تفعل هذا مرة واحدة لكل حافة ، لذلك ، O(E).

دعنا نسمي الرسم البياني G (مع N رؤوس) والخسم الفرعي المحتمل G_1 (مع M رؤوس) ، وتريد أن تجد G_1 is in G.

نظرًا لأن الملصقات ليست فريدة من نوعها ، فيمكنك ، مع البرمجة الديناميكية ، بناء المشكلات الفرعية على هذا النحو بدلاً من ذلك - بدلاً من وجود O(2^N) المشكلات الفرعية ، واحدة لكل مخطط فرعي ، لديك O(M 2^N) المشكلات الفرعية - واحدة لكل قمة في G_1 (مع M رؤوس) مع كل من الخراطيم الفرعية المحتملة.

G_1 is in G = isSubgraph( 0, empty bitmask)

ويتم إعداد الدول على هذا النحو:

isSubgraph( index, bitmask ) =
   for all vertex in G
       if G[vertex] is not used (check bitmask)
          and G[vertex]'s label is equal to G_1[index]'s label
          and isSubgraph( index + 1, (add vertex to bitmask) )
               return true
   return false

مع وجود حالة قاعدة index = M, ، ويمكنك التحقق من مساواة الحواف ، بالنظر إلى Bitmask (وتصنيف الملصقات الضمنية). بدلاً من ذلك ، يمكنك أيضًا القيام بالتحقق ضمن العبارة if - فقط تحقق من ذلك الحالي index, ، الخرف الفرعي الحالي G_1[0..index] مساوي ل G[bitmask] (مع نفس تعيين الملصقات الضمنية) قبل التكرار.

إلى عن على N = 20, ، يجب أن يكون هذا سريعًا بما فيه الكفاية.

(أضف مذكرتك ، أو يمكنك إعادة كتابة هذا باستخدام القيعان لأعلى DP).

Answer 2

حسنًا ، يجب أن أطرح السؤال الواضح. 1. لديك عشرين رأس. المشي كل رسم بياني في العمق أولاً ، الترتيب الأبجدي بين الأشقاء للحصول على سلاسل. 2. رسم بياني واحد هو فرع من آخر IFF سلسلة واحدة في أخرى.

إذن ، ما الذي يختبئ في مواصفات المشكلة لجعل هذا غير ممكن؟

Answer 3

يمكنك عرض هذا كمشكلة محاذاة.في الأساس تريد التوصل إلى رسم خرائط حقني أ يقوم بتعيين كل قمة في V_1 إلى قمة في V_2.خريطة المحاذاة أ يمكن تسجيلها على النحو التالي:

s(a) = \sum_{(v,w) \in E_1} \sigma(v, w, a(v), a(w)),

حيث \sigma(v, w, a(v), a(w)) = 1، إذا كان (a(v), a(w)) \in E_2 وإلا فسيكون 0.

أعتقد أن هذا يمكن صياغته في شكل برنامج خطي صحيح.