| 1 |
جایگاه درس در برنامه درسی دوره |
درس کهاد |
| 2 |
هدف کلی |
هدف این درس، آشنایی دانشجویان با مبانی نظریه گراف، درک مفاهیم بنیادی و قضایای اصلی آن، و کسب توانایی به‌کارگیری این مفاهیم در حل مسائل و مدلسازی‌های ریاضی و مهندسی است. همچنین در این درس بر ارتباط نظریه گراف با سایر شاخه‌های ریاضیات و علوم مهندسی و کاربردهای عملی آن در حوزه‌های مختلف علوم و فناوری تأکید می‌شود. |
| 3 |
شایستگی های پایه |
مبانی ترکیبیات |
| 4 |
اهداف یادگیری |
دانشجو پس از گذراندن این درس باید بتواند:
1. شناخت و تعریف مفهومی:
گراف را به عنوان یک موجود مجرد تعریف کند و تفاوت آن با نمایش هندسی و توپولوژیک گراف را توضیح دهد.
انواع مختلف نمایش یک گراف (ماتریس مجاورت، ماتریس درجه، لیست یال و غیره) را بشناسد و مقایسه کند.
2. درک مفاهیم بنیادی نظریه گراف:
مفاهیم پایه مانند رأس، یال، درجه، زیرگراف، همبندی، اجزای همبند و مسیر را تعریف و به‌کار گیرد.
گراف‌های خاص و معروف (مانند گراف کامل، گراف دو بخشی، گراف‌های چرخه و مسیر) را تشخیص دهد و ویژگی‌هایشان را بیان کند.
3. تسلط بر نتایج مهم کلاسیک:
ویژگی‌ها و قضایای اساسی مربوط به درخت‌ها را بیان و در حل مسائل به کار گیرد.
شرایط و ویژگی‌های گراف‌های اویلری و همیلتونی را توضیح دهد و مسائل مرتبط را تحلیل کند.
4. تحلیل ساختاری و پیشرفته:
مفهوم تطابق در گراف‌ها و قضایای مهم مربوط به آن (مثل قضیه کونیگ) را بشناسد و به کار ببرد.
همبندی در گراف‌ها را تحلیل کند و مفاهیم مرتبط با مسیرها و برش‌ها را درک نماید.
5. رسم و تفسیر هندسی:
تفاوت گراف مجرد با تصویر هندسی آن را درک کند و کاربرد این تفاوت را در مدلسازی توضیح دهد.
گراف‌های مسطح را تشخیص دهد و با مقدمات نشاندن گراف روی رویه‌ها آشنا شود.
6. کاربردهای رنگ‌آمیزی و بهینه‌سازی:
مسأله‌ی رنگ‌آمیزی گراف‌ها را تعریف کند و قضایای کلاسیک مرتبط را بیان نماید.
کاربرد رنگ‌آمیزی در مسائل واقعی (زمان‌بندی، تخصیص منابع و غیره) را تحلیل کند.
7. گراف‌های جهت‌دار و کاربردهای آن:
گراف‌های جهت‌دار را تعریف و در مسائل مختلف مانند شبکه‌های جریان و مسیرهای بحرانی به کار ببرد.
8. مدلسازی ریاضی با گراف‌ها:
مسائل واقعی در علوم رایانه، مهندسی و علوم داده را با استفاده از گراف‌ها مدلسازی کند.
توانایی انتخاب نوع مناسب گراف برای مدلسازی یک مسأله‌ی واقعی را کسب نماید. |
| 5 |
روش تدریس |
در این درس با مفاهیم اصلی نظریه گراف آشنا می‌شویم و با برخی کاربردهای آن نیز روبرو خواهیم شد. امروزه، جایگاه نظریه گراف در علوم ریاضی و بالاخص در رشته علوم کامپیوتر بسیار شاخص بوده و عملاً زبان مدلسازی در بسیاری از شاخه‌های ریاضیات و علوم کامپیوتر در حالات گسسته بر این نظریه استوار است. همچنین کاربردهای این نظریه در علوم مهندسی نیز از بدو پیدایش آن مورد توجه بوده است. لذا این درس با دو وجهه مختلف، ارائه مبانی نظریه و آشنایی با قضیه‌های اصلی و استدلال دقیق و همچنین آشنایی با کاربردهای مختلف این احکام در علوم کامپیوتر و علوم مهندسی ارائه می‌شود. |
| 6 |
وظایف دانشجو |
انتظار می‌رود دانشجویان محترم حضور موثر در کلاس داشته باشند. همچنین تمرین‌های تحویلی مرتبط را نیز حل نمایند و در صورت وجود اشکال و یا ابهام با استاد درس مطرح نمایند. همچنین، تکالیف و گزارش‌ها را در زمان مقرر از طریق سایت vu.um.ac.ir تحویل دهند. |
| 7 |
منبع |
توکلی، م. و رهبرنیا، ف. (1397). نظریه گراف و کاربردهای آن. مشهد: دانشگاه فردوسی مشهد. |
| 8 |
مواد و امکانات آموزشی |
کتاب هایی با عنوان نظریه گراف در کتابخانه و اینترنت |
| 9 |
نحوه ارزشیابی |
آزمون میان ترم+ آزمون پایان ترم + حل تمرین + حضور فعال و موثر در کلاس |
| 10 |
فایل |
Pdf File |