یک الگوریتم با زمان اجرای O(E)e ارائه دهید که تور اویلری را در صورت وجود می یابد(راهنمایی :دور هایی که یال های مجزا دارند ادغام کنید)
فصل ۲۲ مسئله ی ۳
کلا این فصل مسئله هاش سخت بود
راهنماییش رو نفهمیدم اصلا منظورش چیه
از اون e منظورتون چیه؟!
Sent from my SM-T210R using Tapatalk
(۰۷ دى ۱۳۹۲ ۰۸:۲۵ ق.ظ)hoomanab نوشته شده توسط: از اون e منظورتون چیه؟!
Sent from my SM-T210R using Tapatalk
هیچی فقط نوشتم پرانتزا قاطی نشن
منکه نمیدونم جریان چیه ولی فکر کنم این ریختی بشه حلش کرد
تو لیست مجاورتی به ازای تک تک یالها میری جلو و توی هر راس بررسی میکنی که درجه زوج هست یا نه. اگر همه راسهایی که دیدی زوج بود پس گراف اویلریه. به همین سادگی ولی مطمئن نیستم دقیقا همین شکلی باشه
(۰۷ دى ۱۳۹۲ ۰۱:۱۱ ب.ظ)masoud67 نوشته شده توسط: منکه نمیدونم جریان چیه ولی فکر کنم این ریختی بشه حلش کرد
تو لیست مجاورتی به ازای تک تک یالها میری جلو و توی هر راس بررسی میکنی که درجه زوج هست یا نه. اگر همه راسهایی که دیدی زوج بود پس گراف اویلریه. به همین سادگی ولی مطمئن نیستم دقیقا همین شکلی باشه
این مسئله میخواد که تور اویلری رو پیدا کنیم نه این که ببینیم اویلری هست یا نه! اون چیزی که شما میگید رو میشه توی [tex]O(V)[/tex]. بدستش اورد.
ولی یه ایده واسه مسئله بالا میتونه این باشه که ما همهی دور ها رو توی گراف بدست میاریم و اونایی که یال مشترک دارن رو یال رو حذف میکنیم و این دور ها رو که باهم ادغام کنیم میشه همون دور اویلری که چون هر یال رو یک بار میبینیم میشه از [tex]O(E)[/tex] البته باید ببینیم که نظر طراح محترم چی هست
(۰۷ دى ۱۳۹۲ ۰۲:۱۱ ب.ظ)Riemann نوشته شده توسط:دمت گرم(07 دى ۱۳۹۲ ۰۱:۱۱ ب.ظ)masoud67 نوشته شده توسط: منکه نمیدونم جریان چیه ولی فکر کنم این ریختی بشه حلش کرد
تو لیست مجاورتی به ازای تک تک یالها میری جلو و توی هر راس بررسی میکنی که درجه زوج هست یا نه. اگر همه راسهایی که دیدی زوج بود پس گراف اویلریه. به همین سادگی ولی مطمئن نیستم دقیقا همین شکلی باشه
این مسئله میخواد که تور اویلری رو پیدا کنیم نه این که ببینیم اویلری هست یا نه! اون چیزی که شما میگید رو میشه توی [tex]O(V)[/tex]. بدستش اورد.
ولی یه ایده واسه مسئله بالا میتونه این باشه که ما همهی دور ها رو توی گراف بدست میاریم و اونایی که یال مشترک دارن رو یال رو حذف میکنیم و این دور ها رو که باهم ادغام کنیم میشه همون دور اویلری که چون هر یال رو یک بار میبینیم میشه از [tex]O(E)[/tex] البته باید ببینیم که نظر طراح محترم چی هست
داشتم به منجلاب گمراهی میرفتم. من فکر کردم میگه اویلری هست یا نه.
clrs خوندی انقدر خفن جواب دادی؟
(۰۷ دى ۱۳۹۲ ۰۲:۱۱ ب.ظ)Riemann نوشته شده توسط:(07 دى ۱۳۹۲ ۰۱:۱۱ ب.ظ)masoud67 نوشته شده توسط: منکه نمیدونم جریان چیه ولی فکر کنم این ریختی بشه حلش کرد
تو لیست مجاورتی به ازای تک تک یالها میری جلو و توی هر راس بررسی میکنی که درجه زوج هست یا نه. اگر همه راسهایی که دیدی زوج بود پس گراف اویلریه. به همین سادگی ولی مطمئن نیستم دقیقا همین شکلی باشه
این مسئله میخواد که تور اویلری رو پیدا کنیم نه این که ببینیم اویلری هست یا نه! اون چیزی که شما میگید رو میشه توی [tex]O(V)[/tex]. بدستش اورد.
ولی یه ایده واسه مسئله بالا میتونه این باشه که ما همهی دور ها رو توی گراف بدست میاریم و اونایی که یال مشترک دارن رو یال رو حذف میکنیم و این دور ها رو که باهم ادغام کنیم میشه همون دور اویلری که چون هر یال رو یک بار میبینیم میشه از [tex]O(E)[/tex] البته باید ببینیم که نظر طراح محترم چی هست
چطور همه دورها رو توی [tex]O(E)[/tex] به دست میارید؟!
بعدش چطور یال های مشترک رو در تمام دورها به دست میارید؟! لطفا توضیح بدید.
Sent from my SM-T210R using Tapatalk
(۰۷ دى ۱۳۹۲ ۰۲:۱۱ ب.ظ)Riemann نوشته شده توسط:(07 دى ۱۳۹۲ ۰۱:۱۱ ب.ظ)masoud67 نوشته شده توسط: منکه نمیدونم جریان چیه ولی فکر کنم این ریختی بشه حلش کرد
تو لیست مجاورتی به ازای تک تک یالها میری جلو و توی هر راس بررسی میکنی که درجه زوج هست یا نه. اگر همه راسهایی که دیدی زوج بود پس گراف اویلریه. به همین سادگی ولی مطمئن نیستم دقیقا همین شکلی باشه
این مسئله میخواد که تور اویلری رو پیدا کنیم نه این که ببینیم اویلری هست یا نه! اون چیزی که شما میگید رو میشه توی [tex]O(V)[/tex]. بدستش اورد.
ولی یه ایده واسه مسئله بالا میتونه این باشه که ما همهی دور ها رو توی گراف بدست میاریم و اونایی که یال مشترک دارن رو یال رو حذف میکنیم و این دور ها رو که باهم ادغام کنیم میشه همون دور اویلری که چون هر یال رو یک بار میبینیم میشه از [tex]O(E)[/tex] البته باید ببینیم که نظر طراح محترم چی هست
چطور همه دورها رو توی [tex]O(E)[/tex] به دست میارید؟!
بعدش چطور یال های مشترک رو در تمام دورها به دست میارید؟! لطفا توضیح بدید.
Sent from my SM-T210R using Tapatalk
(۰۸ دى ۱۳۹۲ ۱۱:۲۹ ق.ظ)e.sharmi نوشته شده توسط: نمیشه اینجوری گفت که از روی ماتریس مجاورت میریم جلو ، هر یالی رو که ملاقات کردیم اونو از تو ماتریس حذف میکنیم (درایه اش رو ۰ میکنیم) وقتی مثلا رسیدیم به راس b و برای خروج چند تا گزینه داشتیم ، یکی رو به دلخواه انتخاب میکنیم ، چون مطمئنیم به ازای همه ی اون یال های خروجی دیگه حتما یال ورودی هم داریم (گراف اویلری درجه ورودی و خروجی برابره) که بعدا میایم دوباره به همین راس و میتونیم باقی اون ها رو ملاقات کنیم. بنابراین تعداد مراحلی که طی میکنیم به اندازه تعداد ۱ های ماتریس یا همون تعداد یال هاست و چون چون یال رو بعد از ملاقات ۰ میکنیم ، امکان چند بار ملاقات کردن یال هم وجود نداره.خب اینکه شد یه دور. دورهای بعدی چی میشه؟
به نظز من اینجوری حل میشه که چون توی گراف اویلری میشه یالها رو به یک تعذاذ مجموعه مجزا تقسیم کنیم، کافیه اول دورها رو پیدا کنیم، بعد با هم ادغام کنیم. این ادغام با استفاده از مجموعه مجزا امکان پذیره!
(۰۸ دى ۱۳۹۲ ۱۱:۴۸ ق.ظ)س.غ نوشته شده توسط: به نظز من اینجوری حل میشه که چون توی گراف اویلری میشه یالها رو به یک تعذاذ مجموعه مجزا تقسیم کنیم، کافیه اول دورها رو پیدا کنیم، بعد با هم ادغام کنیم. این ادغام با استفاده از مجموعه مجزا امکان پذیره!
برای ترکیب مجموعه ها مشکل داریم چون عضو مشترک باید یه جای دیگه ذخیره شه و بشه نماینده ی اون مجموعه و موقع ترکیب با مجموعه های بعدی فقط همین یک عضو مشترک هست که اجازه ی ترکیب میده شبیه اینه که تو دور اویلری شروع کنیم بعد از مدتی که چرخیدیم برگردیم سر جای اول و راه نداشته باشیم
خسته نباشین!
جوابی که بعضی از دوستان دادن بیشتر به درد پیدا کردن مدار همیلتنی می خوره.
من فک کنم این سوال رو میشه با بررسی تک تک یال ها به دست آورد. این که یک یال چه تاثیری بر گراف می زاره:
ایده اینجوری که با مجموعه راس شروع می کنیم (یعنی هیچ یالی نداریم و فقط راس هاست) و با هر یال که در این مجموعه وارد می شه بررسی می کنیم که آیا این یال چه تاثیری بر راس ها می زاره . وقتی که یالی وارد مجموع بشه بررسی مس کنیم که آیا یک دور ایجاد شده یا نه. اگر ایجاد شد و با یکی از دورهای داخل مجموعه فقط در یک راس مشترک بود یعنی کلیه یال ها مجزا بود ادغام و یک دور بزرگتر تشکیل می شه. باید در اخر کلیه یال ها اضافه شده باشند و گراف همبند و متغیر دور true باشد. چون ممکن است در یک دور با امدن یک یال به هم بخورد.
به احتمال خیلی زیاد کار بکنه ولی یه خورده خامه باید روش کار کرد چون همین الان از آمار خوندن پریدم رو الگوریتم و گسسته.