Weak component
گراف تھیوری میں، ایک ہدایت شدہ گراف کے کمزور اجزاء گراف کے عمودی حصوں کو ذیلی سیٹوں میں تقسیم کرتے ہیں جو مکمل طور پر رسائی کے لحاظ سے ترتیب دیے جاتے ہیں۔ وہ عمودی سیٹ کی بہترین تقسیم بناتے ہیں جو مکمل طور پر اس طرح ترتیب دی جاتی ہے۔ تعریف کمزور اجزاء کی تعریف 1972 کے ایک مقالے میں رونالڈ گراہم، ڈونلڈ نوتھ، اور (بعد از مرگ) تھیوڈور موٹزکن نے ایک ہدایت شدہ گراف کے مضبوطی سے جڑے ہوئے اجزاء سے مشابہت کے ذریعے کی تھی، جو گراف کے عمودی حصوں کو ذیلی سیٹوں میں بہترین ممکنہ تقسیم بناتے ہیں جو جزوی طور پر رسائی کے لحاظ سے ترتیب دیے گئے ہیں۔ اس کے بجائے، انہوں نے کمزور اجزاء کو عمودی حصوں کی سب سیٹوں میں بہترین تقسیم کے طور پر بیان کیا جو مکمل طور پر ان کے ذریعہ ترتیب دی گئی ہیں۔ مزید تفصیل سے، کسی بھی ہدایت شدہ گراف کے عمودی حصوں پر چار ہم آہنگی تعلقات کے امتزاج کے ذریعے کمزور اجزاء کی وضاحت کرتا ہے، جسے یہاں اس طرح ظاہر کیا گیا ہے۔ کسی بھی دو عمودی حصوں اور گراف کے لیے، اگر اور صرف اس صورت میں جب ہر ایک عمودی حصہ دوسرے سے قابل رسائی ہو: گراف میں جانے اور جانے کے راستے موجود ہوں۔ تعلق ایک مساوات کا تعلق ہے، اور اس کی مساوات کی کلاسیں گراف کے مضبوطی سے جڑے ہوئے اجزاء کی وضاحت کے لیے استعمال ہوتی ہیں۔ کسی بھی دو عمودی اور گراف کے لیے، اگر اور صرف اس صورت میں جب کوئی بھی عمودی دوسرے سے قابل رسائی نہ ہو: گراف میں دونوں سمتوں میں راستے موجود نہیں ہیں۔ کسی بھی دو عمودی اور گراف کے لیے، اگر اور صرف اس صورت میں جب دونوں میں سے کوئی ایک ہو۔ یعنی، ان عمودی کے درمیان دو طرفہ تعلق ہو سکتا ہے، یا وہ باہمی طور پر ناقابل رسائی ہو سکتے ہیں، لیکن ان کا یک طرفہ تعلق نہ بھی ہو سکتا ہے۔ رشتہ کو عارضی بندش کے طور پر بیان کیا جاتا ہے یعنی، جب عمودی سلسلے کی ترتیب ہوتی ہے، اس طرح شروع ہوتی ہے اور ختم ہوتی ہے کہ ترتیب میں ہر مسلسل جوڑا متعلق ہوتا ہے تو پھر ایک مساوات کا رشتہ ہوتا ہے: ہر عمودی خود سے متعلق ہوتا ہے (کیونکہ یہ لمبائی صفر کے راستوں سے دونوں سمتوں میں خود تک پہنچ سکتا ہے)، کوئی بھی دو عمودی جو اس سے متعلق ہوتے ہیں اس رشتے کو تبدیل کیے بغیر ایک دوسرے کے لیے تبدیل کیے جا سکتے ہیں (کیونکہ یہ ہم آہنگی کے تعلقات سے بنا ہے اور یہ ایک عارضی تعلق ہے (کیونکہ یہ کسی دوسرے رشتے کی عارضی بندش ہے)۔ کسی بھی مساوات کے تعلق کی طرح، اس کا استعمال گراف کے عمودی حصوں کو مساوات کی کلاسوں، عمودی حصوں کے ذیلی سیٹوں میں تقسیم کرنے کے لیے کیا جا سکتا ہے تاکہ دو عمودی حصوں کا تعلق صرف اس صورت میں ہو جب وہ ایک ہی مساوات کی کلاس سے تعلق رکھتے ہوں۔ یہ مساوات کی کلاسیں دی گئی تعریف کے کمزور اجزاء ہیں۔ گراہم، نوتھ اور موٹزکن کی اصل تعریف مساوی ہے لیکن کچھ مختلف طریقے سے وضع کی گئی ہے۔ ایک ہدایت کو دیکھتے ہوئے وہ پہلے عارضی بندش کے تکمیل گراف کے طور پر ایک اور گراف بناتے ہیں جیسا کہ بیان کیا گیا ہے، کناروں کی نمائندگی کرتے ہیں، عمودی کے جوڑے جو کسی راستے سے جڑے نہیں ہیں۔ پھر، دو عمودی ایک ہی کمزور جزو سے تعلق رکھتے ہیں جب یا تو وہ ایک ہی مضبوطی سے جڑے ہوئے جزو سے تعلق رکھتے ہیں یا جیسا کہ گراہم، نوتھ اور موٹزکن ثابت کرتے ہیں، یہ شرط ایک مساوات کی وضاحت کرتی ہے جس کی وضاحت اوپر کی گئی ہے۔ ان تعریفوں کے مطابق، ایک ہدایت شدہ گراف کو کمزور طور پر جڑا ہوا کہا جاتا ہے اگر اس میں بالکل ایک کمزور جزو ہو۔ اس کا مطلب یہ ہے کہ اس کے عمودی حصوں کو دو ذیلی حصوں میں تقسیم نہیں کیا جا سکتا، اس طرح کہ پہلے ذیلی حصے کے تمام عمودی حصے دوسرے ذیلی حصے کے تمام عمودی حصوں تک پہنچ سکتے ہیں، لیکن اس طرح کہ دوسرے ذیلی حصے کا کوئی بھی عمودی حصہ پہلے ذیلی حصے کے کسی بھی عمودی حصے تک نہیں پہنچ سکتا۔ یہ ادب میں کمزور کنیکٹوٹی کے دیگر تصورات سے مختلف ہے، جیسے کہ کنیکٹوٹی اور بنیادی غیر منسلک گراف میں اجزاء، جس کے لیے نوتھ متبادل اصطلاحات کی خصوصیات تجویز کرتا ہے۔ اگر اور یہ ایک ہدایت شدہ گراف کے دو کمزور اجزاء ہیں، تو یا تو تمام عمودی نقاط گراف میں راستوں کے ذریعے تمام عمودی نقاط تک پہنچ سکتے ہیں، یا تمام عمودی نقاط تمام عمودی نقاط تک پہنچ سکتے ہیں۔ تاہم، ان دونوں اجزاء کے درمیان دونوں سمتوں میں رسائ کے تعلقات موجود نہیں ہو سکتے۔ لہذا، ہم کمزور اجزاء پر ایک ترتیب کی وضاحت کر سکتے ہیں، جس کے مطابق جب تمام عمودی تمام عمودی تک پہنچ سکتے ہیں۔ تعریف کے مطابق، یہ ایک غیر متناسب تعلق ہے (دو عناصر کا تعلق صرف ایک سمت میں ہو سکتا ہے، دوسرے میں نہیں) اور یہ رسائی کی منتقلی سے ایک عارضی تعلق ہونے کی خاصیت کو وراثت میں حاصل کرتا ہے۔ لہذا، یہ کمزور اجزاء پر کل ترتیب کی وضاحت کرتا ہے۔ یہ عمودی حصوں کی مکمل طور پر ترتیب شدہ عمودی حصوں کے سیٹ میں بہترین ممکنہ تقسیم ہے جو کمزور اجزاء پر اس ترتیب کو متبادل طور پر عمودی حصوں پر ایک کمزور ترتیب کے طور پر سمجھا جا سکتا ہے، اس خاصیت کے ساتھ کہ جب کمزور ترتیب میں ہوتا ہے تو وہاں لازمی طور پر ایک راستہ موجود ہوتا ہے لیکن اس سے نہیں ہوتا ہے۔ تاہم، یہ اس کمزور ترتیب کی مکمل خصوصیت نہیں ہے، کیونکہ دو عمودی حصے اور ہر ایک کے طور پر ایک ہی کمزور جزو سے تعلق رکھتے ہوئے اسی رسائی کی ترتیب ہو سکتی ہے۔ ہر کمزور جزو مضبوطی سے جڑا ہوا ہے۔ اگر کسی دیئے گئے گراف کے مضبوطی سے جڑے ہوئے اجزاء کو سنگل عمودی حصوں سے معاہدہ کیا جاتا ہے، تو ایک ہدایت شدہ ایسائکلک گراف (دیئے گئے گراف کا) تیار ہوتا ہے، اور پھر یہ سنکشیپن ٹپوولوجیکل طور پر ترتیب دیا جاتا ہے، پھر ہر کمزور جزو لازمی طور پر ایک مسلسل تسلسل کے طور پر ظاہر ہوتا ہے۔ کمزور اجزاء کے لیے الگورتھم اس ترتیب میں مضبوطی سے جڑے ہوئے اجزاء کو پیدا کرتا ہے، اور ان اجزاء کی تقسیم کو برقرار رکھتا ہے جو اب تک ان کے محرک ذیلی گراف کے کمزور اجزاء میں پیدا ہوئے ہیں۔ تمام اجزاء تیار ہونے کے بعد، یہ تقسیم پورے کے کمزور اجزاء کی وضاحت کرے گی۔ موجودہ تقسیم کو اسٹیک میں کمزور اجزاء میں برقرار رکھنا آسان ہے، جس میں ہر کمزور جزو اضافی طور پر اس کے، مضبوطی سے جڑے ہوئے اجزاء کی ایک فہرست کو برقرار رکھتا ہے جس میں اسی کمزور جزو میں دوسرے مضبوطی سے جڑے ہوئے اجزاء سے آنے والے کنارے نہیں ہوتے ہیں، جس میں حال ہی میں تیار کردہ ماخذ پہلے ہوتا ہے۔ ہر نیا تیار کردہ مضبوطی سے جڑا ہوا جزو اپنے طور پر ایک نیا کمزور جزو تشکیل دے سکتا ہے، یا اسٹیک کے اوپری حصے کے قریب پہلے سے تعمیر شدہ کچھ کمزور اجزاء کے ساتھ ضم ہو سکتا ہے، جن کے لیے یہ سب تک نہیں پہنچ سکتا۔ اس طرح، الگورتھم مندرجہ ذیل کارکردگی کا مظاہرہ کرتا ہے۔ کمزور اجزاء کے ایک خالی اسٹیک کو شروع کریں، ہر ایک اس کے ماخذ اجزاء کی فہرست سے وابستہ ہے۔ ٹورجن کے مضبوطی سے جڑے ہوئے اجزاء کے الگورتھم کا استعمال کریں تاکہ دیئے گئے گراف کے مضبوطی سے جڑے ہوئے اجزاء کو ٹوپولوجیکل ترتیب کے برعکس تیار کیا جا سکے۔ جب ہر مضبوطی سے جڑا ہوا جزو تیار کیا جاتا ہے، تو اس کے ساتھ درج ذیل مراحل انجام دیں: اگرچہ اسٹیک خالی نہیں ہے اور اسٹیک کے اوپری کمزور جزو کے کنارے نہیں ہیں، اس جزو کو اسٹیک سے پاپ کریں۔ اگر اسٹیک اب بھی خالی نہیں ہے، اور اس کے اوپری کمزور جزو کے کچھ ذرائع کناروں سے متاثر نہیں ہوتے ہیں تو اس جزو کو اسٹیک سے دوبارہ پاپ کریں۔ ذرائع کے طور پر موجود ایک نیا کمزور بنائیں اور پاپ کیے گئے اوپری جزو سے تمام غیر ہٹ ذرائع بنائیں، اور اسٹیک پر دبائیں۔ ہر ٹیسٹ کے لیے کہ آیا کسی کمزور جزو سے ٹکرانے والے کناروں کو مستقل وقت میں انجام دیا جا سکتا ہے جب ہم اس کنارے کے ہدف کے جزو کا موازنہ دوسرے سے اوپر والے جزو کے پہلے ماخذ سے کر کے، حال ہی میں تیار کردہ پہلے مضبوطی سے جڑے ہوئے جزو کا کنارہ تلاش کر لیں۔ اسٹیک پر۔ حوالہ جات گراف کنیکٹوٹی گراف تھیوری آبجیکٹ