دانلود تحقیق ریاضیات گسسته

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

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

توفیق مفاهیم لازم برای بررسی این مسائل به کار گیری منطق ریاضی و نظریه مجموعه ها را اجتناب ناپذیر ساخته است.

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

ریاضیات گسسته مقدماتی متنی فشرده برابر یک دوره ریاضیات گسسته در سطحی مقدماتی برای دانشجویان کارشناسی علوم کامپیوتر و ریاضیات است.

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

جایگاه و ضرورت آموزش ریاضیات گسسته در نظام جدید دبیرستانی
در جریان تغییر نظام آموزش دوره های کارشناسی ریاضی در سالهای اخیر در دانشگاهها و موسسات آموزش عالی شاهد بودیم که درسهای جدید به تنا سب گرایشهای این رشته جایگزین درسهایی از نظام قبلی شدند.

درس ریا ضیات گسسته نیز به ارزش 4 واحد درسی در این راستا بعنوان یکی از واحدهای پایه همه گرایشهای دوره کارشناسی ریاضی در نظر گرفته شده است.

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

می باشیم.

همچنین در دوره پیش دانشگاهی نیز درسی جداگانه تحت عنوان ریاضیات گسسته در نظر گرفته شده است.

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

مطالبی که در این قسمت از بحث طرح خواهد شد بیشتر بر اساس مقاله ای است که تحت عنوان »آموزش ریاضی گسسته در دوره دبیرستان« توسط پروفسور آ.کاتلین
در مجله بین المللی ریاضیات، علم و تکنولوژی 1990 درج شده است.

» انقلاب کامپیوتری، ریاضیات گسسته را همانند حساب دیفرانسیل و انتگرال برای علم و تکنولوژی ضروری ساخته است.«

محتوای کلی ریاضیات گسسته
محتوای دقیق یک دوره ریاضیات گسسته هنوز تا حدودی به طور مبهم باقیمانده است، زیرا هم کتابهایی که تاکنون در این زمینه به رشته تحریر در آمده و هم برنامه های درسی که در این مورد از سوی برنامه ریزان مباحث درسی ریاضی تهیه وتنظیم می شود، دقیقاَ نتوانسته اند موضوعات و قلمرو مباحث این درس را مشخص نمایند.

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

با این حال می توان گفت که ریاضیات گسسته شامل مباحثی است که مراحل مربوط به تغییرات گسسته و کمیتهای گسسته را توصیف می کند، در مقابل کالکوس که مراحل تغییرات به طور پیوسته را دنبال می کند پس به طور دقیق می توان گفت که ریاضیات گسسته کالکوس( حسابان) نیست.

محتوای دقیق یک دوره ریاضیات گسسته هنوز تا حدودی به طور مبهم باقیمانده است، زیرا هم کتابهایی که تاکنون در این زمینه به رشته تحریر در آمده و هم برنامه های درسی که در این مورد از سوی برنامه ریزان مباحث درسی ریاضی تهیه وتنظیم می شود، دقیقاَ نتوانسته اند موضوعات و قلمرو مباحث این درس را مشخص نمایند.

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

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

اعداد حقیقی، پایه همه ریا ضیاتی هستند که مانند حساب دیفرانسیل و انتگرال با خواص توابع پیوسته سر و کار دارند.

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

می دانیم که سیستم های فیزیکی از تعداد زیادی ذرات گسسته – اتمها و مولکولها – تشکیل شده است، در عمل پیوسته فرض کردن ماده فرض بسیار مناسب و دقیقی است.

این سبب می شوند که اکثر پدیده ها ی طبیعی سیستمهای فیزیکی که از طریق حساب دیفرانسیل و انتگرال مدل سازی می شوند نوعاَ به صورت معادلات دیفرانسیل درآیند.

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

این آغاز شکوفایی آنالیز عددی بود نمونه متعارف از مسائلی که با استفاده از تکنیکهای آنالیز عددی حل می شوند این است که فرمول بندی یک مساله فیزیکی را با استفاده از حساب دیفرانسیل و انتگرال در نظر بگیریم و سپس آن را به شکل گسسته تبدیل کنیم تا با روشهای عددی قابل حل باشد.

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

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

