صفحهها: ۱ ۲
بله الگوریتم درسته دقت نکردم. اما اگه یال های هم وزن دیگه ای مثل یال های درخت باشن، اینطور میشه. اگه تعبیر از درخت پوشای کمینه دوم اینطور باشه، n-امین درخت هم اگه یکتا باشه mst یکتاست. مطمینید منظور از یکتا بودن، یکتا بودن مجموع وزنا نیست؟! منظورم اینه وقتی وزن دو تا درخت کمینه با شکل متفاوت یکسان باشه، دیگه درخت پوشای کمینه یکتا نیست!
Sent from my SM-T210R using Tapatalk
(۰۹ بهمن ۱۳۹۲ ۰۸:۴۲ ب.ظ)hoomanab نوشته شده توسط: بله الگوریتم درسته دقت نکردم. اما اگه یال های هم وزن دیگه ای مثل یال های درخت باشن، اینطور میشه. اگه تعبیر از درخت پوشای کمینه دوم اینطور باشه، n-امین درخت هم اگه یکتا باشه mst یکتاست. مطمینید منظور از یکتا بودن، یکتا بودن مجموع وزنا نیست؟! منظورم اینه وقتی وزن دو تا درخت کمینه با شکل متفاوت یکسان باشه، دیگه درخت پوشای کمینه یکتا نیست!شما یه مربع با اضلاع ۳ را در نظر بگیر
پوشای اول و دوم و سوم و چهارمش همه وزنشون یکی میشه. یعنی این گراف در کل چهارتا درخت پوشا داره که همشون اوزان مشابه دارند. و درختهای اول و دوم ... یکتا نیستند چون هر کدوم میتونن به عنوان یکی از درختهای اول و دوم ... قرار بگیرن. !۴ حالت
نه دیگه .... مثلا تو اون مثالی که زدم (مربع با اضلاع ۳و۳و۱و۲) ، درخت سوم و چهارم کمینه یکتا هستند ولی کمینه یکتا نیست.
یکتا بودن منظور مجموع وزن درخته دیگه. چیزی که شما گفتید درسته، وقتی وزن دو تا درخت کمینه با شکل متفاوت یکسان باشه ، درخت کمینه یکتا نیست. بخاطر همین تو کراسکال میگیم اگه یال تکراری باشه ، ممکنه درخت پوشای کمینه یکتا نشه.
خوب پس توی این مثالی که شما زدید، با این استدلال، درخت پوشای کمینه دوم هم یکسان نیست. چون هر کدومشون میتونن به عنوان اولین در نظر گرفته شن!
Sent from my SM-T210R using Tapatalk
(۰۹ بهمن ۱۳۹۲ ۰۸:۵۴ ب.ظ)hoomanab نوشته شده توسط: خوب پس توی این مثالی که شما زدید، با این استدلال، درخت پوشای کمینه دوم هم یکسان نیست. چون هر کدومشون میتونن به عنوان اولین در نظر گرفته شن!درسته. منم گفتم این مثالم اشتباهه. من اول کار یه مثال از روی جهالتم زدم، ولی بعد که یه خرده جستجو کردم ، فهمیدم این مثال از بیخ اشتباه بوده .
Sent from my SM-T210R using Tapatalk
البته این مثال برای اثبات سوال مدرسان مناسبه ولی برای ردش نه .
مثالی که این امر درست باشه ندارید؟!
Sent from my SM-T210R using Tapatalk