تالار گفتمان مانشت
سوال : الگوریتم – گراف – مولفه های همبند قوی - نسخه‌ی قابل چاپ

سوال : الگوریتم – گراف – مولفه های همبند قوی - Morris - 16 دى ۱۳۹۲ ۰۳:۵۳ ب.ظ

سلام خدمت دوستان عزیز و صاحب نظر

در جزوه دکتر سید جوادی الگوریتمی برای بدست آوردن مولفه های همبند قوی مطرح شده است. به نظر من بند سوم آن نادرست است. این الگوریتم از جزوه را در زیر قرار داده ام.

[تصویر:  235259_01.jpg]

در کتاب CLRS 3.0 این الگوریتم به شکل دیگری آورده شده است و دقیقا مانند آنچه که در CLRS آمده است در کتاب الگوریتم پوران نیز مطرح شده است. این الگوریتم با آنچه دکتر سید جوادی مطرح نموده اند در بند سوم آن تفاوت دارد. این الگوریتم از CLRS 3.0 را در زیر قرار داده ام.

[تصویر:  235259_02.jpg]

در کتاب CLRS 3.0 مثالی آمده است و من هر دو الگوریتم فوق را (دکتر سید جوادی و CLRS 3.0) با شروع از گره f، بر روی آن اجرا نمودم و تنها الگوریتم CLRS درست عمل کرده است. این مثال را در زیر آورده ام.

[تصویر:  235259_03.jpg]

سوال من این است که آیا الگوریتم جزوه صحیح می باشد و اگر پاسخ به نظر شما مثبت است لطفا بفرمایید چطور.

RE: سوال : الگوریتم – گراف – مولفه های همبند قوی - hoomanab - 16 دى ۱۳۹۲ ۰۵:۰۰ ب.ظ

فکر کنم بر اساس بزرگترین زمان پایان درست باشه

Sent from my SM-T210R using Tapatalk

RE: سوال : الگوریتم – گراف – مولفه های همبند قوی - Morris - 17 دى ۱۳۹۲ ۱۲:۳۱ ق.ظ

(۱۶ دى ۱۳۹۲ ۰۵:۰۰ ب.ظ)hoomanab نوشته شده توسط:  فکر کنم بر اساس بزرگترین زمان پایان درست باشه

Sent from my SM-T210R using Tapatalk







ممنونم از شما دوست عزیز.
کسی دیگه نظری نداره ؟

RE: سوال : الگوریتم – گراف – مولفه های همبند قوی - izadan11 - 24 دى ۱۳۹۲ ۰۹:۲۰ ق.ظ

این الگوریتم یکی از عجیب ترین الگوریتم هایی هست که تو عمرم دیدم
قبلا که بررسی کردم برای مرله ی سوم تو یادداشت هام نوشتم :از بالاترین مقدار زمان پایان شروع به dfs می زنیم و اینقدر تکرار می کنیم تا همه ی مولفه ها را پیدا کنیم تو پرانتز هم نوشتم (توضیحش سخت و طولانی)
چند ساعت وقتمو گرفت تا قضیه رو فهمیدمTongue

RE: سوال : الگوریتم – گراف – مولفه های همبند قوی - Morris - 24 دى ۱۳۹۲ ۰۳:۱۳ ب.ظ

(۲۴ دى ۱۳۹۲ ۰۹:۲۰ ق.ظ)izadan11 نوشته شده توسط:  این الگوریتم یکی از عجیب ترین الگوریتم هایی هست که تو عمرم دیدم
قبلا که بررسی کردم برای مرله ی سوم تو یادداشت هام نوشتم :از بالاترین مقدار زمان پایان شروع به dfs می زنیم و اینقدر تکرار می کنیم تا همه ی مولفه ها را پیدا کنیم تو پرانتز هم نوشتم (توضیحش سخت و طولانی)
چند ساعت وقتمو گرفت تا قضیه رو فهمیدمTongue

پس شما نیز معتقدید که دکتر اشتباه گفته اند ؟

RE: سوال : الگوریتم – گراف – مولفه های همبند قوی - izadan11 - 24 دى ۱۳۹۲ ۰۶:۳۶ ب.ظ

(۲۴ دى ۱۳۹۲ ۰۳:۱۳ ب.ظ)Morris نوشته شده توسط:  
(24 دى ۱۳۹۲ ۰۹:۲۰ ق.ظ)izadan11 نوشته شده توسط:  این الگوریتم یکی از عجیب ترین الگوریتم هایی هست که تو عمرم دیدم
قبلا که بررسی کردم برای مرله ی سوم تو یادداشت هام نوشتم :از بالاترین مقدار زمان پایان شروع به dfs می زنیم و اینقدر تکرار می کنیم تا همه ی مولفه ها را پیدا کنیم تو پرانتز هم نوشتم (توضیحش سخت و طولانی)
چند ساعت وقتمو گرفت تا قضیه رو فهمیدمTongue

پس شما نیز معتقدید که دکتر اشتباه گفته اند ؟

بله

RE: سوال : الگوریتم – گراف – مولفه های همبند قوی - Morris - 24 دى ۱۳۹۲ ۰۷:۰۱ ب.ظ

(۲۴ دى ۱۳۹۲ ۰۶:۳۶ ب.ظ)izadan11 نوشته شده توسط:  
(24 دى ۱۳۹۲ ۰۳:۱۳ ب.ظ)Morris نوشته شده توسط:  
(24 دى ۱۳۹۲ ۰۹:۲۰ ق.ظ)izadan11 نوشته شده توسط:  این الگوریتم یکی از عجیب ترین الگوریتم هایی هست که تو عمرم دیدم
قبلا که بررسی کردم برای مرله ی سوم تو یادداشت هام نوشتم :از بالاترین مقدار زمان پایان شروع به dfs می زنیم و اینقدر تکرار می کنیم تا همه ی مولفه ها را پیدا کنیم تو پرانتز هم نوشتم (توضیحش سخت و طولانی)
چند ساعت وقتمو گرفت تا قضیه رو فهمیدمTongue

پس شما نیز معتقدید که دکتر اشتباه گفته اند ؟

بله

سپاس