آنالیز عددی با وجود کار بردهای وسیع، آن موضوعی تخصصی است نمی تواند تأثیر چشمکیری بر روند دآموزشی ریاضیات بگذارد هر چند آنالیز عددی مهمترین محل تلاقی ریاضیات پیوسته گسسته است امروزه تنها یک جزء کوچک از کار بردهای ریاضیات گسسته را در‌بر‌می‌گیرد.

محرک حقیقی برای رشد ریاضیات گسسته خود علوم کامپیوتری و همچنین نیازهای سایر رشته ها مانند اقتصاد ، پزشکی، زیست شناسی، علوم اجتماعی و...

بوده است.

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

چنانچه قبلانیز اشاره شد باید توجه کرد که ریا ضیات گسسته و پیوسته وجه تمایز قاطعی ندارند بعضی از شاخه های ریاضیات، شامل عناصری از هر دونوع گسسته و پیوسته هستند.

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

اما شاخه هایی از ریاضیات گسسته که در زیر مورد بحث قرار خواهیم داد گستره گوناگونی از کاربردهای عملی را در بر خواهند داشت.

همچنین تذکر این نکته ضروری است که از نظر آموزشی بهتر است ریاضیات گسسته و پیوسته به همراه همدیگر تعلیم داده شوند.

مرور تاریخی مباحث مهم ریاضیات گسسته: تجزیه مسائل به اجزایی که برای حل به فرمولهای همانند یا متفاوتی نیاز دارند بینشی کلیدی در پهنه های ریاضیات گسسته و ترکیباتی فراهم کرد این چیزی شبیه به روش از بالا به پایین برای بسط الگوریتمها در زبان ساخت یا فته ای نظیر زبان پاسکال است.

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

مفهوم جایگشت را می توان در اثر عبری( کتاب آفرنش) دستخوشی عرفانی که در زمانی بین 200تا600 سال قبل از میلاد نوشته شده است یافت .

اما حتی قبل از آن جالب است که بگوئیم قضیه ای از خنوکراتس اهل جالسدون(396-314 قبل از میلاد) در دست است که احتمالاَممکن است شامل » اولین تلاش در ثبت حل مسأله ای مشکل در جایگشتها و ترکیبها باشد.« اولین فن حدس زدن (Ars Conjectandi) نوشته یاکوب برنولی(1654-1705 ) نخستین کتاب درسی است که پاره ای از مطالب این بحث را مورد بررسی قرار داده است این کتاب در سال 1731 پس از مرگ برنولی منتشر شد و شامل چاپ تازه اولین رساله رسمی درباره احتمال است که در 1675 کریستیان هوینگس نوشته است.

در 1837 پترگوستاف لوژون دیریکله (1805-1859) فرمولبندی دقیقتری را از مفاهیم متغیر، تابع، و تناظر بین متغیر مستقلx ومتغیر وابسته y ، وقتی پی ریزی کرد کاردیله بر بستگی بین دو مجموعه از اعداد تأکید داشت و منربوط به وجود فرمول یا عبارتی که دو مجموعه را به هم مربوط کند بشود.

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

دیرکله علاوه بر کار اساس اش درباره تعریف تابع در ریاضیات کاربردی و در نظریه اعداد نیز کاملاَ فعال بوددر همین جا بود که نیاز به اصل لانه کبوتررا که اغلب به آن اصل کشوی دیریکله هم می گویند دریافت.

اعدا استرلینگ به ا فتخار جیمز استرلینگ(1692-1770) که در بسط تابعهای مولد پیشگام بوده است، به این نام خوانده شده اند.

