سوال مورد نظر پیوست شده است
جوابش رو گزینه ۲ زده.
ممنون از دوستان
سلام
تست جالبی است ولی میتوانیم به دور از چشم اساتید مانشت یواشکی با استفاده از یک نکته و به صورت حل تستی به سوال پاسخ دهیم. اینکه عدد رنگی (Chromatic) در محدوده ی بین ۱ و n است [tex]1\le\chi(G)\le n[/tex] که ۱ مثلا مربوط به زمانی است که گراف یال ندارد پس با یک رنگ می توانیم گراف را رنگ کنیم و n مثلا مربوط به وقتی است که گراف کامل است و ما نیاز به n رنگ یا همان تعداد راس ها نیاز داریم.پس با این اوصاف گزینه های ۳ و ۴ به راحتی رد می شوند.می مونه گزینه ی ۱ و ۲ ولی در سوال گفته شده که گراف دارای [tex]O(n)[/tex] یال است پس میتوانیم نتیجه بگیریم که گراف ما از کامل بودن تا حدود زیادی دور است چرا که گراف کامل دارای [tex]\theta(n^2)[/tex]یال است و این اختلاف زیاد باعث می شود ما از عدد رنگی حداکثری n تا حدود زیادی به سمت یک حرکت کنیم که تنها گزینه ۲ پیش روی ماست.البته بهتر بود طراح بیان می کرد که منظورش کدام نوع زنگ امیزی است راسی یا یالی و باز بهتر بود به جای [tex]O[/tex] از [tex]\theta[/tex] استفاده میکردچرا که تتا دارای خاصیت هم ارزی است و در ک ان در بیان مثلا گرافی چقدر یال دارد بهتر است.