صفحه‌ها: ۱ ۲
در یک گراف، در صورتیکه دومین درخت پوشای کمینه یکتا باشد آنگاه درخت پوشای کمینه یکتا خواهد بود (هیچ فرضی در مورد یکسان بودن یا نبودن یالها نداریم )
این جمله درسته ؟
من این مثال را براش زدم که ردش کنم . آیا مثالی که زدم مشکل داره؟
تو مثال درخت پوشای کمینه یکتا نیست ولی دومین درخت پوشای کمینه یکتاست .
(۰۸ بهمن ۱۳۹۲ ۰۷:۲۲ ب.ظ)آنجلا نوشته شده توسط: نه مثالتون مشکلی نداره..یکتا بودن درخت پوشای کمینه تا زمانی که یال با اندازه های مساوی وجود داره(البته اگه اون یال ها جز درخت پوشای کمینه باشن) نقض میشه و به چیز دیگه ای هم تا زمانی که این یال ها وجود دارن بستگی نداره حتی با یکتابودن دومین درخت پوشای کمینه هم نمیشه کاریش کرد...تو آزمون مدرسان ، یه همچین موردی را صحیح دونسته (هیچ فرضی در مورد تکراری بودن یالها در نظر نگرفته) ولی من هنوز زیر بار نرفتم
من استننباطم از این جمله اینه که اگه دومین درخت پوشای کمینه رو هم بدست آوردی و با اولی یکسان بود، درخت پوشای کمینه یکتاست!
حالا تو مثالی که شما زدی، اون درختی که شما روش نوشتی پوشای ۲ اصلا کمینه نیست!
اون دو تای دیگه کمینه هستند، پس درخت دوم پوشای کمینه یکی از اونهاست که چون دو تا یال با وزن یکسان داریم(یال با وزن ۳)، درخت پوشای کمینمون یکسان نیست.
وقتی درخت پوشامون یکتاست که وزن های یال هایی که جز درخت پوشامون هستند، یکتا باشن،ولی عکسش درست نیست .
موفق باشید
(۰۸ بهمن ۱۳۹۲ ۰۸:۰۹ ب.ظ)minami نوشته شده توسط: من استننباطم از این جمله اینه که اگه دومین درخت پوشای کمینه رو هم بدست آوردی و با اولی یکسان بود، درخت پوشای کمینه یکتاست!این که کلا جمله غلطی هست.
طبق حرف شما، مربعی با ۴ ضلع با وزن ۳ ، ۴ تا درخت پوشای کمینه داره (پوشای اول و دوم و سوم و چهارم) که همشون یکسان هستند ولی درخت پوشای کمینه ، یکتا نیست.
(۰۸ بهمن ۱۳۹۲ ۰۸:۰۹ ب.ظ)minami نوشته شده توسط: حالا تو مثالی که شما زدی، اون درختی که شما روش نوشتی پوشای ۲ اصلا کمینه نیست!اگر اشتباه نکرده باشم، درختی که روش نوشتم پوشای ۲ ، دومین درخت پوشا حساب میشه. کمینه اول وزن کلی ۶ داره ، کمینه دوم وزن ۷ و کمینه سوم وزن ۸ داره. فکر کنم کمینه ها بر همین اساس دسته بندی میشن که وزن کلی درخت پوشایی که بدست میاد ترتیب وزنشون میشه ، ترتیب درخت پوشای مین
(۰۸ بهمن ۱۳۹۲ ۰۸:۰۹ ب.ظ)minami نوشته شده توسط: وقتی درخت پوشامون یکتاست که وزن های یال هایی که جز درخت پوشامون هستند، یکتا باشن،ولی عکسش درست نیست .این جمله که از روز برام روشن تره. ولی متاسفانه سوال چیز دیگه ای است
اینی که شما میگید رو اولین بار که میشنوم! خوبه یه چی یاد گرفتم
الان گوگل کردم، حق با شماست، من ذهنم یه جا دیگه بود فقط یه چیزی، واسه مثال نقضی که برا حرفم آوردید، مگه یکسان بودن رو از برچسب رئوس تعیین نمیکنیم؟ یا هر دو درختی که ایزومورف باشه رو یکسان در نطر میگیریم ؟
(ببخشید واسه تأکید رو حرفم نمیپرسم، حس میکنم اشتباه فهمیدم مبحث رو، میخوام درست شه)
(۰۸ بهمن ۱۳۹۲ ۰۹:۱۳ ب.ظ)minami نوشته شده توسط: اینی که شما میگید رو اولین بار که میشنوم! خوبه یه چی یاد گرفتمتو گوگل سرچ کردید چی شد ؟ این قضیه که گفتم درست بود یا نه؟ به ما هم لینکشو بدید
فقط یه چیزی، واسه مثال نقضی که برا حرفم آوردید، مگه واسه یکسان بودن رو از برچسب رئوس تعیین نمیکنیم؟ یا هر دو درختی که ایزومورف باشه رو یکسان در نطر میگیریم ؟
(ببخشید واسه تأکید رو حرفم نمیپرسم، حس میکنم اشتباه فهمیدم مبحث رو، میخوام درست شه)
منظور من از یکسان بودن ، یعنی یکسان بودن وزن درختهای پوشا بود. (حواسم نبود چی نوشتم) یعنی همون یکتا نبودن که بر اساس وزن یالها میسنجیم. رئوس که همشون باید تشریف داشته باشن
البته خیلی هم به حرفهای من اعتماد نکنید چون منم ممکنه اشتباه کنم. واسه همین دارم این سوالاتو میپرسم
یک سوال!
دومین درخت کمینه رو چه جوری بدست میارید؟
الگوریتمی منظورمه
(۰۸ بهمن ۱۳۹۲ ۰۹:۳۰ ب.ظ)e.sharmi نوشته شده توسط: یک سوال!ترتیب درختها ظاهرا بر اساس ترتیب مجموع وزن یالها سنجیده میشه
دومین درخت کمینه رو چه جوری بدست میارید؟
الگوریتمی منظورمه
دومین درخت کمینه میشه درخت پوشای کمینه ای که کمترین مجموع وزن یالها را در بین همه درختهای پوشای کمینه داشته باشه، ولی نه کمتر از درخت پوشای کمینه اصلی (کمینه اول)
طبق این شکلی که گذاشتم (مربوط به دانشگاه ماساچوست) گفته شده که پوشای کمینه دوم و اول فقط در یک یال متفاوت هستند
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
الگوریتمش تو همون مثال اینجوری گفته
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۸ بهمن ۱۳۹۲ ۰۹:۴۱ ب.ظ)masoud67 نوشته شده توسط: ترتیب درختها ظاهرا بر اساس ترتیب مجموع وزن یالها سنجیده میشهممنون. جالب بود.
دومین درخت کمینه میشه درخت پوشای کمینه ای که کمترین مجموع وزن یالها را در بین همه درختهای پوشای کمینه داشته باشه، ولی نه کمتر از درخت پوشای کمینه اصلی (کمینه اول)
طبق این شکلی که گذاشتم (مربوط به دانشگاه ماساچوست) گفته شده که پوشای کمینه دوم و اول فقط در یک یال متفاوت هستند
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
الگوریتمش تو همون مثال اینجوری گفته
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
از لحاظ اینکه شما و یکی از دوستان دیگه تست هاتون تموم شده روی به تست های اونور آبی آوردین
یه کم وقت به منم قرض بدید
(۰۸ بهمن ۱۳۹۲ ۱۱:۱۶ ب.ظ)e.sharmi نوشته شده توسط: ممنون. جالب بود.من هر گونه ازدیاد وقتی را تکذیب میکنم
از لحاظ اینکه شما و یکی از دوستان دیگه تست هاتون تموم شده روی به تست های اونور آبی آوردین
یه کم وقت به منم قرض بدید
این تست توی آزمون مدرسان بود و برای اینکه ببینم دقیقا جریان چی هست یه کمی تو منابع اونطرف آب چرخ زدم و گرنه ما هم طالب وقت هستیم.
مرسی از بابت اگوریتمی که گذاشتین...اما چرا این الگوریتم رو روی مثال شما بریم دوباره همون درخت پوشای کمینه میشه؟!!!!!!!!!
من الان دارم به گفته ی خودم شک می کنم ..وقتی دومین درخت پوشای کمینه یکتا باشه حتما توش یال با اندازه تکراری نیست..پس درخت پوشای کمینه هم یکتاست..مدرسان درست گفته بیچاره..
(۰۸ بهمن ۱۳۹۲ ۱۱:۳۴ ب.ظ)آنجلا نوشته شده توسط: مرسی از بابت اگوریتمی که گذاشتین...اما چرا این الگوریتم رو روی مثال شما بریم دوباره همون درخت پوشای کمینه میشه؟!!!!!!!!!من هنوز اون الگوریتم را نگاه نکردم ببینم چی هست. چون اون دوستمون گفتند الگوریتمش چی هست و پایین این مثالی که گذاشتم بود، اینجا قرار دادم.
من الان دارم به گفته ی خودم شک می کنم ..وقتی دومین درخت پوشای کمینه یکتا باشه حتما توش یال با اندازه تکراری نیست..پس درخت پوشای کمینه هم یکتاست..مدرسان درست گفته بیچاره..
ولی حتما انجام میدم و نتیجه را اعلام میکنم. از شما هم ممنون که کمک کردید
دوستانی که اینجا اومدید ، بالاخره جوابم را گفتم
طبق این الگوریتم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
که درخت پوشای کمینه دوم را حساب میکنه و طبق مثالی که تو اول سوالم زدم (مربع) درخت پوشای کمینه دومی که کشیدم اشتباهه. درخت پوشای کمینه دوم تو این مثالی که زدم یکتا نیست ، یعنی هم پوشای اولش دوتاست هم پوشای دومش دوتاست که هر دو یک مجموع وزن دارند
پس این تعریفی که مدرسان تو آزمونش نوشته بود صحیح بود که :
اگر دومین درخت پوشای کمینه گرافی یکتا باشد ، درخت پوشای کمینه آن یکتاست
تشکر از همه
(۰۸ بهمن ۱۳۹۲ ۰۹:۲۴ ب.ظ)masoud67 نوشته شده توسط:(08 بهمن ۱۳۹۲ ۰۹:۱۳ ب.ظ)minami نوشته شده توسط: اینی که شما میگید رو اولین بار که میشنوم! خوبه یه چی یاد گرفتمتو گوگل سرچ کردید چی شد ؟ این قضیه که گفتم درست بود یا نه؟ به ما هم لینکشو بدید
فقط یه چیزی، واسه مثال نقضی که برا حرفم آوردید، مگه واسه یکسان بودن رو از برچسب رئوس تعیین نمیکنیم؟ یا هر دو درختی که ایزومورف باشه رو یکسان در نطر میگیریم ؟
(ببخشید واسه تأکید رو حرفم نمیپرسم، حس میکنم اشتباه فهمیدم مبحث رو، میخوام درست شه)
منظور من از یکسان بودن ، یعنی یکسان بودن وزن درختهای پوشا بود. (حواسم نبود چی نوشتم) یعنی همون یکتا نبودن که بر اساس وزن یالها میسنجیم. رئوس که همشون باید تشریف داشته باشن
البته خیلی هم به حرفهای من اعتماد نکنید چون منم ممکنه اشتباه کنم. واسه همین دارم این سوالاتو میپرسم
من فقط تعریف دومین درخت پوشای کمینه که اشتباه فهمیده بودم رو اون موقع گوگل کردم، بعد رفتم..
مرسی از توضیحات و الگوریتم، جالبه
چطور؟! این درختی که کشیدید دومین درختش یکتا نیست؟! حالت دیگه اش کدومه؟!
Sent from my SM-T210R using Tapatalk
(۰۹ بهمن ۱۳۹۲ ۰۸:۳۱ ب.ظ)hoomanab نوشته شده توسط: چطور؟! این درختی که کشیدید دومین درختش یکتا نیست؟! حالت دیگه اش کدومه؟!این درختی که کشیده بودم و نوشته بودم پوشای ۲ اشتباهه و این میشه پوشای ۳
این الگوریتم مطمینید کمینه دوم رو حساب میکنه؟!
اون دوتا که نوشتم پوشای یک ، یکیش میشه پوشای کمینه (پوشای یکم) و اون یکیش میشه پوشای دوم و یکتا هم نیستند یعنی اگه یکیشون یکم باشه، اون یکی میشه دوم
این الگوریتمی که گذاشتم واسه دانشگاه ماساچوست بود که یه مثال زده بود و حلش کرده بود. که به نظرم درست هم میاد چون درخت کمینه دوم یعنی کل وزن این درخت باید وزنش از همه درختهای پوشا کمتر باشه ، به جز درخت پوشای اول