پرش به مطلب اصلی

نظریه گراف و کاربردها

Graph Theory & Applications​

نام درس:نظریه گراف و کاربردهامقطع:کارشناسی
پیش‌نیاز:مبانی ترکیبیاتگروه درس:تخصصی اختیاری
هم‌نیاز:نداردنوع درس:نظری
تعداد واحد:3تعداد ساعت:48
حل تمرین:ندارد

سرفصل درس:

  • مفاهیم و تعاریف اولیه گراف های ساده، جهت دار و مخلوط - درجه راس - همبندی – زیرگراف ها - یکریختی گرافها – مکمل گراف. ماتریس های وابسته به گراف ها مانند ماتریس مجاورت و ماتریس وقوع. رده های مختلف گرافها مانند: دور- مسیر- دوبخشی – وتری – ابرمکعب و …. اعداد استقلال و پوشش راسی گراف ها. دورهای همیلتونی و اویلری. عملیات مختلف روی گراف ها. همبندی راسی و یالی – گراف های 2-همبند و بلوک ها - قضیه منگر. تطابق ها و قضیه هال. گراف های مسطح - قضیه کوراتوسکی. انواع رنگ آمیزی گراف ها و قضایای معروف مربوطه. مجموعه‌های مستقل و خوشه ها.

منابع:

    1. Diestel, R. (2017). Extremal Graph Theory. In Graph Theory (pp. 173-207). Springer, Berlin Heidelberg.
    1. West, D. B. (1996). Introduction to Graph Theory: Vol. 2. Prentice Hall.
    1. Bondy, J. A., & Murty, U. S. R. (1976). Graph Theory with Applications: Vol. 290. Macmillan, London..