نظریه گرافها برای المپیاد کامپیوتر
تعاریف اولیه
مقدمات و مدل سازی با گراف
انواع گراف
پیاده سازی گراف
گشت، گذر، مسیر، اکسترمال
زیرگراف ها
همبندی، یال برشی و راس برشی
گراف دو بخشی
درخت ها
خاصیت های مقدماتی
فاصله در درخت و گراف
شمردن تعداد درخت ها
DFS
BFS
الگوریتم پیدا کردن قطر درخت
DFS Start/Finish Time
الگوریتم های راس و یال برشی
کارگاه پرورش ایده
گراف جهتدار
تعاریف
تورنومنت
گراف جهتدار بدون دور
مولفههای قویا همبند
تشخیص دور داشتن گراف جهت دار
بازیها و گراف جهتدار
گراف تابعی و گرافجایگشت
تکنیک های اثبات مسائل گراف
انتخاب های اکسترمالی
منقبض کردن
گراف و جادو
تور اویلری و دور همیلتونی
معرفی
تور اویلری در گراف جهت دار و بی جهت
De Bruijn sequence
قضیه های وجودی دور همیلتونی
الگوریتم های نمایی پیدا کردن دور و مسیر همیلتونی
الگوریتم های کوتاه ترین مسیر
بلمن فورد
دکسترا
فلوید وارشال
ماتریس ها
ماتریس و عملیات های روی آن
دترمینان ماتریس ها
ماتریس وقوع
ماتریس مجاورت
تعداد گشت ها به طول n
به دست آوردن توابع بازگشتی به کمک گراف و ماتریس
داده ساختار های درختی
درخت دودویی (Binary Tree)
درخت جست و جوی دودویی (BST یا Binary Search Tree)
Heap
DSU
Segment Tree
Trie
مسائل np و np کامل
تعریف np و np کامل
اثبات np کامل بودن مساله sat
مسائل np کامل گراف
Lca
شرح مساله
راه حل O(n+q*lg(n)) به کمک جداسازی سبک-سنگین
الگوریتم برونخط تارجان
ارتباط LCA و RMQ
راه خطی برای LCA
درخت مجازی
الگوریتم های پیشرفته درخت
درخت پوشای کمینه
گونی
سنتروید
هافمن کدینگ
هش درخت
تجزیه سبک سنگین(HLD)
همبندی
برش ها و همبندی
گراف k همبند
برش کمینه و جریان بیشینه
تطابق
آشنایی
تطابق در گراف دوبخشی
قضایا ی مینماکس
کاربرد ها
جریان بیشینه و تطابق
Poset
تطابق در گراف های عام
مباحث ویژه
گراف مسطح
دنباله درجه ای
رنگ آمیزی
یک ریختی
Random Walk
اعداد رمزی
مجموعه مستقل و خوشه
2-SAT
چند ماتریس خاص
ضمیمه
چگونه از این کتاب استفاده کنیم؟
آشنایی با الگوریتم ها و پیچیدگی
برگه تقلب (Cheat sheet)
فهرست
سوالات
سورس
نظریه گرافها برای المپیاد کامپیوتر
¶
حتما پیش از شروع به خواندن، مطلب
چگونه این کتاب را بخوانیم
را مطالعه کنید.
تعاریف اولیه
مقدمات و مدل سازی با گراف
انواع گراف
پیاده سازی گراف
گشت، گذر، مسیر، اکسترمال
زیرگراف ها
همبندی، یال برشی و راس برشی
گراف دو بخشی
درخت ها
خاصیت های مقدماتی
فاصله در درخت و گراف
شمردن تعداد درخت ها
DFS
BFS
الگوریتم پیدا کردن قطر درخت
DFS Start/Finish Time
الگوریتم های راس و یال برشی
کارگاه پرورش ایده
گراف جهتدار
تعاریف
تورنومنت
گراف جهتدار بدون دور
مولفههای قویا همبند
تشخیص دور داشتن گراف جهت دار
بازیها و گراف جهتدار
گراف تابعی و گرافجایگشت
تکنیک های اثبات مسائل گراف
انتخاب های اکسترمالی
منقبض کردن
گراف و جادو
تور اویلری و دور همیلتونی
معرفی
تور اویلری در گراف جهت دار و بی جهت
De Bruijn sequence
قضیه های وجودی دور همیلتونی
الگوریتم های نمایی پیدا کردن دور و مسیر همیلتونی
الگوریتم های کوتاه ترین مسیر
بلمن فورد
دکسترا
فلوید وارشال
ماتریس ها
ماتریس و عملیات های روی آن
دترمینان ماتریس ها
ماتریس وقوع
ماتریس مجاورت
تعداد گشت ها به طول n
به دست آوردن توابع بازگشتی به کمک گراف و ماتریس
داده ساختار های درختی
درخت دودویی (Binary Tree)
درخت جست و جوی دودویی (BST یا Binary Search Tree)
Heap
DSU
Segment Tree
Trie
مسائل np و np کامل
تعریف np و np کامل
اثبات np کامل بودن مساله sat
مسائل np کامل گراف
Lca
شرح مساله
راه حل O(n+q*lg(n)) به کمک جداسازی سبک-سنگین
الگوریتم برونخط تارجان
ارتباط LCA و RMQ
راه خطی برای LCA
درخت مجازی
الگوریتم های پیشرفته درخت
درخت پوشای کمینه
گونی
سنتروید
هافمن کدینگ
هش درخت
تجزیه سبک سنگین(HLD)
همبندی
برش ها و همبندی
گراف k همبند
برش کمینه و جریان بیشینه
تطابق
آشنایی
تطابق در گراف دوبخشی
قضایا ی مینماکس
کاربرد ها
جریان بیشینه و تطابق
Poset
تطابق در گراف های عام
مباحث ویژه
گراف مسطح
دنباله درجه ای
رنگ آمیزی
یک ریختی
Random Walk
اعداد رمزی
مجموعه مستقل و خوشه
2-SAT
چند ماتریس خاص
ضمیمه
چگونه از این کتاب استفاده کنیم؟
آشنایی با الگوریتم ها و پیچیدگی
برگه تقلب (Cheat sheet)
بعدی