۰
subtitle
ارسال: #۱
  
رنگ آمیزی درخت (کنکور۸۷)
دوستان از کمکتون ممنونم .. لطفا راهی برای حل این سوال بیابید ؟
۲
ارسال: #۲
  
رنگ آمیزی درخت (کنکور۸۷)
با سلام.
با توجه به صورت سوال درجه هر راس یا یکه یا سه. اگه 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]
با توجه به صورت سوال درجه هر راس یا یکه یا سه. اگه 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]
۱
ارسال: #۳
  
رنگ آمیزی درخت (کنکور۸۷)
شکل دوم شما اشتباهه. فقط e,f داریم. اگه g داشته باشیم که مجاور b باشه اون موقع درجه راس b میشه ۴/ اگه توجه کنین به راس b و راس a که مجاورشه رنگ نسبت دادیم. حالا رئوس e,f میمونن که درکل ۲ حالت دارن. فکر کنم بقیشو متوجه شده باشین.
با تشکر
با تشکر
۰
ارسال: #۴
  
رنگ آمیزی درخت (کنکور۸۷)
سلام. از پاسختون ممنونم
بیاین چک کنیم تا مطمئن بشم مطلب و گرفتم . فایل پیوست مراحل را نشون دادم .
اگر پاسختون رو چند قسمت کنم
قسمت اول را با شکل ۱ نشون دادم :
قسمت دوم: منظورتون از مجاور رئوس رنگ آمیزی شده راس e,f,g است؟
قسمت سوم شکل ۲)
شکل ۱
و شکل۲
بیاین چک کنیم تا مطمئن بشم مطلب و گرفتم . فایل پیوست مراحل را نشون دادم .
اگر پاسختون رو چند قسمت کنم
قسمت اول را با شکل ۱ نشون دادم :
(۱۲ دى ۱۳۹۰ ۰۲:۳۲ ق.ظ)Lakikharin نوشته شده توسط: برای شمارش تعداد راه های رنگ آمیزی، یه رنگ به یکی از رئوس درجه ۳ و راس های مجاور میدیم. در کل این راس و ۳ راس مجاورش رو میشه به ۴! یا همون [tex]2^{3}*3[/tex] حالت رنگ آمیزی کرد. (این ۴ راس نمیتونن یک رنگ رو دوبار بگیرن. یعنی طبق فرض مسئله رنگاشون باهم متفاوته.)
قسمت دوم: منظورتون از مجاور رئوس رنگ آمیزی شده راس e,f,g است؟
(۱۲ دى ۱۳۹۰ ۰۲:۳۲ ق.ظ)Lakikharin نوشته شده توسط: حالا نوبت به راس های از درجه ۳ای هست که به اونا تعداد حالت رنگ نسبت دادیم. (یعنی مجاور رئوس رنگ آمیزی شدست.)
قسمت سوم شکل ۲)
(۱۲ دى ۱۳۹۰ ۰۲:۳۲ ق.ظ)Lakikharin نوشته شده توسط: این راسها و یکی از رئوس مجاورش رنگ آمیزی شدن و ۲ خونه مجاورش هنوز بهشون رنگ نسبت داده نشده. این دو راس رو میشه به ۲ حالت رنگ کرد.با قسمت سوم مشکل دارم ..منظورتون از اینکه ۲ خونه مجاورش هنوز بهشون رنگ اختصاص داده نشده f,g است؟ به e چند رنگ می شه اختصاص داد؟ ۲ رنگ؟
شکل ۱
و شکل۲
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
تعداد برگ درخت؟؟؟؟؟؟؟ | rad.bahar | ۴ | ۴,۸۴۹ |
۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ آخرین ارسال: mohamadrra |
|
اصطلاحات انگلیسی با رنگها آموزش زبان انگلیسی | cyruskingsolomon | ۰ | ۱,۸۹۷ |
۲۸ فروردین ۱۴۰۰ ۱۲:۳۰ ق.ظ آخرین ارسال: cyruskingsolomon |
|
دو سوال در مورد درخت BST(درخت جستجوی دودویی) | امیدوار | ۳ | ۵,۶۱۳ |
۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ آخرین ارسال: marzi.pnh |
|
زمان جستجوی درخت | fateme.sm | ۰ | ۱,۷۸۹ |
۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ آخرین ارسال: fateme.sm |
|
مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۴۰۲ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
عمق درخت ???? | rad.bahar | ۱ | ۲,۴۰۹ |
۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ آخرین ارسال: عزیز دادخواه |
|
محاسبه ارتفاع درخت.... | baharkhanoom | ۳ | ۸,۱۳۱ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ آخرین ارسال: mohsentafresh |
|
رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) | ss311 | ۰ | ۲,۱۳۳ |
۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ آخرین ارسال: ss311 |
|
تعداد درخت فراگیر | ss311 | ۰ | ۲,۳۲۲ |
۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ آخرین ارسال: ss311 |
|
درخت دسترس پذیری برای شبکه های پتری | αɾια | ۱ | ۲,۴۱۴ |
۰۹ تیر ۱۳۹۸ ۰۶:۳۰ ب.ظ آخرین ارسال: αɾια |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close