پایان نامه مساله زمانبندی و حل آن با استفاده از رنگ‌آمیزی گراف‌ها

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

فرمت فایل : WORD (قابل ویرایش)

تعداد صفحات:91

فهرست مطالب:
فصل اول : یادآوری و تعاریف    1
فصل دوم   عدد تعیین کننده رنگ‌آمیزی راسی گراف‌های منتظم    6
2-1 مقدمه     6
2-2 طیف عدد رنگی     8
2-3 عدد تعیین کننده گراف های منتظم    12
2-4 حدس     27
فصل سوم : عدد تعیین کننده گراف های k- رنگ k- منتظم     28
3-1 مقدمه     28
3-2 برخی از لم های ضروری     31
3-3 یک الگوریتم ساختاری     37
3-4 نتایج عمومی     39
3-5 حالت k=6  و k=7    50
3-5 حالت فصل چهارم : آشنایی با مساله زمانبندی    55
4-1 مساله زمانبندی چیست     55
4-2 مدلسازی مساله زمانبندی    57
4-3 زمانبندی امتحانات    59
فصل پنجم : حل مساله زمانبندی امتحانات با روش رنگ آمیزی گراف    63
5-1 مدلسازی زمانبندی امتحانات     64
5-2 الگوریتم رنگ آمیزی     65
5-3 اختصاص کلاس به هر امتحان     70
فصل ششم : برنامه ریزی آموزش با استفاده از رنگ آمیزی گراف    76
6-1 مقدمه     76
6-2 رنگ آمیزی گراف و الگوریتم برنامه ریزی     77
6-3 طراحی نرم افزار برنامه ریزی    78
6-4 نتایج نمونه     86
6-5 خلاصه     87
مراجع    89

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

بر خلاف‌موضوع‌های دیگری ریاضی، نقطه شروع نظریه گراف‌ها ریشه در مقاله‌ای مشخص دارد که لئونارد اویلر (1783-1707) ریاضیدان سوئیسی در سال 1736 میلادی منتشر کرده است.
اندیشه اصلی این مطالب، متکی بر مثال معروف هفت پل کونیکسبرگ است. این مساله‌ای است که همه آنرا می‌دانند و اویلر از حل این مسئله مفاهیم اصلی نظریه گراف را بوجود آورد.
یکی از موضوعات مورد بحث در نظریه گراف، بحث رنگ‌آمیزی گراف‌ها است این مساله با صورتی بسیار ساده شروع می‌شود ولی امروزه در علوم مختلف و دارای کاربردهای زیادی است. این پروژه نیز به این مبحث می‌پردازد
برای اینکه کاربرد شهودی از رنگ آمیزی گراف را مطرح کنیم، مساله زیر را در نظر می‌گیریم: در یک شرکت شیمیایی، شخصی متصدی انبار کردن ترکیب‌های شیمیایی در انبار است. چون بعضی از انواع ترکیب‌ها (نظیر اسیدها و بازها) نباید در مجاورت هم نگهداری شوند، او تصمیم می‌گیرد از همکارش بخواهد انبار را به ناحیه‌های جدا از هم تقسیم کند، بطوریکه بتوان موادشیمیایی ناسازگار با هم را در بخش‌های جدا از یکدیگر انبار کرد.
اگر این شرکت 25 ترکیب شیمیایی بفروشد، فرض کنید.
 
مجموعه‌ راس‌ها باشد.
به ازای هر   اگر ضروری است که  در بخش های جدا از هم انبار شوند، رسم می‌کنیم. این عمل گراف G=(V,E) را می‌دهم که مصداقی از مساله رنگ آمیزی گراف‌ها می باشد.[1]
البته این مساله تنها یکی از کاربردهای نظریه گراف‌ها و علی الخصوص بحث رنگ‌آمیزی گراف‌ها بود. از موضوعات دیگر جالب و مورد بحث در این زمینه می‌توان به بحث زمانبندی اشاره کرد.
ما در این پروژه به دو بحث مهم زمانبندی که عبارتند از زمانبندی امتحانات و زمانبندی کلاس اشاره خواهیم کرد و این دو بحث را با استفاده از رنگ‌آمیزی گراف‌ها حل خواهیم کرد.
بطور کلی ما در فصل اول این پروژه تعاریفی اولیه از گراف ارائه می‌دهیم.
در فصل دوم در مورد عدد تعیین کننده رنگ آمیزی راسی بحث خواهیم کرد.
فصل سوم را به عدد تعیین کننده گراف‌های k- رنگ، k- منتظم اختصاص خواهیم داد.
در فصل چهارم با مساله زمانبندی آشنا خواهیم شد.
فصل پنجم را به حل مساله زمانبندی امتحانات با روش رنگ‌آمیزی گراف می‌پردازیم.
در انتها نیز برنامه‌ریزی آموزشی (زمانبندی کلاسی) را به روش رنگ‌آمیزی گراف انجام خواهیم داد.