نظریه رمزی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
ابرابزار |
|||
خط ۱:
▲این مسئله در باره رنگ آمیزی [[گراف]] هاست که در اینجا به حالت خاصی از آن اشاره میکنیم.
برای عددهای صحیح و دلخواه k و l کوچک‌ترین عدد صحیح (r(k,l وجود دارد به طوری که هر گراف با این تعداد گره دارای خوشه‌ای k گرهی و یا شامل مجموعه مستقل l گرهی است.
=== نمونه ===
برای نمونه
=== تاریخچه ===
این عددهای را برای اولین بار رمزی نام گذاری کرد وبعدها دانشمندان بزرگی چون گلیسون و گرینوودو اردوش بر روی آن‌ها وقضایای مربوطه کار کرده‌اند
سطر ۱۳ ⟵ ۱۴:
=== قضیه کران بالا ===
در این جا
اگر k>۱ , l>۱ آنگاه:
برهان:
فرض کنید g گرافی با (r(k,l-۱) + r(k-
گره v را در نظر بگیرید صبق [[اصل لانه کبوتری]] v یا به (r(k-
در صورتی که حالت اول بر قرار شود در این تعداد گره یا l گره مستقل اند ویا ۱-k گره خوشه‌اند واز آنجا که همه این رئوس به v وصل اند k-۱ گره به همراه k , v گره خوشه را تشکیل می‌دهند حکم مسئله ثابت می‌شود.
و اگر حالت دوم بر قرار شود یا k گره خوشه پیدا می‌شود و یا l-۱ گره مستقل و از آنجا که v به این رئوس وصا نیست l-۱ گره و l,v گره مستقل را تشکیل می‌دهد؛ و حکم ثابت می‌شود.
=== بیان مسئله به صورت دیگر (حالت کلی) ===▼
اگر q1,q2,... ,qn عددهای صحیح بزرگتر از
▲=== بیان مسئله به صورت دیگر(حالت کلی) ===
▲اگر q1,q2,...,qn عددهای صحیح بزرگتر از 2 باشند آنگاه عددی مانند (r(q1,q2,...,qn وجود دارد به طوری که اگر p بزرگتر از (r(q1,q2,...,qn باشد و یال‌های گراف را با n رنگ (رنگ‌های 1 تا n) رنگ کنیم، به ازای حداقل یک رنگ مانند i زیر گراف کامل qi گرهی وجود دارد که یال هایش هم رنگ رنگ i ام است.
== منابع ==
▲برای نمونه r(3,3,3) = 17.
▲* استراتژی‌های حل مسئله/آرتور انگل/مترجمان آرش امینی.../نشر مبتکران/۱۳۸۲
* نظریه گراف و کاربردهای آن/باندی و مورتی/ترجمه دارا معظمی/ویرایش علی عمیدی/مرکز نشر دانشگاهی/۱۳۸۴ چاپ ۳
* ریاضیات انتخاب یا چگونه بدون شمارش بشماریم/ایوان نیون/مترجمان علی عمیدی و بتول جذبی/مرکز نشر پیش دانشگاهی/
[[رده:نظریه رمزی]]
| |||