الگوریتم مؤلفه قوی مبتنی بر مسیر: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات: انتقال 1 پیوند میان‌ویکی به d:q7144620 در ویکی‌داده |
Tarvig elm (بحث | مشارکت‌ها) ایجاد یک مقاله نو از طریق ایجادگر برچسب: منبع‌دهی نادرست (پخ) |
||
خط ۱:
'''الگوریتم Path-based strong component'''
در [[نظریه گراف]] برای پیدا کردن [[مولفه‌های قویا همبند]] یک [[گراف جهتدار]] می‌توان از [[الگوریتمPath-based strong component]] استفاده کرد. قبل از این الگوریتم، [[الگوریتم کساراجو]] و [[الگوریتم تارجان]] نیز به همین منظور ارایه شده است.
== مفاهیم ==
* گراف قویا همبند
به گراف جهت‌داری گویند که هر جفت راس آن از یکدیگر قابل دسترس باشد.
مانند شکل زیر:
[[پرونده:Strong graphhh.jpeg|بندانگشتی|وسط|400px |گراف قویا همبند]]
*مولفه قویا همبند:
مولفه قویا همبند یک گراف به بیشینه زیرمجموعه‌ای از راس ها گویند که قویا همبند هستند.
یعنی از هر جفت راس در آن مجموعه به یکدیگر مسیر مستقیم وجود دارد. مانند شکل زیر:
[[پرونده:Scc.png|بندانگشتی|وسط|400px|مولفه های قویا همبند]]
== الگوریتم ==
فرض کنید گراف G داده شده است. در این الگوریتم رأس‌های گراف را از 1 تا n و مولفه‌های قویا همبند را با شروع از n+1 شماره‌گذاری می‌کنیم. همچنین در این الگوریتم گراف H را که در ابتدا همان گراف G می‌باشد در نظر می‌گیریم و در این گراف مسیر P را به صورت زیر می‌سازیم:
ابتدا یک رأس دلخواه از گراف را در نظر می‌گیریم و از این رأس در جهت کاملا دلخواه حرکت می‌کنیم تا یکی از دو حالت زیر رخ دهد:
*اگر به رأسی رسیدیم که قبلا در مسیر P وجود داشت، تمام گره‌های بین این رأس که تا کنون پیموده شده است را هم در گراف H و هم در مسیر p منقبض می‌کنیم. یعنی همه آن ها را به عنوان یک رأس در نظر می‌گیریم.
*اگر به رأسی رسیدیم که دیگر نتوانستیم مسیر P را ادامه دهیم، گره آخر مسیر P را هم در گراف H وهم در مسیر P حذف کرده و آن را به عنوان یک مولفه قویا همبند معرفی می‌کنیم.
این الگوریتم از الگوریتم [[جستجوی عمق اول]] و همچنین دو [[پشته]] برای نمایش مسیر P استفاده می‌کند. پشته S که شامل دنباله رأس‌های مسیر P است و پشته B که شامل کران‌های رأس‌های منقبض شده است. در این الگوریتم آرایه I نیز وجود دارد که هم اندیس پشته S را و هم شماره مولفه قویا همبند را ذخیره می‌کند. به عبارت دقیق تر این ارایه به صورت زیر تعریف می‌شود:
*I[v]=0 هرگاه گره v در مسیر P نباشد.
*I[v]=j هرگاه گره v اکنون در مسیر P باشد و S[j]=v.
*I[v]=c هرگاه مولفه قویا همبند شامل v حذف شده و با عدد c شماره گذاری شده باشد.
این الگوریتم شامل قسمت اصلی STRONG و قسمت بازگشتی DFS است:
{{چپ‌چین}}
'''Algorithm'''STRONG(G)
1 empty stacks S and B
2 '''for''' v ∈ V do I[v]=0
3 c=n
4 '''for''' v ∈ V do if I[v]=0 then DFS(v)
'''Algorithm'''DFS(G)
1 PUSH(v,S);I[v]=TOP(S);PUSH(I[v],B);/*add v to the end of P*/
2 '''for''' edges (v,w) ∈ E do
3 ''' if '''I[w]=0 then DFS(w)
4 '''else''' /*contract if necessary*/
5 '''while''' I[w]<B[TOP(B)] do POP(B)
6 '''if ''' I[v]=B[TOP(B)''' then'''{/*number vertices of the next strong component*/
7 POP(B);increase c by 1
8 '''while''' I[v]≤TOP(S) do I[POP(S)]=c}
{{پایان چپ‌چین}}
در قضیه زیر برهان درستی و همچنین پیچیدگی این الگوریتم آمده است:
=== قضیه ===
هنگامی که (STRONG(G متوقف شود هر رأس v ∈ V به مولفه قویا همبندی که توسط [I[v شماره گذاری شده است تعلق دارد. همچنین زمان و حافظه مصرفی (O(m+n می‌باشند.
برای اثبات قضیه فوق می‌توانید به [1] مراجعه کنید.
== الگوریتم‌های مرتبط ==
برای دیدن الگوریتم‌های مرتبط با این الگوریتم میتوانید به [[الگوریتم کساراجو]] و [[Tarjan's strongly connected components algorithm]] مراجعه کنید.
== منابع ==
{{چپ‌چین}}
*[1]Path-based depth-first search for strong and biconnected components. Harold N. Gabow
{{پایان چپ‌چین}}
| |||