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

تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

ارسال:
  

so@ پرسیده:

تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

سلام دوستان
ممنون میشم اگه کسی حل این سوالو میدونه منو راهنمایی کنه(کتاب پوران هیچ راه حلی توضیح نداده) پیشاپیش سپاسگذارمShy

فرض کنید گرافی ۲۱ راسی داریم ک ۱۹ راس درجه ۴ و ۲ راس درجه ۳ داریم.مینیمم تعداد رنگی که لازم باشد تا یالهای گراف را رنگ امیزی کنیم به طوری که هر دو یال متصل رنگهای متفاوتی داشته باشند برابر است با:
۱)۲
۲)۳
۳)۴
۴)۵
جواب گزینه ۴

من باشکل میکشم ۵ تا میشه ولی خیلی طول میکشه میخام ببینم راه حل دیگه ای هست ک ساده تر باشه
باتشکرHeart
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

newuser پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

سلام
مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱
پس با توجه به درجات رئوس گراف این عدد ۴ یا ۵ میشود.
گراف مورد نظر غیر دوبخشی است و مشخص کردن تعداد رنگ ها طولانی می شود. اما با توجه به این اصل که تعداد رنگ های تمام گراف های دو بخشی و اکثر گراف های تصادفی برابر ماکزیمم درجه گراف است. می توان نتیجه گرفت جواب ۵ است چون گراف این سوال اگر دو بخشی بود به ۴ رنگ نیاز داشت چون دو بخشی نیست پس ۵ رنگ نیاز دارد.
امیدوارم قابل فهم بوده باشه
نقل قول این ارسال در یک پاسخ

ارسال:
  

ldns0098 پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

(۲۶ آذر ۱۳۹۳ ۰۱:۴۷ ق.ظ)newuser نوشته شده توسط:  مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱

توضیح عالی بود.
در مورد فرمول "مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱" این فرمول برای کدوم دسته از گرافهاست؟ غیر دو بخشی ها؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

newuser پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

(۲۶ آذر ۱۳۹۳ ۰۹:۵۵ ق.ظ)ldns0098 نوشته شده توسط:  
(26 آذر ۱۳۹۳ ۰۱:۴۷ ق.ظ)newuser نوشته شده توسط:  مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱

توضیح عالی بود.
در مورد فرمول "مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱" این فرمول برای کدوم دسته از گرافهاست؟ غیر دو بخشی ها؟

این فرمول واسه حالت کلی
البته دو بخشی ها حالت خاص هستند که با دو رنگ میشه رنگ آمیزی کرد چون عدد فامی ۲ دارند
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

so@ پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

(۲۶ آذر ۱۳۹۳ ۰۱:۴۷ ق.ظ)newuser نوشته شده توسط:  سلام
مینیمم تعداد رنگ های لازم = ماکزیمم درجه گراف یا ماکزیمم درجه گراف+۱
پس با توجه به درجات رئوس گراف این عدد ۴ یا ۵ میشود.
گراف مورد نظر غیر دوبخشی است و مشخص کردن تعداد رنگ ها طولانی می شود. اما با توجه به این اصل که تعداد رنگ های تمام گراف های دو بخشی و اکثر گراف های تصادفی برابر ماکزیمم درجه گراف است. می توان نتیجه گرفت جواب ۵ است چون گراف این سوال اگر دو بخشی بود به ۴ رنگ نیاز داشت چون دو بخشی نیست پس ۵ رنگ نیاز دارد.
امیدوارم قابل فهم بوده باشه

سلام
ممنونم از پاسخت و راهنمایتون دیگه از این ک کسی ب این سوال من جواب بده نامید شده بودم و فراموشش کردم
واقعا تشکرSmile
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

so@ پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

یعنی کسی حل این سوالو نمیدونهSadSad
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

ldns0098 پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

من هم تو این سوال مشکل دارم. دوستان ممکنه راهنمایی کنین؟
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Densike پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

