نظریه گرافها برای المپیاد کامپیوتر
تعاریف اولیه
مقدمات و مدل سازی با گراف
انواع گراف
پیاده سازی گراف
گشت، گذر، مسیر، اکسترمال
زیرگراف ها
همبندی، یال برشی و راس برشی
گراف دو بخشی
درخت ها
خاصیت های مقدماتی
فاصله در درخت و گراف
شمردن تعداد درخت ها
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)
فهرست
گراف جهتدار
سوالات
سورس
گراف جهتدار
¶
تعاریف
تعریف 3.1.1 (گراف جهت دار)
درجه در گراف جهت دار
دور و مسیر در گراف جهت دار
قضایا و لم های مورد استفاده در این بخش
قضیه 3.1.2
قضیه 3.1.3
قضیه 3.1.4
چند تعریف دیگر
تورنومنت
تعریف 3.2.1 (تورنمنت)
شاه در تورنمنتها
تعریف 3.2.2 (شاه)
قضیه 3.2.3
مسیر همیلتونی در تورنمنت
تعریف 3.2.4(مسیر همیلتونی در گراف جهتدار)
قضیه 3.2.5
گراف جهتدار بدون دور
تعریف 3.3.1 (DAG)
یک خاصیت مهم
قضیه 3.3.2
مرتب سازی توپولوژیک
الگوریتم مرتب سازی توپولوژیک
اثبات درستی الگوریتم
پیچیدگی الگوریتم
پیادهسازی الگوریتم
مولفههای قویا همبند
مفاهیم اولیه
تعریف 3.4.1 (جفت راس قویا همبند)
تعریف 3.4.2 (گراف قویا همبند)
تعریف 3.4.3 (مولفه قویا همبند (strongly connected component یا به اختصار scc))
لم 3.4.4
نتیجه 3.4.5
تعریف 3.4.6 (گراف معکوس)
بدون دور بودن مولفههای قویا همبند
تعریف 3.4.7 (گراف فشرده شده مولفههای قویا همبند)
قضیه 3.4.8
نتیجه 3.4.9
پیدا کردن مولفههای قویا همبند
الگوریتم کساراجو
پیچیدگی الگوریتم
لم 3.4.10
پیادهسازی الگوریتم
تشخیص دور داشتن گراف جهت دار
مقدمه
الگوریتم پیدا کردن دور با استفاده از DFS
پیچیدگی الگوریتم
پیادهسازی الگوریتم
الگوریتم کان (kahn)
پیچیدگی الگوریتم
پیادهسازی الگوریتم
بازیها و گراف جهتدار
مقدمه
بررسی یک مثال
نتیجه
بازی حرکت مهره روی گراف
تعمیم
حل بازی روی گراف
چند نتیجه گیری سودمند
حرف آخر
گراف تابعی و گرافجایگشت
تعریف 3.7.1 (گرافجایگشت)
قضیه 3.7.2
قضیه 3.7.3
قبلی
بعدی