من استننباطم از این جمله اینه که اگه دومین درخت پوشای کمینه رو هم بدست آوردی و با اولی یکسان بود، درخت پوشای کمینه یکتاست!

حالا تو مثالی که شما زدی، اون درختی که شما روش نوشتی پوشای ۲ اصلا کمینه نیست!

اون دو تای دیگه کمینه هستند، پس درخت دوم پوشای کمینه یکی از اونهاست که چون دو تا یال با وزن یکسان داریم(یال با وزن ۳)، درخت پوشای کمینمون یکسان نیست.

وقتی درخت پوشامون یکتاست که وزن های یال هایی که جز درخت پوشامون هستند، یکتا باشن،ولی عکسش درست نیست .

موفق باشید

(۰۸ بهمن ۱۳۹۲ ۰۸:۰۹ ب.ظ)minami نوشته شده توسط:  من استننباطم از این جمله اینه که اگه دومین درخت پوشای کمینه رو هم بدست آوردی و با اولی یکسان بود، درخت پوشای کمینه یکتاست!

این که کلا جمله غلطی هست.
طبق حرف شما، مربعی با ۴ ضلع با وزن ۳ ، ۴ تا درخت پوشای کمینه داره (پوشای اول و دوم و سوم و چهارم) که همشون یکسان هستند ولی درخت پوشای کمینه ، یکتا نیست.

(۰۸ بهمن ۱۳۹۲ ۰۸:۰۹ ب.ظ)minami نوشته شده توسط:  حالا تو مثالی که شما زدی، اون درختی که شما روش نوشتی پوشای ۲ اصلا کمینه نیست!

اگر اشتباه نکرده باشم، درختی که روش نوشتم پوشای ۲ ، دومین درخت پوشا حساب میشه. کمینه اول وزن کلی ۶ داره ، کمینه دوم وزن ۷ و کمینه سوم وزن ۸ داره. فکر کنم کمینه ها بر همین اساس دسته بندی میشن که وزن کلی درخت پوشایی که بدست میاد ترتیب وزنشون میشه ، ترتیب درخت پوشای مین

(۰۸ بهمن ۱۳۹۲ ۰۸:۰۹ ب.ظ)minami نوشته شده توسط:  وقتی درخت پوشامون یکتاست که وزن های یال هایی که جز درخت پوشامون هستند، یکتا باشن،ولی عکسش درست نیست .

این جمله که از روز برام روشن تره. ولی متاسفانه سوال چیز دیگه ای است

اینی که شما میگید رو اولین بار که میشنوم! خوبه یه چی یاد گرفتم الان گوگل کردم، حق با شماست، من ذهنم یه جا دیگه بود

فقط یه چیزی، واسه مثال نقضی که برا حرفم آوردید، مگه یکسان بودن رو از برچسب رئوس تعیین نمیکنیم؟ یا هر دو درختی که ایزومورف باشه رو یکسان در نطر میگیریم ؟

(ببخشید واسه تأکید رو حرفم نمیپرسم، حس میکنم اشتباه فهمیدم مبحث رو، میخوام درست شه)

(۰۸ بهمن ۱۳۹۲ ۰۹:۱۳ ب.ظ)minami نوشته شده توسط:  اینی که شما میگید رو اولین بار که میشنوم! خوبه یه چی یاد گرفتم الان گوگل کردم، حق با شماست، من ذهنم یه جا دیگه بود

فقط یه چیزی، واسه مثال نقضی که برا حرفم آوردید، مگه واسه یکسان بودن رو از برچسب رئوس تعیین نمیکنیم؟ یا هر دو درختی که ایزومورف باشه رو یکسان در نطر میگیریم ؟

(ببخشید واسه تأکید رو حرفم نمیپرسم، حس میکنم اشتباه فهمیدم مبحث رو، میخوام درست شه)

تو گوگل سرچ کردید چی شد ؟ این قضیه که گفتم درست بود یا نه؟ به ما هم لینکشو بدید