فرمولی که ذکر شد غلطه ، مینیمم رنگ مورد نیاز بین مینیمم درجه رئوس و ماکزیمم درجه رئوس + ۱ هست ( یعنی توی این بازه)
مثال نقض حرفتون هم گراف k1,5 که با ۲ رنگ ، میشه رنگش کرد ولی ماکزیمم درجه ۵ هست
در ضمن گراف ۲ بخشی با ۲ رنگ ، رنگ میشه نه ۴ رنگ
البته جواب این سوال همون ۵ هست ولی شما باید از اینجا میتونید بهش برسید : بدترین حالت اینه که ۱۹ تا گره یه جورایی شبیه درخت،باشند ، درختشو با ضریب انشعاب ۴ بکشید میبینید آخراش اینا مجبور میشن بهم وصل بشند و باعث میشه نشه با کمتر از ۵ تا رنگ کرد
نقل قول این ارسال در یک پاسخ

ارسال:
  

so@ پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

(۲۷ آذر ۱۳۹۳ ۰۸:۳۷ ق.ظ)Densike نوشته شده توسط:  فرمولی که ذکر شد غلطه ، مینیمم رنگ مورد نیاز بین مینیمم درجه رئوس و ماکزیمم درجه رئوس + ۱ هست ( یعنی توی این بازه)
مثال نقض حرفتون هم گراف k1,5 که با ۲ رنگ ، میشه رنگش کرد ولی ماکزیمم درجه ۵ هست
در ضمن گراف ۲ بخشی با ۲ رنگ ، رنگ میشه نه ۴ رنگ
البته جواب این سوال همون ۵ هست ولی شما باید از اینجا میتونید بهش برسید : بدترین حالت اینه که ۱۹ تا گره یه جورایی شبیه درخت،باشند ، درختشو با ضریب انشعاب ۴ بکشید میبینید آخراش اینا مجبور میشن بهم وصل بشند و باعث میشه نشه با کمتر از ۵ تا رنگ کرد
از توجه شماهم سپاسگذارم الان ک دارم ب توضیحات شما هم فکر میکنم میبینم مستدل تر
حالا انشالله دوستان دیگه هم نظر بدن تا ابهامات رفع بشه
HuhHuh
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۰
  

newuser پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

این استدلال که روش خاصی رو ذکر نکرده اومده رسمش کرده!!
گراف دو بخشی که بحثش جداست. اصلا گراف دو بخشی گرافیه که عدد فامی ۲ داشته باشه پس قطعا ۲ رو رنگ نیاز داره
شاید تو توضیحاتم اشتباه کردم گفتم "اگر دو بخشی بود با ۴ رنگ رنگ آمیزی میشد " فقط سهوا ۴ رو گفتم بهتر بود میگفتم اگر دو بخشی بود که عدد فامی ۲ داشت پس ۲ رنگ کافی بود. در واقع میخواستم حالات خاص رو حذف کنم وگرنه فرمول درسته
نقل قول این ارسال در یک پاسخ

ارسال: #۱۱
  

Densike پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

(۲۷ آذر ۱۳۹۳ ۱۱:۴۰ ق.ظ)newuser نوشته شده توسط:  این استدلال که روش خاصی رو ذکر نکرده اومده رسمش کرده!!
گراف دو بخشی که بحثش جداست. اصلا گراف دو بخشی گرافیه که عدد فامی ۲ داشته باشه پس قطعا ۲ رو رنگ نیاز داره
شاید تو توضیحاتم اشتباه کردم گفتم "اگر دو بخشی بود با ۴ رنگ رنگ آمیزی میشد " فقط سهوا ۴ رو گفتم بهتر بود میگفتم اگر دو بخشی بود که عدد فامی ۲ داشت پس ۲ رنگ کافی بود. در واقع میخواستم حالات خاص رو حذف کنم وگرنه فرمول درسته