اصل شمول و عدم شمول تاریخچه جالبی دارد که در نوشته های مختلف تحت نامهایی نظیر » روش غربال« یا » ا صل رده بندی حذ فی« وجود دارد یک صورت نظریه مجموعه ای این اصل که با اجتماعها و اشتراکها سر وکار دارد در اصول شانسها (1718) کتابی درسی درباره نظریه احتمال اثر آبرام دمواورآمده است کمی پیشتر از آن در1713 پی ریمون دمونموراندیشه زیر بنایی این اصل را در حل مسأله‌ای که عموماَ به مسأله پریشیها معروف است به کار برد.

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

نظریه گراف یکی از شاخه های مهم ریاضیات در حالتی گسترده با موضوعات مختلف نظریه گراف می باشد .

نظریه گراف یکی از کاربردی ترین شاخه های ریاضیات گسسته است یکی از محبوبترین و پربارترین شاخه های ریاضیات و علوم کامپیوتری است.

یکی از دلایل مهم این علاقه به نظریه گرا فها در قابلیت کاربرد آن در بسیاری از مسایل پیچیده و گسترده جامعه مدرن در زمینه های گوناگون نظیر ا قتصاد، توزیع، خدمات، مدیریت، بازاریابی ، مدلسازی انرژی، انتقال اطلاعات و برنامه‌ریزی حمل و نقل نهفته است، از این جهت نظریه گرافها را نخست و قبل از همه به عنوان ابزاری برای فرمولبندی مسائل و تعریف روابط متقابل ساختاری به کار می گیرند.رشته نظریه گرافها دارای دوشاخه متفاوت است 1- جنبه های جبری 2- جنبه های بهینه سازی مسأله پل کونیگسبرگ: نخستین مطلب منتشر شده درباره نظریه گرا فها از لئونهارت اویلرسوئیسی در 1736 بود مقاله او راه حل را برای مسئله ای که بنام مسئله بل کونیکسبرگ مشهور است ارائه می کردشهر کونیکسبرگ در روسیه که در کنار رود پرگل واقع شده است از شاخص شمالی(N) ساحل جنوبی (S )جزیره غربی(W) و جزیره شرقی(E) تشکیل شده است.

ارتباط بین این چهار قسمت به وسیله هفت پل برقرار می شد.دوپل بینN وW دوپل بین S وW و یک پل ازE به هر یک ازNوS وW (مطابق شکل)مسئله ای که اویلر مطرح کرد این بود که »آیا امکان دارد از جایی در شهر شروع به حرکت کرد و پس از پیمودن هر پل دقیقاَیکبار به نقطه شروع بازگشت یا نه؟« اگر هر قسمت شهر بعنوان یک رأس و هر پل بعنوان یک یا ل تلقی شود.

گراف با چهار رأس، هفت بال داریم که مدلسازی مسئله نامبرده را به زبان گرافها به دست می دهد که می توان مسئله را به این شرح بیان کرد: گرافی (نه لزوماَ ساده) مفروض است، آیا امکان دارد کل نمودار این گراف را چنان پیمود که از روی هر بال بیش از یک بار عبور بکنیم؟

اویلر به آسانی ثابت کرد که در مورد مسئله بل کونیکسبرگ پاسخ منفی است.

- طریقه نمایش گراف نقاطP ،Q ،R ،S ،T ،رئوس(Vertices )و خطوطی که رئوس را با هم وصل می کند ضلع (e d g e )نامیده می شودتوجه داریم که محل تلاقی QT وPS یک رأس نیست این دیاگرام را یک گراف(g r a p h ) می نامیم.

درجه (d e g r e e )یک رأس A در یک گراف ، برابر تعداد اضلاعی است که رأس A نقطه انتهایی آنها می باشد.لذا درجه Q برابر با4 است.

یک گراف را می توان به طرق مختلف نمایش داد مثلاَمی توانستیم ضلع S وP را خارج ا ز مستطیل رسم کنیم چون گرافی را که می سازیم مشخص مجموعه ای از نقاط و راههایی است که آنها را به هم وصل می کند خواص متریک در آنها صادق نیستند لذا از این دیدگاه هردو گرافی که دارای یک ساختار باشند، نمایانگر یک گراف خواهند بود مانند شکلهای(الف و ب).

