سلام دوستان
ممنون میشم اگه کسی حل این سوالو میدونه منو راهنمایی کنه(کتاب پوران هیچ راه حلی توضیح نداده) پیشاپیش سپاسگذارم
فرض کنید گرافی ۲۱ راسی داریم ک ۱۹ راس درجه ۴ و ۲ راس درجه ۳ داریم.مینیمم تعداد رنگی که لازم باشد تا یالهای گراف را رنگ امیزی کنیم به طوری که هر دو یال متصل رنگهای متفاوتی داشته باشند برابر است با:
۱)۲
۲)۳
۳)۴
۴)۵
جواب گزینه ۴
من باشکل میکشم ۵ تا میشه ولی خیلی طول میکشه میخام ببینم راه حل دیگه ای هست ک ساده تر باشه
باتشکر
یعنی کسی حل این سوالو نمیدونه
من هم تو این سوال مشکل دارم. دوستان ممکنه راهنمایی کنین؟
سلام
مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱
پس با توجه به درجات رئوس گراف این عدد ۴ یا ۵ میشود.
گراف مورد نظر غیر دوبخشی است و مشخص کردن تعداد رنگ ها طولانی می شود. اما با توجه به این اصل که تعداد رنگ های تمام گراف های دو بخشی و اکثر گراف های تصادفی برابر ماکزیمم درجه گراف است. می توان نتیجه گرفت جواب ۵ است چون گراف این سوال اگر دو بخشی بود به ۴ رنگ نیاز داشت چون دو بخشی نیست پس ۵ رنگ نیاز دارد.
امیدوارم قابل فهم بوده باشه
(۲۶ آذر ۱۳۹۳ ۰۱:۴۷ ق.ظ)newuser نوشته شده توسط: مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱
توضیح عالی بود.
در مورد فرمول "مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱" این فرمول برای کدوم دسته از گرافهاست؟ غیر دو بخشی ها؟
(۲۶ آذر ۱۳۹۳ ۰۹:۵۵ ق.ظ)ldns0098 نوشته شده توسط:(26 آذر ۱۳۹۳ ۰۱:۴۷ ق.ظ)newuser نوشته شده توسط: مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱
توضیح عالی بود.
در مورد فرمول "مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱" این فرمول برای کدوم دسته از گرافهاست؟ غیر دو بخشی ها؟
این فرمول واسه حالت کلی
البته دو بخشی ها حالت خاص هستند که با دو رنگ میشه رنگ آمیزی کرد چون عدد فامی ۲ دارند
(۲۶ آذر ۱۳۹۳ ۰۱:۴۷ ق.ظ)newuser نوشته شده توسط: سلام
مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱
پس با توجه به درجات رئوس گراف این عدد ۴ یا ۵ میشود.
گراف مورد نظر غیر دوبخشی است و مشخص کردن تعداد رنگ ها طولانی می شود. اما با توجه به این اصل که تعداد رنگ های تمام گراف های دو بخشی و اکثر گراف های تصادفی برابر ماکزیمم درجه گراف است. می توان نتیجه گرفت جواب ۵ است چون گراف این سوال اگر دو بخشی بود به ۴ رنگ نیاز داشت چون دو بخشی نیست پس ۵ رنگ نیاز دارد.
امیدوارم قابل فهم بوده باشه
سلام
ممنونم از پاسخت و راهنمایتون دیگه از این ک کسی ب این سوال من جواب بده نامید شده بودم و فراموشش کردم
واقعا تشکر
فرمولی که ذکر شد غلطه ، مینیمم رنگ مورد نیاز بین مینیمم درجه رئوس و ماکزیمم درجه رئوس + ۱ هست ( یعنی توی این بازه)
مثال نقض حرفتون هم گراف k1,5 که با ۲ رنگ ، میشه رنگش کرد ولی ماکزیمم درجه ۵ هست
در ضمن گراف ۲ بخشی با ۲ رنگ ، رنگ میشه نه ۴ رنگ
البته جواب این سوال همون ۵ هست ولی شما باید از اینجا میتونید بهش برسید ： بدترین حالت اینه که ۱۹ تا گره یه جورایی شبیه درخت،باشند ، درختشو با ضریب انشعاب ۴ بکشید میبینید آخراش اینا مجبور میشن بهم وصل بشند و باعث میشه نشه با کمتر از ۵ تا رنگ کرد
(۲۷ آذر ۱۳۹۳ ۰۸:۳۷ ق.ظ)Densike نوشته شده توسط: فرمولی که ذکر شد غلطه ، مینیمم رنگ مورد نیاز بین مینیمم درجه رئوس و ماکزیمم درجه رئوس + ۱ هست ( یعنی توی این بازه)از توجه شماهم سپاسگذارم الان ک دارم ب توضیحات شما هم فکر میکنم میبینم مستدل تر
مثال نقض حرفتون هم گراف k1,5 که با ۲ رنگ ، میشه رنگش کرد ولی ماکزیمم درجه ۵ هست
در ضمن گراف ۲ بخشی با ۲ رنگ ، رنگ میشه نه ۴ رنگ
البته جواب این سوال همون ۵ هست ولی شما باید از اینجا میتونید بهش برسید ： بدترین حالت اینه که ۱۹ تا گره یه جورایی شبیه درخت،باشند ، درختشو با ضریب انشعاب ۴ بکشید میبینید آخراش اینا مجبور میشن بهم وصل بشند و باعث میشه نشه با کمتر از ۵ تا رنگ کرد
حالا انشالله دوستان دیگه هم نظر بدن تا ابهامات رفع بشه
این استدلال که روش خاصی رو ذکر نکرده اومده رسمش کرده!!
گراف دو بخشی که بحثش جداست. اصلا گراف دو بخشی گرافیه که عدد فامی ۲ داشته باشه پس قطعا ۲ رو رنگ نیاز داره
شاید تو توضیحاتم اشتباه کردم گفتم "اگر دو بخشی بود با ۴ رنگ رنگ آمیزی میشد " فقط سهوا ۴ رو گفتم بهتر بود میگفتم اگر دو بخشی بود که عدد فامی ۲ داشت پس ۲ رنگ کافی بود. در واقع میخواستم حالات خاص رو حذف کنم وگرنه فرمول درسته
(۲۷ آذر ۱۳۹۳ ۱۱:۴۰ ق.ظ)newuser نوشته شده توسط: این استدلال که روش خاصی رو ذکر نکرده اومده رسمش کرده!!
گراف دو بخشی که بحثش جداست. اصلا گراف دو بخشی گرافیه که عدد فامی ۲ داشته باشه پس قطعا ۲ رو رنگ نیاز داره
شاید تو توضیحاتم اشتباه کردم گفتم "اگر دو بخشی بود با ۴ رنگ رنگ آمیزی میشد " فقط سهوا ۴ رو گفتم بهتر بود میگفتم اگر دو بخشی بود که عدد فامی ۲ داشت پس ۲ رنگ کافی بود. در واقع میخواستم حالات خاص رو حذف کنم وگرنه فرمول درسته
میخواید واستون مثال نقض بفرستم؟ مثلا گراف چرخ ، ماکزیمم درجه n هست ولی با ۳ یا ۴ رنگ بسته زوج و فرد بودن تعداد راس ها میشه رنگش کرد ، این که دیگه ۲ بخشی هم نیست ّ
درستش اینه که تعداد رنگ مورد نیاز یه عددی هست تو بازه تعداد کلیک های گراف و ماکزیمم درجه + ۱ (حتی بعضی مواقع میتونه از مینیمم درجه هم کمتر بشه اگر بخواید مثالشو بفرستم)
گرچ تاپیک قدیمی هست ولی اینو میگم واسه بقیه کسایی که ممکنه مثب من اولش تو حل این سوال به مشکل بر بخورند : یه جور دیگه هم به مسئله میشه نگاه کرد رد گزینه کنید گراف ۲ بخشی نیست پس گرینه الف رد میشه گراف چرخ یا دور هم نیست پس گزینه های ب و ج هم حذف میشه فقط گزینه د باقی می مونه که جواب درست هست