الگوریتم مؤلفه قوی مبتنی بر مسیر: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ماني صفحهٔ Path-based strong component algorithm را به الگوریتم گابو منتقل کرد |
بدون خلاصۀ ویرایش |
||
خط ۱:
در [[نظریه گراف]] برای پیدا کردن [[مولفه‌های قویا همبند]] یک [[گراف جهتدار]]
▲در [[نظریه گراف]] برای پیدا کردن [[مولفه‌های قویا همبند]] یک [[گراف جهتدار]] می‌توان از [[الگوریتمPath-based strong component]] استفاده کرد. قبل از این الگوریتم، [[الگوریتم کساراجو]] و [[الگوریتم تارجان]] نیز به همین منظور ارایه شده است.
== مفاهیم ==
* گراف قویا همبند
به گراف جهت‌داری گویند که هر جفت راس آن از یکدیگر قابل دسترس باشد.
مانند شکل زیر:
[[پرونده:Strong graphhh.jpeg|بندانگشتی|وسط|400px |گراف قویا همبند]]
* مولفه قویا همبند:
مولفه قویا همبند یک گراف به بیشینه زیرمجموعه‌ای از
یعنی از هر جفت راس در آن مجموعه به یکدیگر مسیر مستقیم وجود دارد. مانند شکل زیر:
[[پرونده:Scc.png|بندانگشتی|وسط|400px|
== الگوریتم ==
فرض کنید گراف G داده شده است. در این الگوریتم
ابتدا یک رأس دلخواه از گراف را در نظر
* اگر به رأسی رسیدیم که قبلا در مسیر P وجود داشت، تمام
* اگر به رأسی رسیدیم که دیگر نتوانستیم مسیر P را ادامه دهیم، گره آخر مسیر P را هم در گراف H وهم در مسیر P حذف کرده و آن را به عنوان یک مولفه قویا همبند معرفی
این الگوریتم از الگوریتم [[جستجوی عمق اول]] و همچنین دو [[پشته]] برای نمایش مسیر P استفاده
* I[v]=
* I[v]=j هرگاه گره v اکنون در مسیر P باشد و S[j]=v.
* I[v]=c هرگاه مولفه قویا همبند شامل v حذف شده و با عدد c شماره گذاری شده باشد.
این الگوریتم شامل قسمت اصلی STRONG و قسمت بازگشتی DFS است:
سطر ۲۹ ⟵ ۲۷:
'''Algorithm'''STRONG(G)
'''Algorithm'''DFS(G)
{{پایان چپ‌چین}}
سطر ۴۹ ⟵ ۴۶:
=== قضیه ===
هنگامی که (STRONG(G متوقف شود هر رأس v ∈ V به مولفه قویا همبندی که توسط [I[v شماره گذاری شده است تعلق دارد. همچنین زمان و حافظه مصرفی (O(m+n
برای اثبات قضیه فوق
==
برای دیدن
==الگوریتم گابو==
'''الگوریتم چریَن- ملورن/ گابو''' در [[نظریه گراف]]، یک روش با [[پیچیدگی زمانی]] خطی برای یافتن مولفه‌های همبندی قوی در یک [[گراف جهتدار]] است<ref>{{citation
| last = Sedgewick | first = R.
| contribution = 19.8 Strong Components in Digraphs
| edition = 3rd
| location = Cambridge MA
| pages = 205–216
| publisher = Addison-Wesley
| title = Algorithms in Java, Part 5 – Graph Algorithms
year = 2004}}</ref>
. این الگوریتم در سال ۱۹۹۶ توسط جوزف چِریَن و{{سخ}}کورت ملورن<ref>{{citation
| last1 = Cheriyan | first1 = J.
| last2 = Mehlhorn | first2 = K. | author2-link = Kurt Mehlhorn
| doi = 10.1007/BF01940880
| journal = [[Algorithmica]]
| pages = 521–549
| title = Algorithms for dense graphs and networks on the random access computer
| volume = 15
| year = 1996}}</ref> ارائه شد و در سال 1999 توسط هارولد گابو<ref>{{citation
| last = Gabow | first = H.N.
| contribution = Searching (Ch 10.1)
| editor1-last = Gross | editor1-first = J. L.
| editor2-last = Yellen | editor2-first = J.
| pages = 953–984
| publisher = CRC Press
| title = Discrete Math. and its Applications: Handbook of Graph Theory
| volume = 25
| year = 2003}}</ref> بهبود یافت.{{سخ}}
الگوریتم گابو همانند الگوریتم مولفه‌های همبند قوی تارجان، تنها یک [[جستجوی عمق اول]] در گراف داده شده انجام می‌دهد،
و از یک [[پشته]] برای نگهداری گره‌هایی که{{سخ}}به مولفه‌ای اختصاص داده نشده‌اند استفاده می‌کند، و بعد از اختصاص دادن آخرین گره به مولفه همبندی، این گره‌ها را به یک مولفهٔ جدید منتقل می‌کند.{{سخ}}الگوریتم تارجان از یک آرایه با اندیس گره‌ها شامل اعداد پیش‌ترتیب استفاده می‌کند، که به ترتیب دیده شدن در جستجوی عمق اول مقداردهی شده‌اند.{{سخ}}از آرایهٔ پیش‌ترتیبی برای دانستن اینکه چه زمانی مولفهٔ همبندی جدید ایجا شود استفاده می‌گردد. الگوریتم گابو به جای استفاده از آرایه، از پشتهٔ دیگری به این منظور استفاده می‌کند.
== الگوریتم گابو ==
الگوریتم گابو با پشتیبانی دو پشتهٔ S و P یک جستجوی عمق اول بر روی گراف داده شدهٔ G انجام می‌دهد. پشتهٔ S تمامی گره‌هایی را تاکنون به یک مولفهٔ همبندی قوی{{سخ}}
اختصاص داده نشده‌اند، شامل می‌شود. گره‌ها در این پشته به ترتیبی که جستجوی عمق اول به آن می‌رسد قرار دارند. پشتهٔ P شامل گره‌هایی است که هنوز اختصاص آن‌ها به
مولفه‌های همبندی{{سخ}}قوی متفاوت از هم، تعیین نشده است. همچنین در الگوریتم از یک شمارندهٔ C که تعداد گره‌های مشاهده شده تاکنون است، برای محاسبهٔ اعداد پیش‌ترتیب گره‌ها استفاده می‌شود.{{سخ}}
هنگامی که جستجوی عمق اول به یک گره v می‌رسد، الگوریتم مراحل زیر را به ترتیب انجام می‌دهد:
# عدد پیش‌ترتیب v را برابر C قرار می‌دهد، و مقدار C را یکی افزایش می‌دهد.
# گره v را در پشتهٔ S و همینطور P قرار می‌دهد.
# برای هر یال از گره v به گره مجاور w:
#* اگر عدد پیش‌ترتیب w هنوز مقداردهی نشده، به طور بازگشتی جستجو را روی w انجام می‌دهد؛
#* در غیر اینصورت، اگر w هنوز به یک مولفهٔ همبندی قوی اختصاص داده نشده:
#** تا زمانی که عدد پیش‌ترتیب عنصر بالای پشته P، بزرگتر اکید عدد پیش‌ترتیب w است، عنصر بالای P را خارج می‌کند.
# اگر v عنصر بالای P بود:
#* عناصر بالای S را تا زمانی که v خارج شود، خارج کرده و این عناصر را به یک مولفهٔ همبندی اختصاص می‌دهد.
#* گره v را از P خارج می‌کند.
الگوریتم کلی شامل یک حلقه روی گره‌های گراف G است، که این جستجوی بازگشتی را برای گره‌هایی که هنوز عدد پیش‌ترتیب آن‌ها مقدار دهی نشده است، صدا می‌زند.
== منابع ==
{{پانویس}}
{{چپ‌چین}}
* [
{{پایان چپ‌چین}}
[[رده:الگوریتم‌ها]]
[[رده:الگوریتم‌های گراف]]
[[رده:همبندی گراف]]
| |||