Articulation Point رأسی است که حذف آن تعداد بخشهای همبند گراف را بیشتر میکند. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Articulation Points زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
با DFS و مقادیر discovery/low میفهمیم کدام رأس نقش نقطه شکست دارد.
مراحل اجرا
- DFS و discovery time را ثبت میکنیم.
- low هر رأس را محاسبه میکنیم.
- ریشه با بیش از یک child بحرانی است.
- برای غیرریشه اگر low[child] >= disc[node] باشد، node بحرانی است.
نمونه کد JavaScript
// Tarjan idea: a non-root u is critical when low[v] >= disc[u]
// for one of its DFS children v. A DFS root is critical with >1 child.
function isArticulation(discU, lowChild) {
return lowChild >= discU;
}مثالهای واقعی و دنیای کار
- روتر بحرانی
- Single Point of Failure
- ایستگاه کلیدی حملونقل
- سرویس مرکزی زیرساخت
پیچیدگی زمانی و فضایی
O(V + E) زمان و O(V) حافظه
چه زمانی استفاده کنیم؟
تحلیل نقاط شکست شبکه
چه زمانی مناسب نیست؟
برای یال بحرانی باید Bridges را بررسی کرد.
جمعبندی
Articulation Points را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.