یالها ممکن است بدون جهت باشندیا جهت داشته باشند که در حالت اخیر آن را گراف جهت دار یا دی گراف می نامیم.

گراف هامیلتونی ریاضیدان شهیر ایرلندی سر ویلیام هامیلتون (1805-1865) است که وجود جوابی برای بازی » دوددینا« را مورد پژوهش قرار داد.دراین بازی از یازیکن خواسته می شود که راهی در امتداد یالهایی یک دوازده وجهی ( یک چند وجهی منظم با20 رأس،80 یال و12 وجه) چنان بیابد که از هررأس دقیقاَ یک بار بگذرد و سپس به رأس شروع حرکت باز گردد بدین سان این بازی دارای جواب است اگر فقط G یک گراف هامیلتونی باشد.

تعریف: مسیری بین هر دو رأس گراف که از هر رأس دقیقاَیک بار بگذرد.مسیرها میلتونی گویند .

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

گرافی را گراف هامیلتونی گویند هرگاه دور هامیلتون داشته باشد.

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

نقشه ای با 48 ایالت همجوار را در نظر بگیرید مسأله این است که کمترین تعداد رنگهایی که لازم است تا نقشه را چنان رنگ آمیزی کنیم که هیچ دو ناحیه هم مرز(که در بیش از یک نقطه هم مرزند و ناحیه یک تکه اند) رنگ مشابهی نداشته باشندد چند تاست؟

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

قضیه چهار رنگ بیان می دارد که برای رنگ آمیزی هر نقشه ای که بتواند آن را بر روی کاغذ رسم کرد، چهار رنگ کافی است این مسأله برای اولین بار در نیمه اول قرن نوزدهم مطرح شد و تنها حدود بیست سال قبل 977 با استفاده از نظریه گراف قضیه های فراوان و 1200 ساعت از وقت یکی از سریعترین کامپیوترهای زمان توسط دو ریاضیدان به نامهای کنت اپل و ولگانگ هیکن در دانشگاه ایلی نویز حل شد چگونه قضیه چهار رنگ به صورت قضیه ای در نظریه گراف مطرح می گردد؟

اگر به جای هر یک از نواحی نقشه، یک رأس در نظر بگیریم و سپس فقط رأسهای مربوط به نواحی هم مرز زا به یکدیگر وصل کنیم نقشه مورد نظر تبدیل به یک گراف می شودگراف حاصل با نقشه مورد نظر متناظر است.

اپل و هیکن با استفاده از یک کامپیوتر سریع به بررسی تعداد زیادی از حالتهای ممکن که پیش از آن از طریق تحلیل ریاضی نشان داده شده بود که بررسی آنها برای اثبات قضیه کفایت می کند پرداختند و به این ترتیب قضیه را ثابت کردند بنابر این مسأله ای که بیش از نیم قرن در مقابل حمله تعدادی از برگترین ریاضیدانهای زمان مقاومت کرده بود، در برابر یک تحلیل کامپیوتری که بر پایه پیشرفتهای ریاضی نظریه گراف بنا شده بوداز پای در امد.می دانیم که عدد کروماتیک (رنگی )یک گراف عبارت است از مینیمم (Minimom ) تعداد رنگی که بتوان رئوس گراف را رنگ زد، طوری که دو رأس همجوار دارای رنگهای یکسان نباشند.

بنابر این عدد 4 عدد رنگی گرافی است که متناظر با نقشهای است که برای نثال 48 ایالت دارد که به وسیله عملیات جبری محاسبه می شود.

یکی از مسائل مهم و عمده در نظریه گراف و مسائلی که از مدل سازی ریاضی سیستمهای فیزیکی اقتصادی، اجتماعی، زیستی و...

