هل هذه مشكلة معروفة في نظرية الرسم البياني؟

Question

مشكلتي الأساسية تتضمن رسم بياني حيث يرتبط كل عقدة $ i $ مع وزن $ c_i $ ، والمشكلة هي العثور على حد أدنى (أو أقصى حد) مجموعة مستقلة مرجحة مع بطاقة ادورينية ثابتة $ P $ . هذا أعتقد أن مشكلة معروفة في نظرية الرسم البياني والتي تتم دراستها بشكل جيد لأنواع مختلفة من الرسوم البيانية.

الآن، لنفترض أنني أتعامل مع شكل معمم من المشكلة كما يلي. يمكن أن يستغرق وزن كل عقدة $ P $ قيم مختلفة، أي كل عقدة مرتبطة $ P $ الأوزان المختلفة. الهدف مرة أخرى للعثور على الحد الأدنى (أو الحد الأقصى) المحدد المستقل المرجح مع بطاقة ادورينية ثابتة $ P $ يمكن اختيار كل نوع من الوزن مرة واحدة فقط. بالتحديد، إذا تم تحديد نوع الوزن $ J $ $ i i $ ، أي نحن نختار الوزن $ c_ {ij} $ ، ثم العقد الأخرى المختارة لا يمكن أن تأخذ وزن النوع $ J $ .

سؤالي هو أن هذه مشكلة نظرية رسم بيانية؟ هل هو تعميم معروف في نظرية الرسم البياني؟

أي مساعدة و / أو مرجع موضع تقدير.

Answer 1

إذا $ g= (v، e) $ ، مع $ v={v_1، v_2، .. .، v_n \} $ والأوزان $ \ {c_ {i، j}، i= 1،2، ...، n، j= 1،2، ...، p \} $ هو الرسم البياني المحدد، ثم يمكننا إنشاء منتج قوي (وجدت أخيرا اسم العملية) $ g \ boxtimes k_p $ من $ G $ و $ k_p $ ، حيث $ k_p $ هو الرسم البياني الكامل مع $ P $ الرأس. هذا هو الرسم البياني مع القمم $ \ {v_ {i، j}، i= 1،2، ...، n، j= 1،2، ...، p \ } $ وحواف $ \ {v_ {{a، b}، v_ {c، d} \} $ أينما إما:

1. $ a= c $ ،
2. $ B= D $ أو
3. $ \ {v_a، v_c \} \ in e $ . (الشرط الفعلي للمنتج القوي يقلل من ذلك لأنه في $ k_p $ جميع القمم مجاورة).

نعطي قمة الرأس $ v_ {i،} $ الوزن $ c_ {i، j} $ < / span>، مقابل $ i= 1،2، ...، n $ و $ J= 1،2، ...، P $ .

المشكلة على $ g $ تعادل المشكلة الحد الأدنى (الحد الأدنى) مجموعة مستقلة مرجحة في $ g \ boxtimes k_p $ . إذا تم اختيار Vertex $ v_ $ من الرسم البياني الجديد يتم اختيار هذا يتوافق مع اختيار Vertex $ v_i $ < / SPAN> من الرسم البياني الأصلي واستخدام $ J $ -wink $ c_ {i، j} $ المقابلة لها.

مجموعة من حواف $ g \ boxtimes k_p $ هي بالضبط تلك التي تمنع الخيارات المقابلة في $ G $ لاستخدام القمم المجاورة أو إعادة استخدام الأوزان مع نفس الفهرس:

• حالة $ 1 $ تعرف الحواف في المنتج القوي الذي يمنع ما يعادل استخدام أوزان من نفس القمة الأصلية.
• حالة $ 2 $ يمنع استخدام الأوزان مع نفس الفهرس من القمم المختلفة من الرسم البياني الأصلي.
• حالة 3 دولارات $ يمنع أن اثنين من القمم التي كانت جيرانها في الرسم البياني الأصلي يتم تحديدها.

مثال:

إذا كان $ G $ هو الرسم البياني

p>

و $ p= 2 $ ، ثم $ g \ boxtimes k_2 $ سيكون الرسم البياني < / ص>

p> href="https://i.stack.imgur.com/gyacr.png" rel="nofollow noreferrer">

الصور التي تم إنشاؤها باستخدام هذه الأداة .