نظریه رمزی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

قضیه رمزی (ramsey) درباره رنگ‌آمیزی گراف هاست که در اینجا به حالت خاصی از آن اشاره می‌کنیم.

برای عددهای صحیح و دلخواه k و l کوچک‌ترین عدد صحیح (r(k,l وجود دارد به‌طوری‌که هر گراف با این تعداد گره دارای خوشه‌ای k گرهی یا شامل مجموعه مستقل l گرهی است.

نمونه[ویرایش]

برای نمونه

(r(x,۲)=x r(۱,x)=۱ ۱=r(x,1
r(۴٬۵) = ۲۵ r(۵٬۳) = ۱۴ r(۴٬۴) = ۱۸ r(۳٬۴) = ۹ r(۳٬۳) = ۶ عدد رمزی آخر در سال ۱۹۹۳ با استفاده از کامپیوتر بدست آمده.

تاریخچه[ویرایش]

این عددهای را برای اولین بار رمزی نام گذاری کرد وبعدها دانشمندان بزرگی چون گلیسون و گرینوودو اردوش بر روی آن‌ها وقضایای مربوطه کار کرده‌اند این عددهای فعلاً تجربی اند و جز در موارد خاص فرمولی برای آن‌ها نداریم. برای آشنایی بیشتر به قضیه زیر توجه کنید.

قضیه کران بالا[ویرایش]

در این جا می‌خواهیم کران بالایی برای عددهای رمزی (r(k,l بیان کنیم: اگر k>۱ , l>۱ آنگاه:

 (r(k,l) <= r(k,l-۱) + r(k-1,l

برهان:

فرض کنید g گرافی با (r(k,l-۱) + r(k-1,l گره باشد. گره v را در نظر بگیرید صبق اصل لانه کبوتری v یا به (r(k-1,l گره وصل است ویا به (r(k,l-۱ گره وصل نیست.

در صورتی که حالت اول بر قرار شود در این تعداد گره یا l گره مستقل اند ویا ۱-k گره خوشه‌اند و از آنجا که همه این رئوس به v وصل اند k-۱ گره به همراه k , v گره خوشه را تشکیل می‌دهند حکم مسئله ثابت می‌شود.

و اگر حالت دوم بر قرار شود یا k گره خوشه پیدا می‌شود یا l-۱ گره مستقل و از آنجا که v به این رئوس وصا نیست l-۱ گره و l,v گره مستقل را تشکیل می‌دهد؛ و حکم ثابت می‌شود.

بیان مسئله به صورت دیگر (حالت کلی)[ویرایش]

اگر q1,q2,... ,qn عددهای صحیح بزرگتر از ۲ باشند آنگاه عددی مانند (r(q1,q2,... ,qn وجود دارد به‌طوری‌که اگر p بزرگتر از (r(q1,q2,... ,qn باشد و یال‌های گراف را با n رنگ (رنگ‌های ۱ تا n) رنگ کنیم، به ازای حداقل یک رنگ مانند i زیر گراف کامل qi گرهی وجود دارد که یال‌هایش هم رنگ رنگ i ام است.

برای نمونه r(3,3,3) = ۱۷.

منابع[ویرایش]

  • استراتژی‌های حل مسئله/آرتور انگل/مترجمان آرش امینی… /نشر مبتکران/۱۳۸۲
  • نظریه گراف و کاربردهای آن/باندی و مورتی/ترجمه دارا معظمی/ویرایش علی عمیدی/مرکز نشر دانشگاهی/۱۳۸۴ چاپ ۳
  • ریاضیات انتخاب یا چگونه بدون شمارش بشماریم/ایوان نیون/مترجمان علی عمیدی و بتول جذبی/مرکز نشر پیش دانشگاهی/۱۳۸۶.