پدید می آیند پیدا کردن عدد رنگی یک گراف می باشد این موضوع برای گرا فهای با تعداد اضلاع و رئوس متناهی پایین ( برای نثال با تعداد رئوس 4و5و…)به سادگی برای انواع گرا فها محاسبه می‌شود ولی وقتی تعداد رئوس یا اضلاع بیشتر و یامتناهی باشداز مسائل پیشرفته و پیچیده این نظریه می باشد.

یک روش جالب در این مورد که از مفاهیم مربوط به نظریه حلقه ها استفاده کرده و ارتباطی بین نظریه گراف و نظریه حلقه ها در جبر ایجاد کرده است مبتنی بر مقاله ای است با عنوان» رنگ کردنن حلقه های جابجایی« توسط استوان بک (Istvan Bek ) می باشد که موضوع پایان‌نامه تحصیلی در دوره کارشناسی ارشد استاد ارجممند دکترمحمد‌جهانشاهی نیز بوده است.

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

مسائلی ازنظریه گراف: نظریه گراف شاخه ای از ریاضیات گسسته است ک برای حل و فرموله کردن بسیاری از مسائل اجتماعی از قبیل حمل ونقل، ترا فیک در شهرها، آلودگی، سرویسهای شهری ژنتیکی، مسائل پلیسی و مسائل مهندسی از قبیل انرژی و مدارهای الکتریکی، مهندسی شیمی و…با کار می رود نمی توان ادعا کرد که نظریه گراف به تنهایی قادر به حل این مسائل است و یا بدون نظری گراف حل این مسا ئل غیرممکن است بلکه این نظریه وسیله ای برای فرموله کردن این مسائل است.

اغلب فرموله کردن دقیق مسأله به ما مشان می دهد که چرا مسأله دشوار است؟و برای حل آن چگونه باید داده ها ی مسأله ر برای بازکردن موجود در مسأله، تنظیم و سازماندهی کرد بنابراین گاهی وقتها نظریه گراف مسأله را حل می کند و یا دست کم به ما این بصیرت را می دهد که چگونه از امکانات موجود برای رسیدن به هدف خاصی استفاده کنیم.

1- اگر تعداد روشهای مختلف رنگ کردن رئوس گراف G را با رنگ مختلف نشان دهد طوری که در هر روش هیچ دو رأس همجوار دارای رنگ یکسان نباشد در مورد هر یک از گرافها ی زیر عبارتی تحلیلی برای بیان بر حسب K پیدا کنید.

حل: در مورد (الف) ملاحظه می کنیم که اگر نقطه میانی به K طریق رنگ شود آن گاه نقطه های انتهایی به طریق رنگ خواهند شد لذا برای عبارت است از: در مورد (ب) ملاحظه می کنیم که شبیه حالت (الف)،می تواند به صورت و بالاخره در مورد (ج) اگر یکی از رئوس به K طریق رنگ شود رأس دیگر به طریق و رأس سوم بهطریق رنگ خواهد شدلذا برابر است با : همین طور برای چنین گرافی باn رأس داریم: ملاحظه می کنیم که در مورد گرا فها ی(الف)و(ب)حداقل مقدارk برابر 2و در مورد گراف (ج) حداقل مقدار k برابر 3 می باشد.

کمترین مقدار ممکن k را با شرایط فوق عدد رنگی گرافG می نامیم و با(G)X نشان می دهیم.

2- می خواهیم با هفت دبیر دبیرستانی پنج کمیته آموزش، پژوهش، ورزش، هنرو کتابخانه چنان تشکیل دهیم که برخی از دبیران بتوانند در بیش از یک کمیته عضویت داشته باشند اگر هر کمیته موظف باشد که جلسه ای یک ساعته با حضور تمام اعضای خودتشکیل دهد .زمان لازم برای این که تمام کمیته ها بتوانند وظایف خود را انجام دهند چقدر باید باشد؟

حل: فرض کنیم دبیران با a وکمیته ها بانشان داده شوند همچنین اعضای کمیته ها به صورت زیر مشخص شده باشند.

عضوکمیته هستند .

عضو کمیته هستند.

عضو کمیتههستند.

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

