نظریه الگوریتمی گراف‌ها

Algorithmic Graph Theory

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

هدف کلی

هدف از این درس، آشنایی دانشجویان با مباحث پیشرفته در نظریه‌ی گراف‌ها است. در این درس دانشجویان ضمن آشنایی با رده‌های مهمی از گراف‌ها نظیر گراف‌های تام، گراف‌های مسطح و گراف‌های وتری، با روش‌های طراحی الگوریتم‌های کارا برای این دسته از گراف‌ها آشنا می‌شوند.

سرفصل‌ها

  1. تعاریف و مفاهیم اولیه
  2. گراف‌های بازه‌ای
  3. گراف‌های وتری و الگوریتم‌های تشخیص
  4. گراف‌های مقایسه‌پذیری
  5. گراف‌های تام
  6. درخت‌ها و عرض درختی
  7. گراف‌های مسطح
  8. مسائل روی گراف‌های مسطح
  9. جداسازها
  10. گراف‌های مثلث‌بندی‌شده
  11. نظریه طیفی گراف‌ها

ارزیابی پیشنهادی

منابع پیشنهادی

  1. M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. 2nd Edition, Elsevier, 2004.
  2. G. Chartrand and O. R. Oellermann. Applied and Algorithmic Graph Theory. McGraw-Hill, 1993.
  3. T. Nishizeki and N. Chiba. Planar Graphs: Theory and Algorithms. Dover Publications, 1988.
  4. D. B. West. Introduction to Graph Theory. 2nd Edition, Pearson Education, 2001.