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

sلام ..
۱/ چون باید مسطح بودن ملاک قرار بدیم پس ما شاید همه یالها که به n میرود رو حساب نکنیم .. مثلا اگر دو راس داشته باشیم که مشکلی نیست ولی اگر بیشتر از ۲تا باشه رو با مقایسه رابطه E<=3V-6 حساب میکنیم
(حد مجانبها رو در نظر بگیریم از یک جایی به بعد که لازم نیست یالی رو بررسی کنیم پس حدش در هر حالت به n نمیرسه یعنی n همیشه عددی هست که در واقعیت هست و بی نهایت نیست یعنی اگر ۱۰۰۰۰۰۰ هم باشه باز هم زمان اجرایش ۱ هست چون حد دارد و انتها داره)

۲/ اگر مسطح بودن رو برداریم تعداد دورها رو میشه در زمان O(V+E) بدست آورد

۳/ این معنی نداره .. چون بعضی جاها به همون گراف , گراف ساده هم میگویند

اگر اشتباه میگم اصلاح کنید
موفق باشید

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

(10 بهمن ۱۳۹۲ ۱۲:۲۲ ب.ظ)e.sharmi نوشته شده توسط:  سلام دوستان
یه سوال.
تو سوال های سال ۸۱ ، یه سوال هست که گفته شده تعداد دور در گراف ساده مسطح رو میشه با مرتبه ۱ با استفاده از فرمول اویلر حساب کرد.
من چند تا سوال دارم :
۱- تو این سوال فرض شده که ما تعداد یال های رو میدونیم؟ اگر بخوایم تعداد یال ها رو بدست بیاریم این خودش n زمان نمی خواد؟
۲- اگر قید مسطح بودن رو برداریم ، زمان چی میشه؟
۳- اگر قید ساده بودن رو برداریم چی میشه ؟

sلام ..
۱/ چون باید مسطح بودن ملاک قرار بدیم پس ما شاید همه یالها که به n میرود رو حساب نکنیم .. مثلا اگر دو راس داشته باشیم که مشکلی نیست ولی اگر بیشتر از ۲تا باشه رو با مقایسه رابطه E<=3V-6 حساب میکنیم
(حد مجانبها رو در نظر بگیریم از یک جایی به بعد که لازم نیست یالی رو بررسی کنیم پس حدش در هر حالت به n نمیرسه یعنی n همیشه عددی هست که در واقعیت هست و بی نهایت نیست یعنی اگر ۱۰۰۰۰۰۰ هم باشه باز هم زمان اجرایش ۱ هست چون حد دارد و انتها داره)

۲/ اگر مسطح بودن رو برداریم تعداد دورها رو میشه در زمان O(V+E) بدست آورد

۳/ این معنی نداره .. چون بعضی جاها به همون گراف , گراف ساده هم میگویند

اگر اشتباه میگم اصلاح کنید
موفق باشید

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

(۱۰ بهمن ۱۳۹۲ ۰۳:۵۱ ب.ظ)e.sharmi نوشته شده توسط:  ممنون از توضیحتون.
در گراف جهت دار تعداد دور جهت دار رو چه جوری میشه حساب کرد. میدونم که وجود دور رو با DFS میشه پیدا کرد ولی این الگوریتم تعداد رو نمیده.
همین سوال اگر گراف جهت دار نباشه ، شما میگید با DFS میشه ؟ با یک بار DFS ؟

خواهش میکنم .. فقط ببخشید با قاطعیت صددرصد جواب ندادم

سوالتون باعث شد چندتا نکته یادبگیرم به شما هم میگم (البته اینا رو براساس جوابهای کتابا از کنکورها نتیجه گرفتم)
۱/ اگر گراف جهت دار باشه برای یافتن دور داریم O(V+E)
۲/ اگر گراف غیر جهت دار باشه برای یافتن دور داریم O(V) .. البته این بهترین حالتش هست
۳/ تعداد دورها یکی از تعداد نواحی کمتر است ... نواحی =e-v+2

خب حالا سوال شما:
در یک گرف جهت دار که میخوایم دور رو با dfs پیدا کنیم چون باید تمام راسها رو پیمایش کنیم پس جواب میشه جمع تعداد رئوس با تعداد یالها یعنی همون O(e+v)

در مورد گراف غیرجهتدار هم اگر بهترین حالت رو فرض کنیم (یعنی درجه هر گره ۲ باشه) پس مرتبش میشه O(v)

فکر میکنم سوال شما بخاطر این بود که تایید کنید حرف اولتون رو که باید جواب n میشد ..
به هر حال منم هنوز دقیقا مطمئن نیستم که چطور ۱ شد .. بحث مجانبها و اینکه محدود به مسطح بودن هست رو پیش کشید چون فکر کنم بغیر اینا همون n صحیح هست

ببینید من دقیقا سوالم رو تعداد دور در گراف جهت دار و تعداد دور در گراف غیر جهت دار غیر مسطح هست.
من از روی ۶۰۰ مساله دارم می گم که اکیدا گفته با DFS فقط میشه وجود یا عدم وجود دور رو تشخیص داد ولی تعداد رو نه ، میخوام بودم تعداد رو باید چی کار کرد؟