حساب حالات الفرعية

Question

دعنا نقول أن لدي رسم بياني كبير (عدة آلاف من العقدة) ز ورسم بياني موجه أصغر بكثير (3-5 عقدة) ز. أريد أن أحسب عدد الأشكال المتماثلة ز يكون في ز. بمعنى آخر ، أريد أن أعرف عدد مجموعات العقد الفريدة ز مباراة ز. أدرك أن هذه مثال لمشكلة التماثل الفرعي ، وبالتالي فهي مكتملة NP. ومع ذلك ، بالنظر إلى أنك قد تفترض ذلك ز هل صغير ، هل هناك أي خوارزمية فعالة بشكل معقول للقيام بذلك؟

Answer 1

على الرغم من أن التماثل الرسم البياني هو NP-COMPLETE بشكل عام ، إلا أن المشكلات التي تصادفها في العالم الحقيقي غالبًا ما تكون سهلة للغاية. يجب أن تكفي قوة الغاشمة البسيطة: دعنا M_i تكون مجموعة من الخرائط من العقد الأولى من G إلى عقد G. ابدأ بـ m_0 تحتوي على الخريطة الفارغة وتوسيع عقدة واحدة في كل مرة ، وتجاهل أي خرائط تنتهك القيد x->y IFF m(x)->m(y).

ستحتاج إلى طلب العقد في G بحيث يحدث الكثير من التقليم في وقت مبكر. على افتراض أن الرسوم البيانية الخاصة بك متفرق إلى حد ما ، ستحتاج إلى طلب يكمل أكبر عدد ممكن من الحواف في أقرب وقت ممكن ، وربما DFS من أعلى درجة.