الگوریتم‌های گراف

الگوریتم‌های گراف بر روی شبکه‌هایی از رأس‌ها و یال‌ها عمل می‌کنند تا به سؤالاتی در مورد اتصال‌پذیری، فواصل، ساختارهای پوشا و جریان‌ها پاسخ دهند — هسته الگوریتمی مسائلی که به صورت گراف مدل‌سازی می‌شوند.

Definition

الگوریتم‌های گراف رویه‌هایی هستند که ویژگی‌های گراف‌ها — ساختارهای ریاضی متشکل از رأس‌های متصل به وسیله یال‌ها — را محاسبه می‌کنند یا مسائل بهینه‌سازی را روی آن‌ها حل می‌کنند، مانند دسترسی‌پذیری، کوتاه‌ترین فواصل، درخت‌های پوشا و حداکثر جریان‌ها.

Scope

این حوزه الگوریتم‌های مربوط به گراف‌ها و شبکه‌ها را پوشش می‌دهد: پیمایش سیستماتیک (جستجوی اول سطح و جستجوی اول عمق)، محاسبه کوتاه‌ترین مسیر، درخت‌های پوشای کمینه، جریان شبکه و تطابق، و مسائل ساختاری (اتصال‌پذیری، ترتیب توپولوژیکی، چرخه‌ها) که این الگوریتم‌ها پشتیبانی می‌کنند. این حوزه به نمایش‌های گراف (لیست‌های مجاورت و ماتریس‌ها) و تأثیر آن‌ها بر هزینه الگوریتم می‌پردازد و به الگوهای طراحی (حریصانه، برنامه‌ریزی پویا) و ساختارهای داده (صف‌های اولویت‌دار) که الگوریتم‌های گراف به آن‌ها متکی هستند، مرتبط می‌شود. این حوزه مطالعه ترکیبیاتی انتزاعی گراف‌ها را که به ریاضیات گسسته تعلق دارد، شامل نمی‌شود.

Sub-topics

• پیمایش گراف
• درخت‌های پوشای مینیمم
• الگوریتم‌های جریان شبکه
• الگوریتم‌های کوتاه‌ترین مسیر

Core questions

• یک گراف چگونه نمایش داده می‌شود و این نمایش چگونه بر کارایی الگوریتم تأثیر می‌گذارد؟
• پیمایش‌های اول سطح و اول عمق چگونه اتصال‌پذیری و ساختار را آشکار می‌کنند؟
• کوتاه‌ترین مسیرها تحت شرایط مختلف وزن یال چگونه محاسبه می‌شوند؟
• کدام ساختارها با حداقل هزینه یک گراف را پوشش می‌دهند و چگونه یافت می‌شوند؟
• چه مقدار جریان می‌تواند از یک شبکه عبور کند و چه چیزی آن را محدود می‌کند؟

Key concepts

• رأس‌ها و یال‌ها
• لیست و ماتریس مجاورت
• جستجوی اول سطح و اول عمق
• کوتاه‌ترین مسیرها
• درخت پوشای کمینه
• مرتب‌سازی توپولوژیکی
• جریان شبکه
• حداکثر جریان برش کمینه

Key theories

جستجوی گراف به عنوان یک پایه

جستجوی اول سطح و اول عمق به طور سیستماتیک از تمام رأس‌های قابل دسترس بازدید می‌کنند و اساس اتصال‌پذیری، مرتب‌سازی توپولوژیکی، تشخیص چرخه و بسیاری دیگر از محاسبات گراف را تشکیل می‌دهند.

دوگانگی حداکثر جریان برش کمینه

حداکثر جریان از طریق یک شبکه برابر با ظرفیت برش کمینه آن است؛ این دوگانگی، که توسط فورد و فولکرسون برقرار شد، زیربنای الگوریتم‌های جریان است و به مسائل تطابق و اتصال‌پذیری مرتبط می‌شود.

Clinical relevance

الگوریتم‌های گراف طیف وسیعی از مسائل واقعی را مدل‌سازی و حل می‌کنند: مسیریابی و ناوبری (کوتاه‌ترین مسیرها)، طراحی شبکه و زیرساخت (درخت‌های پوشا)، زمان‌بندی و حل وابستگی (مرتب‌سازی توپولوژیکی)، تطابق دو بخشی در تخصیص و توصیه، و مسائل جریان در لجستیک، مخابرات و تقسیم‌بندی تصویر.

History

نظریه گراف الگوریتمی در اواسط قرن بیستم به سرعت رشد کرد: الگوریتم کوتاه‌ترین مسیر دایکسترا (1959)، کار فورد و فولکرسون در مورد حداکثر جریان (1956)، و الگوریتم‌های درخت پوشا کروسکال و پریم (1956-1957). الگوریتم‌های مبتنی بر جستجوی اول عمق رابرت تارژان در دهه 1970 راه‌حل‌های زمان خطی برای بسیاری از مسائل اتصال‌پذیری ارائه دادند و الگوریتم‌های گراف را به عنوان یک حوزه اصلی تثبیت کردند.

Key figures

• Edsger W. Dijkstra
• Lester Ford
• Delbert Fulkerson
• Robert Tarjan

Seminal works

• dijkstra1959
• cormen2009
• kleinberg2006

Frequently asked questions

چه زمانی باید یک گراف را به عنوان لیست مجاورت در مقابل ماتریس مجاورت نمایش دهم؟

لیست‌های مجاورت فضایی متناسب با تعداد یال‌ها مصرف می‌کنند و برای گراف‌های خلوت و پیمایش کارآمد هستند. ماتریس‌های مجاورت فضایی متناسب با مربع تعداد رأس‌ها مصرف می‌کنند و امکان جستجوی یال با زمان O(1) را فراهم می‌کنند، که آن‌ها را برای گراف‌های چگال یا الگوریتم‌هایی که مکرراً یال‌ها را آزمایش می‌کنند، مناسب می‌سازد.

آیا مسائل گراف همیشه به طور کارآمد قابل حل هستند؟

بسیاری از مسائل اصلی گراف (پیمایش، کوتاه‌ترین مسیرها، درخت‌های پوشا، جریان‌ها) الگوریتم‌های زمان چندجمله‌ای کارآمدی دارند، اما برخی دیگر — مانند مسئله فروشنده دوره‌گرد، رنگ‌آمیزی گراف و بزرگترین کلیک — NP-سخت هستند و با روش‌های تقریبی یا مبتنی بر جستجو حل می‌شوند.