Skip to content

Latest commit

 

History

History
85 lines (85 loc) · 2.3 KB

topics.md

File metadata and controls

85 lines (85 loc) · 2.3 KB

تعاریف اولیه

  • مقدمات و پیاده سازی گراف
  • مدل سازی با گراف
  • همبندی، یال برشی و راس برشی
  • گراف دو بخشی
  • گشت، گذر، مسیر، اکسترمال

پیمایش گراف

  • درخت چیست؟
  • dfs
  • bfs

گراف جهتدار

  • تعاریف
  • تورنومنت
  • کینگ
  • اس اس سی
  • بازی ها و گراف جهت دار
  • Dag + Topol sort
  • الگوریتم مسیر خاکستری
  • گراف تابعی و گراف جایگشت

آشنایی با درخت ها

  • خاصیت های مقدماتی
  • فاصله در درخت و گراف
  • مرکز و قطر گراف
  • شمردن تعداد درخت ها
  • الگوریتم پیدا کردن قطر درخت
  • درخت dfs, bfs
  • الگوریتم های راس و یال برشی

تور اویلری و دور همیلتونی

  • معرفی
  • تور اویلری در گراف جهتدار و بی جهت
  • De Bruijn sequence
  • قضیه های وجودی دور همیلتونی
  • الگوریتم های نمایی پیداکردن دور و مسیر همیلتونی
  • Knight's tour

الگوریتم های کوتاه ترین مسیر

  • بلمن فورد
  • دکسترا
  • فلوید

ماتریس ها

  • ماتریس و عملیات های روی آن
  • دترمینان ماتریس ها
  • ماتریس وقوع
  • ماتریس مجاورت
  • تعداد مسیر های به طول n
  • بدست آوردن توابع بازگشتی به کمک گراف و ماتریس

داده ساختار های درختی

  • Binary Tree
  • BST
  • Heap
  • DSU
  • Segment tree

MST

  • Kruskal
  • Prim
  • Buvrika

Lca

  • تبدیل Rmq , Lca
  • sparse table
  • tarjan offline algorithm
  • precompute O(nlg) Query O(1) -> تور اویلری درخت

الگوریتم های پیشرفته درخت

  • سنتروید
  • گونی
  • اچ ال دی
  • هافمن کدینگ
  • هش درخت

تطابق

  • قضایای مینماکس
  • الگوریتم ها
  • تطابق در گراف های عام

همبندی

  • برش ها و همبندی
  • گراف کا همبند
  • فلو

مباحث ویژه

  • گراف مسطح
  • دنباله درجه‌ای
  • رنگ آمیزی
  • یک ریختی
  • Random Walk
  • اعداد رمزی
  • چنذجمله ای گراف
  • مجموعه مستقل و خوشه
  • 2sat
  • چند ماتریس خاص