مقاله ریاضیات گسسته

توضیحات

  مقاله ریاضیات گسسته دارای 52 صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

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

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

بخشی از متن مقاله ریاضیات گسسته :

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

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

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

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

جایگاه و ضرورت آموزش ریاضیات گسسته در نظام جدید دبیرستانی
در جریان تغییر نظام آموزش دوره های كارشناسی ریاضی در سالهای اخیر در دانشگاهها و موسسات آموزش عالی شاهد بودیم كه درسهای جدید به تنا سب گرایشهای این رشته جایگزین درسهایی از نظام قبلی شدند. درس ریا ضیات گسسته نیز به ارزش 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 وكمیته ها با نشان داده شوند همچنین اعضای كمیته ها به صورت زیر مشخص شده باشند.
عضوكمیته هستند .
عضو كمیته هستند.
عضو كمیته هستند.
عضو كمیته هستند.
عضو كمیته هستند.
اگر به هر كمیته یك نقطه نسبت دهیم و دو نقطه را با خطی به هم وصل كنیم ، هرگاه یكدبر بخواهد در بیش از یك كمیته عضویت داشته باشد، آنگاه گراف مربوط به این وضعیت می تواند به صورت زیر باشد.

برای دریافت اینجا کلیک کنید