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

استاد یک درس می‌خواهد پروژه‌هایی را برای اعضای کلاس به صورت گروهی تعریف کند. بعد از طرح مسئله با دانشجویان آنها به N گروه تقسیم می‌شوند. استاد طبق شناختی که از این گروه‌ها دارد می‌داند کدام گروه با کدام گروه می‌تواند ارتباط داشته باشد. بنابراین هدف استاد این است که برای گروه‌هایی که با هم ارتباط دارند پروژه‌های متفاوتی تعریف کند تا نتوانند پروژه‌ها را از روی هم انجام دهند. استاد درس این ارتباطات را به صورت یک گراف برای خود ترسیم می‌کند و هدفش این است که کمترین تعداد ممکن پروژه را تعریف کند. اگر شما بخواهید به این استاد کمک کنید چه الگوریتمی را به او پیشنهاد می‌دهید تا کمترین تعداد پروژه مورد نیاز برای این کلاس را مشخص کنید؟ (نیازی به نوشتن کامل الگوریتم نیست، فقط اسم الگوریتم را گفته و توضیح دهید چرا این الگوریتم می‌تواند برای این مسئله کاربرد داشته باشد؟)

ارسال: #۲

۰۷ دى ۱۳۹۱, ۱۱:۲۸ ق.ظ

mp1368 پاسخ داده:

RE: چه الگوریتمی را به او پیشنهاد می‌دهید

سلام .
این که دیگه معلومه مسئله رنگ آمیزی است.
گروه ها رو رئوس گراف قرار بده ارتباط گروه ها رو هم یال های گراف، حالا ببین با چند رنگ متمایز میتونی گراف رو رنگ آمیزی کنی همون میشه تعداد پروژه ها.

ارسال: #۳

۰۷ دى ۱۳۹۱, ۰۱:۲۶ ب.ظ

ali_h_8224 پاسخ داده:

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

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

ارسال: #۴

۰۷ دى ۱۳۹۱, ۰۲:۰۹ ب.ظ

mp1368 پاسخ داده:

RE: چه الگوریتمی را به او پیشنهاد می‌دهید

سلام .
این یه الگوریتم استاندارد هستش که میتونی توضیح کاملش رو توی کتاب گسسته ببینی . حالا من اینجا یه مثال ساده واست میزنم که جریان رو بفهمی .

فرض میکنیم کلاس ۲۰ نفر عضو داره که استاد اونا رو به ۴ گروه ۵ نفره تقسیم میکنه {A,B,C,D} .
فرض میکنیم که این گروه ها همه با هم ارتباط دارن و به این ترتیب ممکن هست که در انجام پروژه ها به هم کمک کنند . پس مجبوریم به ۴ گروه چون همه با هم ارتباط دارن ۴ پروژه متفاوت بدیم که از روی هم کپ نزنن Big Grin

حالا میخوایم این مسئله رو با رنگ آمیزی حل کنیم .
رنگ آمیزی گراف : رنگ کردن رئوس گراف به صورتی که هیچ دو راس مجاوری حاوی رنگ یکسانی نباشند (برای مثال ما هیچ دو گروهی که با هم ارتباط دارند، حاوی پروژه یکسانی نباشند)

ابتدا گراف مسئله رو به صورت زیر تشکیل میدیم

خب حالا طبق تعریف رنگ آمیزی، گراف رو به صورت زیر رنگ میکنیم

در نتیجه این گراف حتما باید با چهار رنگ متفاوت رنگ شود که میشه همون تعداد پروژه های چهار گروه.
جزئیات رنگ آمیزی گراف رو توی کتاب گسسته پی بگیر.

ارسال: #۵

۰۷ دى ۱۳۹۱, ۰۴:۵۶ ب.ظ

ali_h_8224 پاسخ داده:

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

ممنونم از کمکتون میشه اگه این ۳تایه دیگه رو هم بلدین یه کمکی بکنین ممنون میشم.

موضوع‌های مرتبط با این موضوع...
موضوع:		نویسنده	پاسخ:	بازدید:	آخرین ارسال
	خرید دیزل ژنراتور یک پیشنهاد عالی برای فرا ا	tiaragenerators	۰	۷۵۳	۱۷ آبان ۱۴۰۲ ۰۱:۵۵ ب.ظ آخرین ارسال: tiaragenerators
	پیشنهاد نام برای سلسه گفتگوها با افراد مختلف	Doctorwho	۰	۱,۷۶۹	۰۳ اردیبهشت ۱۴۰۰ ۱۲:۳۹ ق.ظ آخرین ارسال: Doctorwho
	پیشنهاد رشته یا دانشگاه	علیصا	۱	۲,۴۲۱	۱۸ مهر ۱۳۹۸ ۰۴:۱۷ ب.ظ آخرین ارسال: marvelous
	کدوم آموزشگاه زبان رو برا دوره آیلس پیشنهاد می کنید؟؟؟	berkeley	۲۳	۴۰,۵۸۶	۱۱ تیر ۱۳۹۷ ۰۱:۲۸ ب.ظ آخرین ارسال: آریا بختیارنیا
	چطور میشه هر الگوریتمی را طوری تغییر داد که بهترین زمان اجرای خوبی داشته باشه؟	farid612004	۱	۱,۸۵۴	۱۷ آبان ۱۳۹۶ ۰۴:۱۴ ب.ظ آخرین ارسال: msour44
	پیشنهاد ایجاد مانشت انگلیسی برای بحث و گفتگو به زبان انگلیسی	Msccom	۱۲	۱۱,۴۲۴	۱۳ مهر ۱۳۹۶ ۱۰:۲۳ ق.ظ آخرین ارسال: NP-Cσмρℓєтє
	فروش هر کتابی (کاملا نو) از پارسه که بخوای! (پیشنهاد تخفیفات فوق العاده جدید)	lili36	۵۱	۳۱,۹۰۷	۰۴ مهر ۱۳۹۶ ۰۷:۵۱ ب.ظ آخرین ارسال: lili36
	پیشنهاد موضوع پایان نامه نرم افزار	payamjj	۰	۲,۱۲۹	۰۴ مهر ۱۳۹۶ ۰۵:۱۹ ب.ظ آخرین ارسال: payamjj
	پیشنهاد موضوع پایان نامه هوش مصنوعی - مهم	stominer	۱۸	۳۳,۱۹۶	۲۷ شهریور ۱۳۹۶ ۰۶:۵۱ ب.ظ آخرین ارسال: asgharshirdel
	لطفا یک پروژه کارشناسی پیشنهاد بدید	Rehe1994	۶	۵,۴۳۷	۲۹ بهمن ۱۳۹۵ ۱۱:۵۸ ب.ظ آخرین ارسال: husen

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

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

RE: چه الگوریتمی را به او پیشنهاد می‌دهید

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

RE: چه الگوریتمی را به او پیشنهاد می‌دهید

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

Can I see some ID?

Feeling left out?

رمزت رو فراموش کردی؟

Feeling left out?