با توجه به مسأله (1) ملاحظه میکنیم که عدد رنگی این گراف 3 است یعنی با سه ساعت متوالی تمام کمیته ها می توانند جلسه های خود را برگزار کند و با کمتر از سه ساعت این کار عملی نیست زیرا جلسات سه کمیته و وبه دلیل این که اعضای مشترک دارند به سه ساعت متفاوت نیاز دارند بدیهی است که بیشتر از 3ساعت نیز امکان پذیر است ولی به خواست مسأله پاسخ دقیق مسأله درست سه ساعت است.

رابطه های بازگشتی ومعادلات تفاضلی معادلات دیفرانسیل به عنوان اولین مولود زیبای حساب دیفرانسیل و انتگرال (ریاضیات پیوسته نامیده می شوند چنانکه می دانیم هدف ازحل یک معادله دیفرانسیل معمولی(بامشتقات نسبی در حقیقت پیذا کردن یک تابع حقیقی(یاتابع چند متغیره حقیقی)می باشد، که در معادله دیفرانسیل و در شرطهای داده شده اضافی صدق کند بنابر این مجهول یک معادله دیفرانسیل همواره یک تابع می باشد.همتای معادلات دیفرانسیل در ریاضیات گسسته، معادلات تفاضلی است و هدف از حل یک معادله تفاضلی پیدا کردن یک تابع گسسته (در حقیقت یک دنباله) است که بر مجموعه اعداد طبیعی تعریف شده است.

بنا بر ماهیت معادله تفاضلی دنباله جواب به صورت بازگشتی محاسبه می‌شودیعنی هر جمله با جمله ما قبل خود محاسبه می شود.برای مثال در معادله تفاضلی: (1) اگر معلوم باشد به راحتی محاسبه می شود.

مرتبه یک معادله تفاضلی، تفاضل بزرگترین .و کوچکترین اندیسK در نعادله می‌باشد.

برای مثال مرتبه معادله (1)یک است.

مشابهت بسیاری بین نظریه معادلات دیفرانسیل و نظریه معادلات تفاضلی وجود دارد نونه های زیر می تواند بیانگر این مشابهت باشند.

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

همچنین معادله مرتبه دوم نیز دارای دو جواب عمومی است که با شروط معین می گردد.

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

همانند اصل انطباق در نظریه معادلات دیفرانسیل (هر ترکیب خطی از جوابهای یک معادله همگن خطی همچنان جواب معادله مزبور است).

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

که در ان و به ترتیب مدول و آرگومان ریشه های و مختلط می باشد.

که مشابهت با جوابهای معادله دیفرانسیل آشکار است.

مثال1- معادله تفاضلی را در نظر می گیریم که معادله مشخصه آن می باشد ریشه های معادله مشخصه است ، بنا بر این: جوابهای معادله می باشند و این شگفت انگیز است که جوابهای معادله دیفرانسیل مرتبه دوم نیز به صورت می باشدکه در آن و ثابتهای اخباری هستند.

مثال2-معادله تفاضلی زیر را در نظر می گیریم که به عنوان مدلی برای وضعیتی که مبلغ p با نرخ بهره سالانه ثابت r پس انداز شده ،به کار می رود.

در این صورت اگر مقدارپس انداز از k سال باشد: (2) شرط اولیه شرط اولیه می باشد و جواب معادله (2) به صورت دنباله زیر داده می‌شود.

(3) اکنون حالت پیوسته این مسأله را با معادلات دیفرانسیل بحث می کنیم: فرض کنیم که مبلغمبلغ پولی با نرخ بهره r به بانک سپرده شده است مقدار سرمایه (t)s بعد از مدت t سال بستگی به تعداد دفعاتی دارد که بهره به آن اضافه شده است، اگر بهره یک بار در سال به سرمایه اضافه شود آن گاه: (4) ) با استفاده از معادله تفاضلی (3) نوشته شده است.) اگر بهره دوبار شش ماه به شش ماه در سال به سرمایه اضافه شود آنگاه: (5) s و اگر بهره به طور ماهانه به سرمایه اولیه اضافه شود، آنگاه : و به طور کلی اگر بهره m را در سال به سرمایه ا ضافه شود آنگاه: (6) اکنون این وضعیت را با یک مدل راضی با فرض آن که » بهره به طور پیوسته « به سرمایه اضافه می شود تقریب می زنیم.