میخواید واستون مثال نقض بفرستم؟ مثلا گراف چرخ ، ماکزیمم درجه n هست ولی با ۳ یا ۴ رنگ بسته زوج و فرد بودن تعداد راس ها میشه رنگش کرد ، این که دیگه ۲ بخشی هم نیست ّ
درستش اینه که تعداد رنگ مورد نیاز یه عددی هست تو بازه تعداد کلیک های گراف و ماکزیمم درجه + ۱ (حتی بعضی مواقع میتونه از مینیمم درجه هم کمتر بشه اگر بخواید مثالشو بفرستم)
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۲
  

hirkaniboy پاسخ داده:

RE: تست علوم کامپیوتر سال ۸۲ رنگ آمیزی گراف (سوال ۴۰ پوران ص ۲۴۳)

گرچ تاپیک قدیمی هست ولی اینو میگم واسه بقیه کسایی که ممکنه مثب من اولش تو حل این سوال به مشکل بر بخورند : یه جور دیگه هم به مسئله میشه نگاه کرد رد گزینه کنید گراف ۲ بخشی نیست پس گرینه الف رد میشه گراف چرخ یا دور هم نیست پس گزینه های ب و ج هم حذف میشه فقط گزینه د باقی می مونه که جواب درست هست
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  [دانلود]آزمون های آزمایشی مدرسان شریف -مهندسی کامپیوتر و ای تی-سال ۹۱(کنکور ۹۲) esisonic ۱۱ ۴۳,۷۶۸ ۱۸ آبان ۱۴۰۳ ۰۴:۳۹ ب.ظ
آخرین ارسال: farshchian2090
  جزوه برای درس نظریه علوم کامپیوتر matias ۱۳ ۱۵,۳۱۹ ۲۴ شهریور ۱۴۰۳ ۰۸:۳۳ ب.ظ
آخرین ارسال: shabankhah
  گرایش های علوم کامپیوتر alisaaa ۴ ۴,۳۸۱ ۱۳ آذر ۱۴۰۲ ۰۴:۲۷ ب.ظ
آخرین ارسال: hashemhamidi
  علوم کامپیوتر شریف یا نرم افزار تهران؟ ۴L1R3Z4 ۴۴ ۳۳,۲۵۷ ۰۶ شهریور ۱۴۰۲ ۰۸:۱۲ ب.ظ
آخرین ارسال: moeinbahari
  تست ۸۷ کامپیوتر مربوط به عامل ها Shekarchi_shab ۳ ۲,۵۹۶ ۲۰ بهمن ۱۴۰۱ ۰۷:۳۹ ب.ظ
آخرین ارسال: HamidReza1
  رتبه ۵۴ علوم کامپیوتر و ۷۶ ریاضی ارشد ۱۴۰۰ Computer92 ۰ ۲,۳۷۶ ۰۸ شهریور ۱۴۰۰ ۰۹:۴۶ ب.ظ
آخرین ارسال: Computer92
  اصطلاحات انگلیسی با رنگ‌ها آموزش زبان انگلیسی cyruskingsolomon ۰ ۱,۹۱۴ ۲۸ فروردین ۱۴۰۰ ۱۲:۳۰ ق.ظ
آخرین ارسال: cyruskingsolomon
  کارنامه نهایی ازمون دکتری داخل سال ۱۳۹۲-گرایش معماری کامپیوتر انرژی مثبت ۱ ۴,۵۱۳ ۱۷ بهمن ۱۳۹۹ ۰۲:۲۸ ق.ظ
آخرین ارسال: hmaryam567
  تشریح تست همروندی - بررسی یکی از سوالات سال ۸۲ abji22 ۵ ۵,۲۵۴ ۰۲ دى ۱۳۹۹ ۱۱:۰۵ ق.ظ
آخرین ارسال: mohammadasadi1
  بعد ۶ سال اومدم، ارشد مهندسی کامپیوتر کسی هست؟؟ seyed_eng ۷ ۶,۶۸۰ ۱۱ آبان ۱۳۹۹ ۰۷:۴۷ ق.ظ
آخرین ارسال: iraj.leo

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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