آشنایی با نظریه گراف ها

در مورد نظریه گراف ها  کتاب های خیلی خوبی نوشته شده:

به نظرم یکی از بهترین کتاب های موجود کتاب آشنایی با نظریه گراف ها اثر وست است. کتاب وست یک اثر جامع است که ویرایش دومش برای 2002 است.

برای دانلود کتاب وست روی این لینک کلیک کنید.

کتاب دیگری که قبلا مورد  استفاده بود کتاب باندی و مورتی است. که البته در 2008 ورژن جدیدش را ارائه کردند.

کتاب قدیمی تر از آن هم کتاب ویلسون است.

دومینو بازی

صفحه شطرنجی 100*99 به دومینوها افراز شده است. می دانیم برای هر افراز دیگر صفحه شطرنجی به دومینوها ،دومینویی وجود دارد که در هر دو افراز مشترک است .ثابت کنید در افراز اولیه دو ستون متوالی می توان یافت که همه خانه های آن به دومینوهای افقی افراز شده باشد.

جدول مستطیلی

در هر خانه از یک جدول مستطیلی یک عدد طبیعی نوشته شده است. در هر مرحله می توان یک واحد از تمامی اعداد یک ستون کم کرده و یا تمام اعداد یک سطر را دو برابر کنیم. آیا همواره می توان تمام اعداد درون جدول را صفر کرد؟

اعداد روی تخته

اگر n یک عدد فرد باشد و اعداد 1 تا 2n بر روی تخته نوشته شده باشد. در هر مرحله دو تا از اعداد را انتخاب کرده و تفاضل آن ها را به جای آن دو عدد بر روی تخته می نویسیم.

آیا در نهایت می توان به عدد صفر رسید؟

اکسترمال 4

جزوه اکسترمال از سایت المپیاد رشد که ترجمه فصل سوم کتاب استراتژی های حل مسئله است. به همراه اصل کتاب در زیر آمده است:

جزوه اکسترمال المپیاد رشد

کتاب استراتژی های حل مسئه

جاده های خاکی

در یک استان 1000 شهر وجود دارد که بین هر دو شهری دقیقا یک مسیر خاکی وجود دارد. ثابت کنید دولت می تواند بعضی از جاده ها را آسفالت کند به طوری که به هر شهر فرد تا جاده آسفالت وصل باشد.

راه حل: 

اکسترمال 3

مثال 5 : رخ هایی روی صفحه شطرنج  قرار دارند. واضح است که  رخ کمترین تعداد رخی می باشد که تمام خانه های شطرنج  را تهدید می نماید. اما درباره  چه می توان گفت که بتوانند خانه های شطرنج   را تهدید کند. 

مثال 6 : در چهاروجهی با سه یال همرس می توان یک مثلث ساخت. 

مثال 7 :   مجموعه نقاطی از صفحه است. هر نقطه وسط دو نقطه دیگر است. ثابت کنید مجموعه ای نامحدود است.   

مثال 8 : هفت کوتوله دور یک میز دایره ای نشسته اند.در برابر هر یک از آنها، فنجانی قرار دارد.در برخی از فنجان ها شیر هست،روی هم 3 لیتر. یکی از کوتوله ها شیرش رابه طور یکسان میان دیگر فنجان ها قسمت می کند.در فرآیندی پاد ساعتگرد،هر یک از کوتوله ها به نوبت همان کار را انجام می دهند. بعد از آن که کوتوله ی هفتم شیرش را قسمت کرد،محتویات آغازین هر فنجان بازگردانده می شود.میزان آغازین شیر را در هر یک از فنجان ها بیابید.

مثال 9 : در یک پنج ضلعی محدب می توان سه قطر انتخاب کرد که اضلاع یک مثلث باشند 

مثال 10 : عدد های طبیعی را از 1 تا 64 روی خانه های یک صفحه شطرنج به ترتیب نوشته ایم.  (از 1 تا 8 را از چپ به راست در سطر اول و به همین ترتیب تا سطر هشتم.) قبل از تعداد از عدد ها علامت بعلاوه و قبل از بعضی علامت منها را طوری نوشته ایم که در هر سطر و هر ستون 2 تا بعلاوه و 4 تا منها وجود دارد. ثابت کنید مجموع عددهای نوشته شده برابر صفر است.

مثال 11 :  ثابت کنید تعداد رشته های باینری n تایی به طوری که هر دوتا حداقل در سه مکان متفاوت باشند حداکثر (1+2ⁿ) / (n) است .

