یک گراف داریم وزن یال های آن بزرگتر از یک می باشد یک واحد اضافه می کنیم به یالها آیا برش کمینه گراف تغییر می کند ؟
برش کمینه گراف چیست ؟
منظورتون از برش کمینه همان درخت پوشای کمینه است؟ اگر منظورتون همان باشه و یک احد به یالی اضافه شده که جز درخت پوشای کمینه نبوده بله همچنان درخت کمینه است ولی اگر به یالی اضافه شده که در درخت پوشا بوده اون موقع احتمال داره که دیگه کمینه نباشه. اگر درخت کمینگیش را از دست داده باشه فکر کنم دومین درخت پوشای کمینه قبلی حالا میشه درخت پوشای کمینه.
(۲۸ آبان ۱۳۹۰ ۰۱:۰۵ ق.ظ)pos نوشته شده توسط: منظورتون از برش کمینه همان درخت پوشای کمینه است؟ اگر منظورتون همان باشه و یک احد به یالی اضافه شده که جز درخت پوشای کمینه نبوده بله همچنان درخت کمینه است ولی اگر به یالی اضافه شده که در درخت پوشا بوده اون موقع احتمال داره که دیگه کمینه نباشه. اگر درخت کمینگیش را از دست داده باشه فکر کنم دومین درخت پوشای کمینه قبلی حالا میشه درخت پوشای کمینه.
این سوال سال ۹۰ رشته هوش مصنوعی بوده و توی تست گفته
برش کمینه هر دو یکسان است .
درخت کمینه هر دو یکسان است .
گفته چند تا از یان جملات درسته ؟
پس فکر کنم برش کمینه با درخت کمینه فرق داره ؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟
یک واحد به کل وزن یالها اضافه می شود یا یک یال جدید با وزن یک؟!
من دچار ابهام شدم.
فصل ۲۳ CLRS توضیح داده
منظور از برش کمینه min-cut هستش! نه درخت پوشای کمینه .
اگر به همه یالها یک واحد اضافه شود دختر پوشای کمینه بدون تغییر خواهد بود.
به هر یال یک واحد اضافه می شود
(۲۸ آبان ۱۳۹۰ ۰۲:۰۶ ق.ظ)باد نوشته شده توسط: اگر به همه یالها یک واحد اضافه شود دختر پوشای کمینه بدون تغییر خواهد بود.
درخت درست می گید ولی من برش کمینه را می خوام
(۲۸ آبان ۱۳۹۰ ۰۲:۰۶ ق.ظ)saba1000 نوشته شده توسط: به هر یال یک واحد اضافه می شود
(۲۸ آبان ۱۳۹۰ ۰۲:۰۶ ق.ظ)باد نوشته شده توسط: اگر به همه یالها یک واحد اضافه شود دختر پوشای کمینه بدون تغییر خواهد بود.
درخت درست می گید ولی من برش کمینه را می خوام
برش کمینه هم تغییر نمی کنه!
وقتی تمام وزن‌ها به یک میزان تغییر می کننه قاعدتا نباید برش کمینه هم تغییر پیدا کنه
من در خصوص برش کمینه و مفهوم برش سبک چون خیلی مسلط نیستم نمی تونم منظورم رو خوب برسونم.
اگه به فصل ۲۳ و ۲۶ CLRS مراجعه کنید می تونید مطلب رو کاملا درک کنید