اصل اکسترمال

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

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

استفاده از اصل اکسترمال

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

• الف: هر مجموعه کراندار نامشخصی مثل A از اعداد صحیح یا حقیقی دارای یک عنصر می‌نیمال ${\displaystyle A}$ و یک عنصر ماکسیمال ${\displaystyle A}$ دارد که ضرورتاً یکتا نمی‌باشند.
• ب :هر زیر مجموعه غیر تهی از اعداد صحیح مثبت دارای کوچکترین عضو است. این را اصل خوش ترتیبی می‌نامند و هم ارز با اصل استقرای ریاضی است.
• ج: مجموعه بی‌کران ${\displaystyle A}$ از اعداد حقیقی ضرورتاً دارا عضو ماکسیمال یا مینیمال نیست. اگر ${\displaystyle A}$ از بالا کراندار باشد، آنگاه دارای کوچکترین کران بالاست که آن را سوپریموم ${\displaystyle A}$ می‌نامیم. اگر ${\displaystyle A}$ از پایین کراندار باشد دارای بزرگترین کران پایین است و آن را اینفیموم ${\displaystyle A}$می‌نامیم.

اگر ${\displaystyle SUPA\in A}$ باشد آنگاه ${\displaystyle SUP(A)=maxA}$و اگر ${\displaystyle infA\in A}$ آنگاه ${\displaystyle inf(A)=minA}$.

صفحه

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

حل : یک نفر مبتدی برای حل این مسئله از اینجا شروع می‌کند که ${\displaystyle p_{n+1}=g(p_{n})}$. در حقیقت با اضافه کردن یک خط به n خط به سادگی به دست می‌آید که ${\displaystyle p_{n+1}=p_{n}+n+1}$.

در واقع در این استدلال هیچ اشکالی نیست. چون رابطه بازگشتی پایه و اساس این شوره تفکر است، یک مسئله حل کن تجره گرا ممکن است مسئله را در ذهن خود حل نماید. ما به شماره کردن مسئله می‌پردازیم. یکی از اصول شمارش اساسی تناظر یک به یک برقرار کردن است.

اولین سؤال این است آیا می‌توان ${\displaystyle p_{n}}$ بخش از صفحه را به صورت یک به یک به مجموعه مربوط ساخت که به آسانی بتوان آن را شمرد؟

ترکیب ${\displaystyle \left({\begin{array}{cccccc}n\\2\end{array}}\right)}$ نقطه برخورد n خط را به آسانی می‌توان یافت. اما پایین برخورد دقیقاً در یک بخش وجود دارد (اصل اکسترمال) بنابراین ${\displaystyle \left({\begin{array}{cccccc}n\\2\end{array}}\right)}$ بخش را با یک نقطه اشتراک داریم، بخش‌ها بدون نقاط اشتراک در کران پایین واقع نمی‌شود، و بک خط افقی را به n+۱ قسمت تقسیم می‌کند. این بخش‌ها را می‌توان به‌طور منحصربه‌فرد به این نقطه خط‌ها نسبت داد؛ بنابراین ${\displaystyle n+1}$ یا ${\displaystyle \left({\begin{array}{cccccc}n\\1\end{array}}\right)+\left({\begin{array}{cccccc}n\\0\end{array}}\right)}$ قسمت بدون یک نقطه اشتراک وجود دارد؛ بنابراین در مجموع داریم:

${\displaystyle p_{n}=\left({\begin{array}{cccccc}n\\2\end{array}}\right)+\left({\begin{array}{cccccc}n\\1\end{array}}\right)+\left({\begin{array}{cccccc}n\\0\end{array}}\right)}$

مسئله سیلوستر

مثال ۲: این مسئله به وسیله سیلوستر در سال ۱۸۹۳ طرح شد و در سال ۱۹۳۳ توسط گالی به روش پیچیده‌ای حل گردید و سپس در سال ۱۹۴۸ درچند خط با اصل اکسترمال توسط کلی حل گردیده‌است. مجموعه محدود شامل نقاطی از صفحه‌است که هر خط گذرنده ازدو نقطه از نقطه سومی می‌گذرد. ثابت کنید تمام نقاط روی یک خط واقع می‌باشند.

حل: فرض کنیم این نقاط هم خط نیستند. زوج (P,L (عبارت است از خطی مانند${\displaystyle L}$ و نقطه‌ای مانند ${\displaystyle P}$ غیر واقع بر ${\displaystyle L}$. حال نقطه‌ای را در نطر می‌گیریم که فاصله اش از خط می‌نیمم باشد. فرض کنیم ${\displaystyle f}$ پای عمودی است که از نقطه ${\displaystyle P}$ بر خط${\displaystyle L}$ وارد شده‌است؛ بنابراین بنا به فرض حداقل سه نقطه ${\displaystyle a,b,c}$ بر خط قرار دارد. فرض کنیم دو نقطه ${\displaystyle a}$ و${\displaystyle b}$ در یک طرف ${\displaystyle f}$ واقع باشند؛ و فرض کنیم b بهf تاa نزدیکتر باشد آنگاه فاصله b تا ap کمتر از d می‌باشد و این تناقض است.

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

حل : فرض کنیم ${\displaystyle m}$ حداکثر جاده‌های منتهی به یک شهر باشد؛ و فرض کنیم ${\displaystyle M}$ شهری باشد که حداکثر جاده‌ها به آن وصل شده باشد. فرض کنیم ${\displaystyle D}$ مجموعه ${\displaystyle m}$شهری باشد که به ${\displaystyle M}$ متصل هستند و فرض کنیم ${\displaystyle R}$ مجموعه تمام شهرهای نامتصل به ${\displaystyle M}$ و موجود در ${\displaystyle D}$ باشد.

اگر R تهی باشد حکم ثابت است. اگر ${\displaystyle X\in R}$ باشد شهری مانند ${\displaystyle E\in D}$ وجود دارد که از طریق آن می‌توان به M رسید یعنی X → M → E. اگر چنین ${\displaystyle E}$ وجود نداشته باشد، پس به شهر${\displaystyle X}$ می‌توان از طریق شهرهای‌${\displaystyle D}$ و از ${\displaystyle M}$ رسید؛ بنابراین ${\displaystyle m+1}$ جاده به ${\displaystyle X}$ منتهی می‌شود که یک تناقض نسبت به فرض در مورد ${\displaystyle M}$ است؛ بنابراین به هر شهر به‌طور حداکثر به حالت حکم مسئله می‌توان رسید.

منابع

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

پیوندها

• مسائل اکسترمال در پیچیدگی و آنالیزهای حقیقی‌
• الگوریتم هندسی، دایرهای اکسترمال‌
• ترکیب‌شناسی اکسترمال‌
• تئوری گراف اکسترمال‌
• کارگاه پیرامون گرافهای اکسترمال