بااین فرض که میزان رشد سرمایه متناسب است با سرمایه اولیه، خواهم داشت: (که درآن Iضریب تناسب می باشد.) در می آید که جواب این معادله همراه با شرط اولیه عبارت است از: (7) ملاحظه میشود که اگر طرف دوم رابطه(6) به طرف دوم رابطه (7) میلخواهد کردو جواب مسأله در حالت گسسته و پیوسته بر هم منطبق خواهد شد(وقتی که).

همانطور که می دانیم در عمل فقط امکان در نظر گرفتن وجود دارد و مناسب تر است که در حالت گسسته مسأله استفاده شود.

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

برای محاسبه آن اغلب لازم است که اول معادلات دیفرانسیل را به وسیله معادلات تفاضلی تقریب بزنیم و سپس محاسبه را انجام دهیم بر عکس بعضی وقتها نیز مدل ریاضی مسأله به صورت معادلات تفاضلی با ضرایب شامل متغیر و یا به صورت معادلات تفاضلی غیر خطی در می آیند که چنین شراطی به دلیل فقدان نظر به وجود حا معادلات تفاضلی غیر خطی و با ضرایب متغیر و نحوه محاسبه حل آنها، عموماَ مشکل و از مسائل حل نشده هستند.

مناسب ترین روش همان است که سیستم گسسته را با یک مدل پیوسته( معادله دیفرانسیل) مدلسازی کنیم و با حل معادله دیفرانسیل غیر خطی به جواب مسأله برسیم، سپس از روی فرمول جواب، مقادیر مربوط به زمانهای گسسته را مثل( روز، ماه، سال و ….) که مطلوب مسأله می‌باشند پیدا کنیم یکی از این روشها، روش تکرار پیکار می باشد که در مثال زیر توضیح داده شده استبرای مسأله مقدار اولیه: شرط اولیه می خواهیم جواب تقریبی محاسبه کنیم می دانیم که این مسأله با معادله انتگرال زیر هم ارز است: که از این معادله استفاده کرده دنباله تقریبات متوالی را به صورت زیر تشکیل می‌دهیم: اکنون با داشتن تقریب اولیه تقریبهای بعدی وو….و را تا مرحله مورد نظر به دست می آوریم.

مثال2- دوتقریب متوالی جواب مسأله مقدار اولیه با شرط اولیه را به وسیله روش تکرار پیکار به دست آورید : حل : دنباله تابعی روبرو را تشکل می دهیم : بنابراین این روش آنچنانساده است که می تواند براحتی در دوره دبیرستان و دوره پیش‌دانشگاهی استفاده گردد .

نمودار ترسیمی روشها و مدلهای گسسته و پیوسته ریاضی : در این قسمت می خواهیم جایگاه و نقش شاخه های مختلف ریاضی و ارتباط آنها را با همدیگر به وسیله نمودار ترسیم نماییم .

کار ریاضیات کاربردی بررسی و تجزیه و تحلیل مسائل جهان مادی فیزیک و دادن مدل ریاضی متناسب با انها و نهایتاً حل آنها با روشهای ریاضی می باشد .

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

مدلی که در ریاضیات برای بررسی و تجزیه و تحلیل آنها در نظر می‌گیریم.

با توجه به توانائی و مناسبت روشهای ریاضی نیز می تواند به حالت گسسته یا پیوسته در نظر گرفته شود .

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

در اینجا سیستم به طور ذاتی گسسته است ولی روشی که برای بررسی آن به کار می بریم ، یک مدل پیوسته می باشد و اینها در قلمرو حساب دیفرانسیل و انتگرال هستند .