منظور من از یکسان بودن ، یعنی یکسان بودن وزن درختهای پوشا بود. (حواسم نبود چی نوشتم) یعنی همون یکتا نبودن که بر اساس وزن یالها میسنجیم. رئوس که همشون باید تشریف داشته باشن

البته خیلی هم به حرفهای من اعتماد نکنید چون منم ممکنه اشتباه کنم. واسه همین دارم این سوالاتو میپرسم

(۰۸ بهمن ۱۳۹۲ ۰۹:۲۴ ب.ظ)masoud67 نوشته شده توسط:  

(08 بهمن ۱۳۹۲ ۰۹:۱۳ ب.ظ)minami نوشته شده توسط:  اینی که شما میگید رو اولین بار که میشنوم! خوبه یه چی یاد گرفتم الان گوگل کردم، حق با شماست، من ذهنم یه جا دیگه بود

فقط یه چیزی، واسه مثال نقضی که برا حرفم آوردید، مگه واسه یکسان بودن رو از برچسب رئوس تعیین نمیکنیم؟ یا هر دو درختی که ایزومورف باشه رو یکسان در نطر میگیریم ؟

(ببخشید واسه تأکید رو حرفم نمیپرسم، حس میکنم اشتباه فهمیدم مبحث رو، میخوام درست شه)

تو گوگل سرچ کردید چی شد ؟ این قضیه که گفتم درست بود یا نه؟ به ما هم لینکشو بدید

منظور من از یکسان بودن ، یعنی یکسان بودن وزن درختهای پوشا بود. (حواسم نبود چی نوشتم) یعنی همون یکتا نبودن که بر اساس وزن یالها میسنجیم. رئوس که همشون باید تشریف داشته باشن

البته خیلی هم به حرفهای من اعتماد نکنید چون منم ممکنه اشتباه کنم. واسه همین دارم این سوالاتو میپرسم

من فقط تعریف دومین درخت پوشای کمینه که اشتباه فهمیده بودم رو اون موقع گوگل کردم، بعد رفتم..

مرسی از توضیحات و الگوریتم، جالبه

یک سوال!
دومین درخت کمینه رو چه جوری بدست میارید؟
الگوریتمی منظورمه

(۰۸ بهمن ۱۳۹۲ ۰۹:۳۰ ب.ظ)e.sharmi نوشته شده توسط:  یک سوال!
دومین درخت کمینه رو چه جوری بدست میارید؟
الگوریتمی منظورمه

ترتیب درختها ظاهرا بر اساس ترتیب مجموع وزن یالها سنجیده میشه
دومین درخت کمینه میشه درخت پوشای کمینه ای که کمترین مجموع وزن یالها را در بین همه درختهای پوشای کمینه داشته باشه، ولی نه کمتر از درخت پوشای کمینه اصلی (کمینه اول)
طبق این شکلی که گذاشتم (مربوط به دانشگاه ماساچوست) گفته شده که پوشای کمینه دوم و اول فقط در یک یال متفاوت هستند


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


الگوریتمش تو همون مثال اینجوری گفته

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(۰۸ بهمن ۱۳۹۲ ۰۹:۴۱ ب.ظ)masoud67 نوشته شده توسط:  ترتیب درختها ظاهرا بر اساس ترتیب مجموع وزن یالها سنجیده میشه
دومین درخت کمینه میشه درخت پوشای کمینه ای که کمترین مجموع وزن یالها را در بین همه درختهای پوشای کمینه داشته باشه، ولی نه کمتر از درخت پوشای کمینه اصلی (کمینه اول)
طبق این شکلی که گذاشتم (مربوط به دانشگاه ماساچوست) گفته شده که پوشای کمینه دوم و اول فقط در یک یال متفاوت هستند


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


الگوریتمش تو همون مثال اینجوری گفته

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

ممنون. جالب بود.
از لحاظ اینکه شما و یکی از دوستان دیگه تست هاتون تموم شده روی به تست های اونور آبی آوردین
یه کم وقت به منم قرض بدید