مثال 12 :  سه مدرسه مفروض است که در هر یک از سه مدرسه n دانش آموز وجود دارد . هر دانش آموز جمعن n+1 دوست از دو مدرسه دیگر دارد . ثابت کنید می توانیم یک نفر از هر مدرسه انتخاب کنیم به طوری که این سه نفر دو به دو با هم دوست باشند .

مثال 13 :  9 شکل مسطحه داریم که مساحت هر کدام 1 است. آنها را طوری در صفحه قرار داده ایم که مساحت شکل حاصل 5 شده است.ثابت کنید 2 شکل وجود دارد که اشتراک مساحتشان بزرگتر یا مساوی 1/2 است.

مثال 14 : ماشینی در مسیر دایره ای قرار دارد.مقداری بنزین به طور ناهمگن در مسیر ریخته شده است.(ممکن است در نقطه هایی از مسیر اصلا بنزینی وجود نداشته باشد.)باک ماشین در ابتدا خالی است.ماشین از هر نقطه ای از مسیر عبور کند تمام بنزین آن نقطه را در باک خود جمع می کند.اگر کل بنزین ها را جمع کنیم دقیقا به اندازه ی یک دور ماشین است.ثابت کنید نقطه ای در مسیر وجود دارد که اگر از آن نقطه شروع به حرکت کند می تواند دقیقا 1 دور مسیر را بپیماید.

مثال 15:  ثابت کنید برای اعداد صحیح مثبت معادله زیر جواب ندارد. 

اصل اکسترمال 2

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

 به اصل های زیر دقت کنید:

الف.هر زیر مجموعه محدود  از اعداد صحیح یا حقیقی دارای یک عنصر مینیمم و یک عنصر ماکسیمم است . (اصل اکسترمال)
ب.هر زیرمجموعه غیر تهی از اعداد صحیح مثبت دارای کوچک ترین عضو است. این را « اصل خوش ترتیبی» می نامند . (حالت کلی تر اصل اکسترمال)
ج.مجموعه نامحدود از اعداد حقیقی ضرورتاً دارای عضو ماکسیمال یا مینیمال نیست. اگر از بالا کران دار باشد، آنگاه دارای کوچک ترین کران بالاست که آن را سوپریمم می نامیم. اگر از پایین کران دار باشد دارای بزرگترین کران پایین است و آن را اینفیمم می نامیم. (کلی تر از اصل خوش ترتیبی)

و هم چنین  اگر  باشد آنگاه و اگر  آنگاه .

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

چند مسئله:

مثال ۱ : ‏الف. خط حداکثر یک صفحه را به چند بخش تقسیم می کند؟ 

ب. با  صفحه در حالت کلی فضا به چند بخش تقسیم می گردد

مثال 2: ادامه بخش ب: فرض کنیم  نشان دهید در بین  بخش از فضا حداقل  چهاروجهی وجود دارد (). 

مثال 3 (مسئله سیلوستر) :  مجموعه محدود شامل نقاطی از صفحه‌است که هر خط گذرنده ازدو نقطه از نقطه ‏سومی می‌گذرد. ثابت کنید تمام نقاط روی یک خط واقع می‌باشند.‏

مثال 4 : ‏ در کشور اسکانیا هر شهری به شهر دیگر فقط بوسیله یک جاده یک طرفه وصل شده ‏است. ثابت کنید شهری وجود دارد که از هر شهری به آن مستقیم و یا حداکثر به ‏واسطه یک شهر دیگر می‌توان رسید. ‏

منبع: انگل، آرتور. استراتژی‌های حل مسئله، چاپ دوم . تهران: مبتکران ، ۱۳۸۴ 

اصل اکسترمال

اصل اکسترمال: هر مجموعه متناهی  یک ماکسیمم و مینیمم دارد .

البته این اصل بسیار ساده به نظر می رسد اما مثل اصل لانه کبوتری کاربرد های بسیاری دارد . معمولا در برهان خلف یکی از ماکسیمم یا مینیمم ها را انتخاب میکنند و ثابت میکنند اگر این طور باشد عددی کمتر از مینیمم یا بزرگتر ازماکسیمم وجود دارد .

 

تمرین 1:

جدولی نامتناهی به ما داده اند که از یک مجموعه متناهی از اعداد پر شده است و هر عدد میانگین 4 عدد مجاورش است ثابت کنید همه اعداد با هم برابر اند .

 

 

تمرین2 :

N  نقطه در یک صفحه واقعند به طوری که هر سه تا از آن نقاط مثلثی با مساحت کمتر مساوی 1 تشکیل میدهند . ثابت کنید همه آنها را میتوان در مثلثی با مساحت 4 جا داد .