نظریه رمزی

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

قضیه رمزی (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) = ۱۷.

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

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