دوستان از کمکتون ممنونم
.. لطفا راهی برای حل این سوال بیابید ؟
با سلام.
با توجه به صورت سوال درجه هر راس یا یکه یا سه. اگه a تعداد راس های از درجه ۳ و b تعداد راس های از درجه ۱ باشن داریم:
a+b=20 (تعداد رئوس)
۳a+b=19*2 (تعداد یال ها)
از حل معادله بدست میاد که a یا همون تعداد رئوس با درجه ۳ برابر ۹ هست. مسلماً هرکدوم از این رپوس حداقل با یکی دیگه از رئوس درجه ۳ مجاوره.
برای شمارش تعداد راه های رنگ آمیزی، یه رنگ به یکی از رئوس درجه ۳ و راس های مجاور میدیم. در کل این راس و ۳ راس مجاورش رو میشه به ۴! یا همون [tex]2^{3}*3[/tex] حالت رنگ آمیزی کرد. (این ۴ راس نمیتونن یک رنگ رو دوبار بگیرن. یعنی طبق فرض مسئله رنگاشون باهم متفاوته.)
حالا نوبت به راس های از درجه ۳ای هست که به اونا تعداد حالت رنگ نسبت دادیم. (یعنی مجاور رئوس رنگ آمیزی شدست.) این راس‌ها و یکی از رئوس مجاورش رنگ آمیزی شدن و ۲ خونه مجاورش هنوز بهشون رنگ نسبت داده نشده. این دو راس رو میشه به ۲ حالت رنگ کرد. این کارو تا انتخاب حالات رنگ هر ۹ راس با درجه ۳ ادامه میدیم که مسلماً رئوس درجه ۱ مجاورشون هم رنگ میشن. بجز راس درجه ۳ اول که ۴! حالت برای رنگ آمیزی داشت، بقیه رئوس درجه ۳ هرکدام ۲ حالت دارن. پس جواب مسئلمون میشه:
[tex]2^{3}*3*2^{8}=2^{11}*3[/tex]
سلام. از پاسختون ممنونم
بیاین چک کنیم تا مطمئن بشم مطلب و گرفتم . فایل پیوست مراحل را نشون دادم .
اگر پاسختون رو چند قسمت کنم
قسمت اول را با شکل ۱ نشون دادم :
(۱۲ دى ۱۳۹۰ ۰۲:۳۲ ق.ظ)Lakikharin نوشته شده توسط: برای شمارش تعداد راه های رنگ آمیزی، یه رنگ به یکی از رئوس درجه ۳ و راس های مجاور میدیم. در کل این راس و ۳ راس مجاورش رو میشه به ۴! یا همون [tex]2^{3}*3[/tex] حالت رنگ آمیزی کرد. (این ۴ راس نمیتونن یک رنگ رو دوبار بگیرن. یعنی طبق فرض مسئله رنگاشون باهم متفاوته.)
قسمت دوم: منظورتون از مجاور رئوس رنگ آمیزی شده راس e,f,g است؟
(۱۲ دى ۱۳۹۰ ۰۲:۳۲ ق.ظ)Lakikharin نوشته شده توسط: حالا نوبت به راس های از درجه ۳ای هست که به اونا تعداد حالت رنگ نسبت دادیم. (یعنی مجاور رئوس رنگ آمیزی شدست.)
قسمت سوم
شکل ۲)
(۱۲ دى ۱۳۹۰ ۰۲:۳۲ ق.ظ)Lakikharin نوشته شده توسط: این راس‌ها و یکی از رئوس مجاورش رنگ آمیزی شدن و ۲ خونه مجاورش هنوز بهشون رنگ نسبت داده نشده. این دو راس رو میشه به ۲ حالت رنگ کرد.با قسمت سوم مشکل دارم ..منظورتون از اینکه ۲ خونه مجاورش هنوز بهشون رنگ اختصاص داده نشده f,g است؟ به e چند رنگ می شه اختصاص داد؟ ۲ رنگ؟
شکل ۱
و شکل۲
شکل دوم شما اشتباهه. فقط e,f داریم. اگه g داشته باشیم که مجاور b باشه اون موقع درجه راس b میشه ۴/ اگه توجه کنین به راس b و راس a که مجاورشه رنگ نسبت دادیم. حالا رئوس e,f میمونن که درکل ۲ حالت دارن. فکر کنم بقیشو متوجه شده باشین.
با تشکر