زمان کنونی: ۲۸ آذر ۱۳۹۷, ۰۱:۳۲ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

رنگ آمیزی درخت (کنکور۸۷)

ارسال:
  

marzieh پرسیده:

رنگ آمیزی درخت (کنکور۸۷)

دوستان از کمکتون ممنونم Smile .. لطفا راهی برای حل این سوال بیابید ؟


فایل‌(های) پیوست شده

۲
ارسال:
  

Jooybari پاسخ داده:

رنگ آمیزی درخت (کنکور۸۷)

با سلام.
با توجه به صورت سوال درجه هر راس یا یکه یا سه. اگه 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]

۱
ارسال:
  

Jooybari پاسخ داده:

رنگ آمیزی درخت (کنکور۸۷)

شکل دوم شما اشتباهه. فقط e,f داریم. اگه g داشته باشیم که مجاور b باشه اون موقع درجه راس b میشه ۴/ اگه توجه کنین به راس b و راس a که مجاورشه رنگ نسبت دادیم. حالا رئوس e,f میمونن که درکل ۲ حالت دارن. فکر کنم بقیشو متوجه شده باشین.
با تشکر

۰
ارسال:
  

marzieh پاسخ داده:

رنگ آمیزی درخت (کنکور۸۷)

سلام. از پاسختون ممنونم
بیاین چک کنیم تا مطمئن بشم مطلب و گرفتم . فایل پیوست مراحل را نشون دادم .
اگر پاسختون رو چند قسمت کنم
قسمت اول را با شکل ۱ نشون دادم‌ :
(۱۲ دى ۱۳۹۰ ۰۲:۳۲ ق.ظ)Lakikharin نوشته شده توسط:  برای شمارش تعداد راه های رنگ آمیزی، یه رنگ به یکی از رئوس درجه ۳ و راس های مجاور میدیم. در کل این راس و ۳ راس مجاورش رو میشه به ۴! یا همون [tex]2^{3}*3[/tex] حالت رنگ آمیزی کرد. (این ۴ راس نمیتونن یک رنگ رو دوبار بگیرن. یعنی طبق فرض مسئله رنگاشون باهم متفاوته.)

قسمت دوم: ‌ منظورتون از مجاور رئوس رنگ آمیزی شده راس e,f,g است؟
(۱۲ دى ۱۳۹۰ ۰۲:۳۲ ق.ظ)Lakikharin نوشته شده توسط:  حالا نوبت به راس های از درجه ۳ای هست که به اونا تعداد حالت رنگ نسبت دادیم. (یعنی مجاور رئوس رنگ آمیزی شدست.)

قسمت سوم‌ Sadشکل ۲)
(۱۲ دى ۱۳۹۰ ۰۲:۳۲ ق.ظ)Lakikharin نوشته شده توسط:  این راس‌ها و یکی از رئوس مجاورش رنگ آمیزی شدن و ۲ خونه مجاورش هنوز بهشون رنگ نسبت داده نشده. این دو راس رو میشه به ۲ حالت رنگ کرد.
با قسمت سوم مشکل دارم ..منظورتون از اینکه ۲ خونه مجاورش هنوز بهشون رنگ اختصاص داده نشده f,g است؟ به e چند رنگ می شه اختصاص داد؟ ۲ رنگ؟

شکل ۱
و شکل۲


فایل‌(های) پیوست شده
۱/bmp
اندازه فایل: ۹۶/۲ KB
۲/bmp
اندازه فایل: ۷۷/۳۳ KB



پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

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

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close