1- شناسنامه درس:

1-1- نام درس:

نظریه گراف

2-1- مقطع درس:

کارشناسی

3-1- تعداد واحد درس:

3 واحد

4-1- پیش‌نیاز درس:

ریاضیات گسسته

2- مشخصات درس:

1-2- اهداف آموزشی:

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

2-2- مرجع اصلی درس:

R. Balakrishnan, K. Ranganathan, "Textbook of Graph Theory", 0200
 

Adrian Bondy, U.S.R. Murty, "Graph Theory", 0224

3- نمره‌بندی درس:

- ارزش‌یابی مستمر: 5 مسئله 20 نمره

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

- سخنرانی: 10 نمره

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

- گزارش: 20 نمره

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

- آزمون‌ها:

میان‌ترم 20 نمره شامل 10 نمره کتبی و 10 نمره شفاهی

پایان‌ترم 30 نمره شامل 15 نمره کتبی و 15 نمره شفاهی

4- محتوای درس:

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