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

چه الگوریتمی را به او پیشنهاد می‌دهید - ali_h_8224 - 07 دى ۱۳۹۱ ۰۳:۴۳ ق.ظ استاد یک درس می‌خواهد پروژه‌هایی را برای اعضای کلاس به صورت گروهی تعریف کند. بعد از طرح مسئله با دانشجویان آنها به N گروه تقسیم می‌شوند. استاد طبق شناختی که از این گروه‌ها دارد می‌داند کدام گروه با کدام گروه می‌تواند ارتباط داشته باشد. بنابراین هدف استاد این است که برای گروه‌هایی که با هم ارتباط دارند پروژه‌های متفاوتی تعریف کند تا نتوانند پروژه‌ها را از روی هم انجام دهند. استاد درس این ارتباطات را به صورت یک گراف برای خود ترسیم می‌کند و هدفش این است که کمترین تعداد ممکن پروژه را تعریف کند. اگر شما بخواهید به این استاد کمک کنید چه الگوریتمی را به او پیشنهاد می‌دهید تا کمترین تعداد پروژه مورد نیاز برای این کلاس را مشخص کنید؟ (نیازی به نوشتن کامل الگوریتم نیست، فقط اسم الگوریتم را گفته و توضیح دهید چرا این الگوریتم می‌تواند برای این مسئله کاربرد داشته باشد؟)

RE: چه الگوریتمی را به او پیشنهاد می‌دهید - mp1368 - 07 دى ۱۳۹۱ ۱۱:۲۸ ق.ظ سلام . این که دیگه معلومه مسئله رنگ آمیزی است. گروه ها رو رئوس گراف قرار بده ارتباط گروه ها رو هم یال های گراف، حالا ببین با چند رنگ متمایز میتونی گراف رو رنگ آمیزی کنی همون میشه تعداد پروژه ها.

چه الگوریتمی را به او پیشنهاد می‌دهید - ali_h_8224 - 07 دى ۱۳۹۱ ۰۱:۲۶ ب.ظ سلام ببخشین اگه وقت دارین و میشه جواب کاملش رو بزارین چون واقعا به جواب این سئوالها نیاز دارم

RE: چه الگوریتمی را به او پیشنهاد می‌دهید - mp1368 - 07 دى ۱۳۹۱ ۰۲:۰۹ ب.ظ سلام . این یه الگوریتم استاندارد هستش که میتونی توضیح کاملش رو توی کتاب گسسته ببینی . حالا من اینجا یه مثال ساده واست میزنم که جریان رو بفهمی . فرض میکنیم کلاس ۲۰ نفر عضو داره که استاد اونا رو به ۴ گروه ۵ نفره تقسیم میکنه {A,B,C,D} . فرض میکنیم که این گروه ها همه با هم ارتباط دارن و به این ترتیب ممکن هست که در انجام پروژه ها به هم کمک کنند . پس مجبوریم به ۴ گروه چون همه با هم ارتباط دارن ۴ پروژه متفاوت بدیم که از روی هم کپ نزنن حالا میخوایم این مسئله رو با رنگ آمیزی حل کنیم . رنگ آمیزی گراف : رنگ کردن رئوس گراف به صورتی که هیچ دو راس مجاوری حاوی رنگ یکسانی نباشند (برای مثال ما هیچ دو گروهی که با هم ارتباط دارند، حاوی پروژه یکسانی نباشند) ابتدا گراف مسئله رو به صورت زیر تشکیل میدیم [attachment=8651] خب حالا طبق تعریف رنگ آمیزی، گراف رو به صورت زیر رنگ میکنیم [attachment=8652] در نتیجه این گراف حتما باید با چهار رنگ متفاوت رنگ شود که میشه همون تعداد پروژه های چهار گروه. جزئیات رنگ آمیزی گراف رو توی کتاب گسسته پی بگیر.

چه الگوریتمی را به او پیشنهاد می‌دهید - ali_h_8224 - 07 دى ۱۳۹۱ ۰۴:۵۶ ب.ظ ممنونم از کمکتون میشه اگه این ۳تایه دیگه رو هم بلدین یه کمکی بکنین ممنون میشم.