پل یالی است که حذفش تعدادِ مؤلفه‌های هم‌بند را بیشتر کند؛ رأسِ برشی همین اثر را با حذفِ یک رأس و یال‌های متصل به آن دارد. این دو مفهوم یکی نیستند. در گرافی با دو مثلثِ مشترک و یک شاخه، دفترِ کشف و lowlink را می‌سازیم و نتیجه را با حذفِ مستقلِ تک‌تک یال‌ها و رأس‌ها کنترل می‌کنیم.
دو مثلث و یک گرهٔ جدا
یال‌های AB،BC وCA مثلثِ اول وCD،DE وEC مثلثِ دوم را می‌سازند. هر دو در C مشترک‌اند. یالِ EF شاخهٔ انتهایی است وU هیچ یالی ندارد. گراف ساده، بدون جهت و بی‌وزن است؛ هر یال فقط یک بار در ورودی می‌آید و دو جهتِ پیمایش دارد.
پیش از حذف، دو مؤلفه داریم: شش رأسِ AتاF در یک گروه وU در گروهِ جدا. حذفِ EF گروهِ اول را می‌شکند و تعداد را به سه می‌رساند؛ پس EF پل است. حذفِ هر یالِ یک مثلث، راهِ دیگرِ همان مثلث را باقی می‌گذارد و تعداد را افزایش نمی‌دهد.
دفترِ discovery و low
DFS هنگامِ ورود، شمارهٔ کشف را ثبت می‌کند. low هر رأس، کوچک‌ترین شمارهٔ کشفی است که از زیر‌درختِ آن با یال‌های درخت و یک برگشتِ مجاز قابل دستیابی است. پس از برگشت از فرزند، low فرزند در low والد اثر می‌گذارد؛ یالِ برگشت به رأسِ دیده‌شده هم شمارهٔ کشف را وارد محاسبه می‌کند.
یالِ همان والد را برگشت حساب نمی‌کنیم. در گرافِ چندیالی، تشخیصِ فقط نامِ والد کافی نیست و شناسهٔ یال لازم می‌شود؛ آن دامنه در این کد پذیرفته نشده است. دفتر، parent، شمارهٔ کشف و low نهاییِ تمام رأس‌ها را نگه می‌دارد؛ U نیز حذف نمی‌شود.
شرطِ پل با شرطِ رأس فرق دارد
برای یالِ درختِ u→v، اگر low[v] از discovery[u] بزرگ‌تر باشد، زیر‌درختِ v راهِ برگشت به u یا بالاتر ندارد؛ یال پل است. برای رأسِ غیرریشه، کافی است یک فرزند داشته باشد که low آن دست‌کم discovery همان رأس باشد تا حذفِ رأس مسیرِ زیر‌درخت را جدا کند.
در گرافِ اصلی، فقط EF پل است، اما C وE رأسِ برشی‌اند. C دو مثلث را از هم جدا می‌کند، بااین‌حال هیچ‌یک از یال‌هایِ آن دو مثلث پل نیستند. نبودنِ پل، نبودنِ رأسِ برشی را نتیجه نمی‌دهد.
ریشهٔ DFS قاعدهٔ جدا دارد
ریشه والد ندارد؛ شرطِ غیرریشه را روی آن کپی نمی‌کنیم. ریشه زمانی برشی است که بیش از یک فرزندِ درختِ DFS داشته باشد. مثالِ ستاره و حالت‌های چندمؤلفه‌ای جدا اجرا شده‌اند. یک ریشه با یک فرزندِ درخت الزاماً برشی نیست، حتی اگر همسایه‌های زیادی داشته باشد.
در هر مؤلفه، DFS تازه شروع می‌شود، اما دفترِ شماره‌های کشف در همین اجرا یکتا می‌ماند. ترتیبِ بازدید می‌تواند شماره‌ها را عوض کند؛ مجموعهٔ پل‌ها و رأس‌های برشی باید با معنای گراف سازگار بماند. شمارهٔ نمایشیِ low هویتِ واقعیِ یک سرویس نیست.
حذفِ مستقیم، oracleِ مستقل است
تابعِ مستقل ابتدا تعدادِ مؤلفه‌های گرافِ اصلی را با سیلابِ پیمایش حساب می‌کند. سپس هر یال و هر رأس را جدا حذف و تعداد را دوباره می‌سنجد. مقایسه با همان خطِ مبنایِ دو مؤلفه انجام می‌شود؛ فقط «بیشتر از یک» معیار نیست.
همهٔ۶۴گرافِ سادهٔ چهاررأسی نیز با همین oracle کنترل شده‌اند؛ این پوششِ جهانِ چهاررأسی است، نه اثبات یا benchmark برای همهٔ اندازه‌ها. پنج ورودیِ نامعتبر، از سرِ ناشناخته و یالِ تکراری تا self-loop، جهت‌دار یا بیش از۸رأس، رد می‌شوند.
SCC دسترسیِ دوطرفهٔ گرافِ جهت‌دار را می‌سنجد و پیمایش فقط بازدید است. NetworkX اجرا نشده؛ تابعِ bridges آن از روشِ زنجیره استفاده می‌کند، نه الزاماً lowlink اینجا. ادامه در مبانی هوش مصنوعی؛ این گراف سنجشِ پایداریِ زیرساختِ اپرا نیست.
فایل تمرین و منبع
کد مستقل تمرین و تمام کنترل‌ها؛ Python · ورودی و تمام نتایج اجرای واقعی؛ JSON
- NetworkX۳٫۷،تعریفِ رأس برشی و افزایشِ مؤلفه‌ها خوانده شد؛ کتابخانه اجرا نشده
- NetworkX۳٫۷،تعریفِ پل و روشِ زنجیرهٔ پیاده‌سازی خوانده شد؛ الگوریتمِ این فایل lowlink مستقل است
- کد رسمیِ بخشِ _biconnected_dfs؛ discovery/low،حذفِ والد و شرطِ فرزندانِ ریشه خوانده شد؛ کدِ بازگشتیِ تمرین اصیل است
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.