نظریه های گراف ها در آموزش المپیاد کامپیوتر-اول مشاور
17 اسفند 1395

نظریه های گراف ها در آموزش المپیاد کامپیوتر-اول مشاور

نظریه‌ی گراف‌ها
گراف
• تعریف گراف
• خانواده‌های مختلف گراف
• مسیر٬ دور٬ پیمایش و فواصل
• درجه‌ی رئوس
• یک‌ریختی٬ هم‌ریختی و خودریختی
• ماتریس‌ها و نمایش گراف
درخت
• تعریف درخت
• ویژگی‌های درخت
• درخت‌های ریشه‌دار و دودویی
• شمارش درخت‌ها
• درخت‌های فراگیر و شمارش آن‌ها
همبندی
• همبندی راسی و یالی
• راس و یال برشی
• گراف‌‌های k-همبند
• بلوک‌های همبندی
گراف‌‌های جهت‌دار
• تورنمنت
• گراف‌های قویا همبند
دورها
• دور همیلتنی
• تور اویلری
تطابق
• قضیه‌ی ازدواج
• تطابق در گراف دوبخشی
• تطابق در گراف‌های عام
• پوشش راسی و قضایای دوگان
گراف‌های مسطح
• فرمول اویلر و کاربردهای آن
• رنگ‌آمیزی گراف‌های مسطح
رنگ‌آمیزی گراف‌ها
• رنگ‌آمیزی راسی
• رنگ‌آمیزی یالی
• ساختارهای k-رنگی
• جنبه‌های شمارشی رنگ‌آمیزی