زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۹:۰۰ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

ارسال:
  

masoud67 پرسیده:

آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

در یک گراف، در صورتیکه دومین درخت پوشای کمینه یکتا باشد آنگاه درخت پوشای کمینه یکتا خواهد بود (هیچ فرضی در مورد یکسان بودن یا نبودن یالها نداریم )
این جمله درسته ؟
من این مثال را براش زدم که ردش کنم . آیا مثالی که زدم مشکل داره؟
تو مثال درخت پوشای کمینه یکتا نیست ولی دومین درخت پوشای کمینه یکتاست .


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

minami پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

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

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

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

موفق باشید Smile
نقل قول این ارسال در یک پاسخ

ارسال:
  

masoud67 پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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


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


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

ارسال:
  

minami پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

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

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

ارسال:
  

masoud67 پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

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

(ببخشید واسه تأکید رو حرفم نمیپرسم، حس میکنم اشتباه فهمیدم مبحث رو، میخوام درست شه)
تو گوگل سرچ کردید چی شد ؟ این قضیه که گفتم درست بود یا نه؟ به ما هم لینکشو بدید

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

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

ارسال:
  

minami پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

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

(ببخشید واسه تأکید رو حرفم نمیپرسم، حس میکنم اشتباه فهمیدم مبحث رو، میخوام درست شه)
تو گوگل سرچ کردید چی شد ؟ این قضیه که گفتم درست بود یا نه؟ به ما هم لینکشو بدید

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

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

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

مرسی از توضیحات و الگوریتم، جالبه
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

e.shrm پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

ارسال:
  

masoud67 پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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


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


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

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


فایل‌(های) پیوست شده


یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

e.shrm پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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


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


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

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ممنون. جالب بود.
از لحاظ اینکه شما و یکی از دوستان دیگه تست هاتون تموم شده روی به تست های اونور آبی آوردین Cool
یه کم وقت به منم قرض بدید Smile
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال: #۱۰
  

masoud67 پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

۰
ارسال: #۱۱
  

آنجلا پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

ارسال: #۱۲
  

masoud67 پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

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

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

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

تشکر از همه
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۳
  

hoomanab پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ

ارسال: #۱۴
  

masoud67 پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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


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

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

۰
ارسال: #۱۵
  

hoomanab پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

بله الگوریتم درسته دقت نکردم. اما اگه یال های هم وزن دیگه ای مثل یال های درخت باشن، اینطور میشه. اگه تعبیر از درخت پوشای کمینه دوم اینطور باشه، n-امین درخت هم اگه یکتا باشه mst یکتاست. مطمینید منظور از یکتا بودن، یکتا بودن مجموع وزنا نیست؟! منظورم اینه وقتی وزن دو تا درخت کمینه با شکل متفاوت یکسان باشه، دیگه درخت پوشای کمینه یکتا نیست!

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ

ارسال: #۱۶
  

masoud67 پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

نه دیگه .... مثلا تو اون مثالی که زدم (مربع با اضلاع ۳و۳و۱و۲) ، درخت سوم و چهارم کمینه یکتا هستند ولی کمینه یکتا نیست.
یکتا بودن منظور مجموع وزن درخته دیگه. چیزی که شما گفتید درسته، وقتی وزن دو تا درخت کمینه با شکل متفاوت یکسان باشه ، درخت کمینه یکتا نیست. بخاطر همین تو کراسکال میگیم اگه یال تکراری باشه ، ممکنه درخت پوشای کمینه یکتا نشه.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۷
  

hoomanab پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

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

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ

ارسال: #۱۸
  

masoud67 پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

(۰۹ بهمن ۱۳۹۲ ۰۸:۵۴ ب.ظ)hoomanab نوشته شده توسط:  خوب پس توی این مثالی که شما زدید، با این استدلال، درخت پوشای کمینه دوم هم یکسان نیست. چون هر کدومشون میتونن به عنوان اولین در نظر گرفته شن!

Sent from my SM-T210R using Tapatalk
درسته. منم گفتم این مثالم اشتباهه. من اول کار یه مثال از روی جهالتم زدم، ولی بعد که یه خرده جستجو کردم ، فهمیدم این مثال از بیخ اشتباه بوده .
البته این مثال برای اثبات سوال مدرسان مناسبه ولی برای ردش نه .
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۹
  

hoomanab پاسخ داده:

RE: آیا یکتا بودن دومین درخت پوشای کمینه دلیل بر یکتا بودن درخت پوشای کمینه است؟

مثالی که این امر درست باشه ندارید؟!

Sent from my SM-T210R using Tapatalk
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۳۳ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  سلام آیا اینجا کسی رشتش کامپیوتر هست؟ parisa1140 ۲ ۳,۸۷۳ ۱۹ بهمن ۱۳۹۹ ۱۱:۰۶ ب.ظ
آخرین ارسال: farsamw
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۷ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۰۸۱ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۵۰ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  اثبات بومی بودن sirvan.t ۸ ۵,۱۴۷ ۱۰ اسفند ۱۳۹۸ ۰۹:۴۶ ب.ظ
آخرین ارسال: WILL
  تعداد درخت فراگیر ss311 ۰ ۲,۰۵۷ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311
  آیا تبلیغات در اینستاگرام براتون کارآمد بوده؟ کیمیا شیرازی ۰ ۱,۸۶۵ ۰۴ آذر ۱۳۹۸ ۰۵:۵۱ ب.ظ
آخرین ارسال: کیمیا شیرازی

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close