(۰۸ بهمن ۱۳۹۲ ۱۱:۱۶ ب.ظ)e.sharmi نوشته شده توسط:  ممنون. جالب بود.
از لحاظ اینکه شما و یکی از دوستان دیگه تست هاتون تموم شده روی به تست های اونور آبی آوردین
یه کم وقت به منم قرض بدید

من هر گونه ازدیاد وقتی را تکذیب میکنم
این تست توی آزمون مدرسان بود و برای اینکه ببینم دقیقا جریان چی هست یه کمی تو منابع اونطرف آب چرخ زدم و گرنه ما هم طالب وقت هستیم.

مرسی از بابت اگوریتمی که گذاشتین...اما چرا این الگوریتم رو روی مثال شما بریم دوباره همون درخت پوشای کمینه میشه؟!!!!!!!!!
من الان دارم به گفته ی خودم شک می کنم ..وقتی دومین درخت پوشای کمینه یکتا باشه حتما توش یال با اندازه تکراری نیست..پس درخت پوشای کمینه هم یکتاست..مدرسان درست گفته بیچاره..

(۰۸ بهمن ۱۳۹۲ ۱۱:۳۴ ب.ظ)آنجلا نوشته شده توسط:  مرسی از بابت اگوریتمی که گذاشتین...اما چرا این الگوریتم رو روی مثال شما بریم دوباره همون درخت پوشای کمینه میشه؟!!!!!!!!!
من الان دارم به گفته ی خودم شک می کنم ..وقتی دومین درخت پوشای کمینه یکتا باشه حتما توش یال با اندازه تکراری نیست..پس درخت پوشای کمینه هم یکتاست..مدرسان درست گفته بیچاره..

من هنوز اون الگوریتم را نگاه نکردم ببینم چی هست. چون اون دوستمون گفتند الگوریتمش چی هست و پایین این مثالی که گذاشتم بود، اینجا قرار دادم.
ولی حتما انجام میدم و نتیجه را اعلام میکنم. از شما هم ممنون که کمک کردید

---

دوستانی که اینجا اومدید ، بالاخره جوابم را گفتم
طبق این الگوریتم

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

که درخت پوشای کمینه دوم را حساب میکنه و طبق مثالی که تو اول سوالم زدم (مربع) درخت پوشای کمینه دومی که کشیدم اشتباهه. درخت پوشای کمینه دوم تو این مثالی که زدم یکتا نیست ، یعنی هم پوشای اولش دوتاست هم پوشای دومش دوتاست که هر دو یک مجموع وزن دارند
پس این تعریفی که مدرسان تو آزمونش نوشته بود صحیح بود که :
اگر دومین درخت پوشای کمینه گرافی یکتا باشد ، درخت پوشای کمینه آن یکتاست

تشکر از همه

چطور؟! این درختی که کشیدید دومین درختش یکتا نیست؟! حالت دیگه اش کدومه؟!

Sent from my SM-T210R using Tapatalk

(۰۹ بهمن ۱۳۹۲ ۰۸:۳۱ ب.ظ)hoomanab نوشته شده توسط:  چطور؟! این درختی که کشیدید دومین درختش یکتا نیست؟! حالت دیگه اش کدومه؟!

---

این الگوریتم مطمینید کمینه دوم رو حساب میکنه؟!

این درختی که کشیده بودم و نوشته بودم پوشای ۲ اشتباهه و این میشه پوشای ۳
اون دوتا که نوشتم پوشای یک ، یکیش میشه پوشای کمینه (پوشای یکم) و اون یکیش میشه پوشای دوم و یکتا هم نیستند یعنی اگه یکیشون یکم باشه، اون یکی میشه دوم

این الگوریتمی که گذاشتم واسه دانشگاه ماساچوست بود که یه مثال زده بود و حلش کرده بود. که به نظرم درست هم میاد چون درخت کمینه دوم یعنی کل وزن این درخت باید وزنش از همه درختهای پوشا کمتر باشه ، به جز درخت پوشای اول

بله الگوریتم درسته دقت نکردم. اما اگه یال های هم وزن دیگه ای مثل یال های درخت باشن، اینطور میشه. اگه تعبیر از درخت پوشای کمینه دوم اینطور باشه، 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