آموزش جامع نظریه گراف | مقدمه‌ای بر دنیای گراف‌ها - آخرین آپدیت

گراف چیست؟ What is a Graph?

• گراف خطوط هوایی Airlines Graph

• جابه‌جایی اسب شطرنج Knight Transposition

• هفت پل کونیگزبرگ Seven Bridges of Königsberg

• گراف چیست؟ What is a Graph?

• مثال‌های گراف Graph Examples

• کاربردهای گراف Graph Applications

• درجه رأس Vertex Degree

• مسیرها Paths

• اتصال‌پذیری Connectivity

• گراف‌های جهت‌دار Directed Graphs

• گراف‌های وزن‌دار Weighted Graphs

• مسیرها، دورها و گراف‌های کامل Paths, Cycles and Complete Graphs

• درخت‌ها Trees

• گراف‌های دو parte Bipartite Graphs

دورها Cycles

• لم دست دادن Handshaking Lemma

• درجه کل Total Degree

• مولفه‌های متصل Connected Components

• معمای گوارینی: کد Guarini Puzzle: Code

• کران پایین Lower Bound

• سنگ سنگین‌تر The Heaviest Stone

• گراف‌های جهت‌دار بدون دور (DAG) Directed Acyclic Graphs

• مولفه‌های به شدت متصل Strongly Connected Components

• دورهای اویلری Eulerian Cycles

• دورهای اویلری: معیارها Eulerian Cycles: Criteria

• دورهای همیلتونی Hamiltonian Cycles

• سرهم‌بندی ژنوم Genome Assembly

انواع کلاس‌های گراف Graph Classes

• تعمیر جاده Road Repair

• درخت‌ها Trees

• درخت پوشای کمینه Minimum Spanning Tree

• تخصیص وظایف Job Assignment

• گراف‌های دو parte Bipartite Graphs

• تطبیق‌ها Matchings

• قضیه هال Hall's Theorem

• خطوط مترو Subway Lines

• گراف‌های مسطح Planar Graphs

• فرمول اویلر Euler's Formula

• کاربردهای فرمول اویلر Applications of Euler's Formula

پارامترهای گراف Graph Parameters

• رنگ‌آمیزی نقشه Map Coloring

• رنگ‌آمیزی گراف Graph Coloring

• کران‌های عدد رنگی Bounds on the Chromatic Number

• کاربردها Applications

• کیک‌های گراف (Cliques) Graph Cliques

• کیک‌ها و مجموعه‌های مستقل Cliques and Independent Sets

• ارتباط با رنگ‌آمیزی Connections to Coloring

• قضیه مانتل Mantel's Theorem

• گراف‌های متعادل Balanced Graphs

• اعداد رمزی Ramsey Numbers

• وجود اعداد رمزی Existence of Ramsey Numbers

• سیستم آنتی‌ویروس Antivirus System

• پوشش رأس Vertex Covers

• قضیه کونیگ König's Theorem

جریان‌ها و تطبیق‌ها Flows and Matchings

• یک مثال An Example

• چارچوب کار The Framework

• فورد و فولکرسون: اثبات Ford and Fulkerson: Proof

• قضیه هال Hall's theorem

• چه چیزهای دیگر؟ What Else?

• چرا تطبیق‌های پایدار؟ Why Stable Matchings?

• ریاضیات و زندگی واقعی Mathematics and Real Life

• مثال‌های پایه Basic Examples

• جستجو برای یک تطبیق پایدار Looking For a Stable Matching

• الگوریتم گیل-شاپلی Gale-Shapley Algorithm

• اثبات صحت Correctness Proof

• چرا این الگوریتم ناعادلانه است؟ Why The Algorithm Is Unfair

• چرا الگوریتم بسیار ناعادلانه است؟ Why the Algorithm is Very Unfair