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

Graph Theory & Applications

---

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

سرفصل درس:

• مفاهیم و تعاریف اولیه گراف های ساده، جهت دار و مخلوط - درجه راس - همبندی – زیرگراف ها - یکریختی گرافها – مکمل گراف. ماتریس های وابسته به گراف ها مانند ماتریس مجاورت و ماتریس وقوع. رده های مختلف گرافها مانند: دور- مسیر- دوبخشی – وتری – ابرمکعب و …. اعداد استقلال و پوشش راسی گراف ها. دورهای همیلتونی و اویلری. عملیات مختلف روی گراف ها. همبندی راسی و یالی – گراف های 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..