الگوریتم مؤلفه قوی مبتنی بر مسیر ( به انگلیسی: Path - based strong component algorithm ) در نظریه گراف برای پیدا کردن مولفه های قویا همبند یک گراف جهت دار استفاده می شود. قبل از این الگوریتم، الگوریتم کساراجو و الگوریتم تارژان نیز به همین منظور ارائه شده است.
• گراف قویا همبند
به گراف جهت داری گویند که هر جفت راس آن از یکدیگر قابل دسترس باشد. مانند شکل زیر:
• مؤلفه قویا همبند:
مولفه قویا همبند یک گراف به بیشینه زیرمجموعه ای از رأس ها گویند که قویا همبند هستند. یعنی از هر جفت راس در آن مجموعه به یکدیگر مسیر مستقیم وجود دارد. مانند شکل زیر:
فرض کنید گراف G داده شده است. در این الگوریتم رأس های گراف را از ۱ تا n و مؤلفه های قویا همبند را با شروع از n+۱ شماره گذاری می کنیم. همچنین در این الگوریتم گراف H را که در ابتدا همان گراف G می باشد در نظر می گیریم و در این گراف مسیر P را به صورت زیر می سازیم: ابتدا یک رأس دلخواه از گراف را در نظر می گیریم و از این رأس در جهت کاملاً دلخواه حرکت می کنیم تا یکی از دو حالت زیر رخ دهد:
• اگر به رأسی رسیدیم که قبلاً در مسیر P وجود داشت، تمام گره های بین این رأس که تاکنون پیموده شده است را هم در گراف H و هم در مسیر p منقبض می کنیم. یعنی همه آن ها را به عنوان یک رأس در نظر می گیریم.
• اگر به رأسی رسیدیم که دیگر نتوانستیم مسیر P را ادامه دهیم، گره آخر مسیر P را هم در گراف H وهم در مسیر P حذف کرده و آن را به عنوان یک مؤلفه قویا همبند معرفی می کنیم.
این الگوریتم از الگوریتم جستجوی عمق اول و همچنین دو پشته برای نمایش مسیر P استفاده می کند. پشته S که شامل دنباله رأس های مسیر P است و پشته B که شامل کران های رأس های منقبض شده است. در این الگوریتم آرایه I نیز وجود دارد که هم اندیس پشته S را و هم شماره مؤلفه قویا همبند را ذخیره می کند. به عبارت دقیق تر این ارائه به صورت زیر تعریف می شود:
• I=۰ هرگاه گره v در مسیر P نباشد.
• I=j هرگاه گره v اکنون در مسیر P باشد و S=v.
• I=c هرگاه مؤلفه قویا همبند شامل v حذف شده و با عدد c شماره گذاری شده باشد.
این الگوریتم شامل قسمت اصلی STRONG و قسمت بازگشتی DFS است:
AlgorithmSTRONG ( G ) ۱ empty stacks S and B ۲ for v ∈ V do I=۰ ۳ c=n ۴ for v ∈ V do if I=۰ then DFS ( v ) AlgorithmDFS ( G ) ۱ PUSH ( v, S ) ; I=TOP ( S ) ; PUSH ( I, B ) ; /*add v to the end of P*/ ۲ for edges ( v, w ) ∈ E do ۳ if I=۰ then DFS ( w ) ۴ else /*contract if necessary*/ ۵ while I< B do POP ( B ) ۶ if I=B=c} در قضیه زیر برهان درستی و همچنین پیچیدگی این الگوریتم آمده است:
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف• گراف قویا همبند
به گراف جهت داری گویند که هر جفت راس آن از یکدیگر قابل دسترس باشد. مانند شکل زیر:
• مؤلفه قویا همبند:
مولفه قویا همبند یک گراف به بیشینه زیرمجموعه ای از رأس ها گویند که قویا همبند هستند. یعنی از هر جفت راس در آن مجموعه به یکدیگر مسیر مستقیم وجود دارد. مانند شکل زیر:
فرض کنید گراف G داده شده است. در این الگوریتم رأس های گراف را از ۱ تا n و مؤلفه های قویا همبند را با شروع از n+۱ شماره گذاری می کنیم. همچنین در این الگوریتم گراف H را که در ابتدا همان گراف G می باشد در نظر می گیریم و در این گراف مسیر P را به صورت زیر می سازیم: ابتدا یک رأس دلخواه از گراف را در نظر می گیریم و از این رأس در جهت کاملاً دلخواه حرکت می کنیم تا یکی از دو حالت زیر رخ دهد:
• اگر به رأسی رسیدیم که قبلاً در مسیر P وجود داشت، تمام گره های بین این رأس که تاکنون پیموده شده است را هم در گراف H و هم در مسیر p منقبض می کنیم. یعنی همه آن ها را به عنوان یک رأس در نظر می گیریم.
• اگر به رأسی رسیدیم که دیگر نتوانستیم مسیر P را ادامه دهیم، گره آخر مسیر P را هم در گراف H وهم در مسیر P حذف کرده و آن را به عنوان یک مؤلفه قویا همبند معرفی می کنیم.
این الگوریتم از الگوریتم جستجوی عمق اول و همچنین دو پشته برای نمایش مسیر P استفاده می کند. پشته S که شامل دنباله رأس های مسیر P است و پشته B که شامل کران های رأس های منقبض شده است. در این الگوریتم آرایه I نیز وجود دارد که هم اندیس پشته S را و هم شماره مؤلفه قویا همبند را ذخیره می کند. به عبارت دقیق تر این ارائه به صورت زیر تعریف می شود:
• I=۰ هرگاه گره v در مسیر P نباشد.
• I=j هرگاه گره v اکنون در مسیر P باشد و S=v.
• I=c هرگاه مؤلفه قویا همبند شامل v حذف شده و با عدد c شماره گذاری شده باشد.
این الگوریتم شامل قسمت اصلی STRONG و قسمت بازگشتی DFS است:
AlgorithmSTRONG ( G ) ۱ empty stacks S and B ۲ for v ∈ V do I=۰ ۳ c=n ۴ for v ∈ V do if I=۰ then DFS ( v ) AlgorithmDFS ( G ) ۱ PUSH ( v, S ) ; I=TOP ( S ) ; PUSH ( I, B ) ; /*add v to the end of P*/ ۲ for edges ( v, w ) ∈ E do ۳ if I=۰ then DFS ( w ) ۴ else /*contract if necessary*/ ۵ while I< B do POP ( B ) ۶ if I=B=c} در قضیه زیر برهان درستی و همچنین پیچیدگی این الگوریتم آمده است:
