سوف الدنيا شجرة الامتداد ليس فقط تلك الحواف المحددة من قبل دائرة الملكية ؟ [مكررة]

Question

هذا السؤال سبق الجواب هنا:

ما حواف ليست في أي MST? (1 إجابة)

مغلقة منذ 4 أشهر.

لقد بدأت للتو في فهم "الحد الأدنى تغطي الأشجار" (الفرق الجراحية المتنقلة) و قد تأتي عبر دورة الملكية.وأنا أشير إلى الكتاب - تصميم خوارزمية جون Kleinberg و إيفا Tardos.بيان العقار كما هو مكتوب في الكتاب هو:

نفترض أن كل حافة التكاليف متميزة.اسمحوا ج أي دورة في ز ، والسماح حافة e = (v,w) تكون أغلى حافة ينتمون إلى C.ثم e لا تنتمي إلى أي الحد الأدنى من شجرة الامتداد.

الآن بلدي شك هو:هي حواف الرسم البياني (الرسم البياني صليات مع حواف وجود متميزة إيجابية الأوزان) التي لا ترضي دورة المنشأة الوحيدة التي ليست موجودة في MST أو لن يكون هناك أي حواف التي لا تنتمي إلى MST و لا تغطيها هذه الخاصية ؟

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

Answer 1

دعونا نقول أن الحافة $e$ في $G$ هو سيئة إذا كان هناك دورة في $G$ التي $e$ وقد الوزن الأقصى.

تعريف ${\كال ب}=\{e~|~e$ هو سيئة في $G\}$ إلى أن جمع كل سوء الحواف.

السؤال هو ما إذا كان الرسم البياني $(G - {\كال ب})$ MST من $G$ (على افتراض أن جميع الحافة الأوزان متميزة).الجواب هو نعم!

من أجل إثبات هذا يكفي لإظهار أن $(G - {\كال ب})$ هو احلقي.

نفترض على العكس من ذلك أن $(G - {\كال ب})$ يحتوي على دورة, يقول $C$.نلاحظ أن $C$ دورة في $G$ أيضا.السماح $e^*$ تكون حافة الوزن الأقصى في دورة $C$.الآن $e^*$ هو سيئة الحافة ، لذلك ينبغي أن لا يكون هو الرسم البياني $(G - {\كال ب})$ على المركز الأول.وهذا يدل على أن $(G - {\كال ب})$ هو احلقي.

Answer 2

آسف إذا لم أفهم سؤالك، ولكن ما أعتقد أنك تهدف إلى طرحه هو، ما إذا كان من الممكن أن تكون حافة لا تكون في MST إذا كانت هذه الحافة ليست في دورة.

ها هي إجابتي.

دعونا نفترض أن لدينا حافة (U، V) في رسم بياني، وهذا ليس جزءا من دورة.هذا يعني أنه لا يوجد مسار منك إلى الخامس الذي ليس الحافة (U، V). إذا لم تكن الحافة (U، V) في MST، فسيحدر ذلك أنه لا يوجد مسار منك إلى الخامس في هذا المنسق، مما يعني أن MST سيتم قطع اتصالها، وبالتالي ليس من طراز MST على الإطلاق. وبالتالي إذا كانت الحافة ليست جزءا من الدورة، فيجب أن تكون في MST من الرسم البياني.