ابحث عن جميع عمليات الرسم البياني الكامل داخل الرسم البياني

Question

هل هناك خوارزمية أو طريقة معروفة للعثور على جميع الرسم البياني الكامل داخل الرسم البياني؟ لدي رسم بياني غير موجه غير مرغوب فيه وأحتاج إلى العثور على جميع الخراطيم الفرعية داخله حيث يتم توصيل كل عقدة في المخطط الفرعي بعقدة أخرى في الخرف الفرعي.

هل هناك خوارزمية موجودة لهذا؟

Answer 1

هذا هو المعروف باسم مشكلة الزمرة; ؛ إنه صعب وهو في NP-Complete بشكل عام ، ونعم هناك العديد من الخوارزميات للقيام بذلك.

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

من ويكيبيديا

في علوم الكمبيوتر ، تشير مشكلة الزمرة إلى أي من المشكلات المتعلقة بإيجاد خراطيم فرعية كاملة ("مجموعات") في رسم بياني ، أي مجموعات من العناصر التي يتم توصيل كل زوج من العناصر.

تشمل مشاكل الزمرة:

• العثور على الحد الأقصى من الزمرة (زمرة مع أكبر عدد من القمم) ،
• إيجاد زمرة ذات وزن أقصى في رسم بياني مرجح ،
• سرد جميع الزمعات القصوى (الزمر التي لا يمكن توسيعها)
• حل مشكلة قرار اختبار ما إذا كان الرسم البياني يحتوي على زمرة أكبر من حجم معين.

هذه المشكلات كلها صعبة: مشكلة قرار الزمرة هي مكتملة NP (واحدة من مشكلات NP 21 NP في KARP) ، ومشكلة العثور على الحد الأقصى من الزمرة هي كل من المعلمة الثابتة وضلاعًا تقريبيًا ، وإدراج جميع الزمر القصوى قد تتطلب الوقت الأسي لأن هناك رسومات بيانية مع العديد من الزمعات القصوى بشكل كبير. ومع ذلك ، هناك خوارزميات لهذه المشكلات التي تعمل في وقت أسي أو تتعامل مع بعض الرسوم البيانية للمدخلات المتخصصة في وقت متعدد الحدود.

أنظر أيضا

• خوارزمية برون كيربوش

Answer 2

حسنًا ، مشكلة إيجاد خريطة فرعية K-Vertex في رسم بياني من الحجم n هي ذات تعقيد

o (n^kk^2)

لأن هناك n^k خرفصات فرعية للتحقق منها وكل منها لديه k^2 حواف.

ما تطلبه ، فإن العثور على جميع الخراطيم الفرعية في الرسم البياني هو مشكلة مكتملة NP ويتم شرحها في خوارزمية Bron-kerbosch المذكورة أعلاه.