تسيطر مجموعة من رسم بياني البطولة

Question

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

Answer 1

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

Answer 2

لا، لأن ستشمل MST جميع القمم من الرسم البياني، ومجموعة المسيطرة قد لا.

وانظر على سبيل المثال في الرسم البياني هنا: http://en.wikipedia.org/ ويكي / Tournament_ (graph_theory) القمم 2 و 4 إنشاء مجموعة المهيمنة، وليس الشجرة الممتدة.