از اون 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

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

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

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

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

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

ایده اینجوری که با مجموعه راس شروع می کنیم (یعنی هیچ یالی نداریم و فقط راس هاست) و با هر یال که در این مجموعه وارد می شه بررسی می کنیم که آیا این یال چه تاثیری بر راس ها می زاره . وقتی که یالی وارد مجموع بشه بررسی مس کنیم که آیا یک دور ایجاد شده یا نه. اگر ایجاد شد و با یکی از دورهای داخل مجموعه فقط در یک راس مشترک بود یعنی کلیه یال ها مجزا بود ادغام و یک دور بزرگتر تشکیل می شه. باید در اخر کلیه یال ها اضافه شده باشند و گراف همبند و متغیر دور true باشد. چون ممکن است در یک دور با امدن یک یال به هم بخورد.

به احتمال خیلی زیاد کار بکنه ولی یه خورده خامه باید روش کار کرد چون همین الان از آمار خوندن پریدم رو الگوریتم و گسسته.