Bridge (graph theory)
گراف تھیوری میں، پل، استھمس، کٹ ایج، یا کٹ آرک گراف کا ایک کنارہ ہے جس کے حذف ہونے سے گراف کے منسلک اجزاء کی تعداد میں اضافہ ہوتا ہے۔ اسی طرح، ایک کنارہ ایک پل ہے اگر اور صرف اس صورت میں جب یہ کسی سائیکل میں شامل نہ ہو۔ منسلک گراف کے لیے، ایک پل منفرد طور پر کٹ کا تعین کر سکتا ہے۔ ایک گراف کو بغیر پل یا استھمس سے پاک کہا جاتا ہے اگر اس میں پل نہ ہوں۔ اس قسم کے پل کو گراف تھیوری میں "پل" کے غیر متعلقہ معنی سے ممتاز کیا جانا چاہیے، ایک ذیلی گراف جو عمودی حصوں کے ایک مخصوص ذیلی سیٹ کے ذریعے باقی گراف سے الگ ہوتا ہے۔ پل دیکھیں۔ درخت اور جنگلات نوڈس کے ساتھ ایک گراف زیادہ تر پلوں پر مشتمل ہو سکتا ہے، کیونکہ اضافی کناروں کو شامل کرنے کے لیے ایک سائیکل بنانا ضروری ہے۔ بالکل پلوں والے گراف بالکل درخت ہوتے ہیں، اور وہ گراف جس میں ہر کنارے پر پل ہوتا ہے بالکل جنگل ہوتے ہیں۔ ہر غیر ہدایت شدہ گراف میں، عمودی حصوں پر ایک مساوات کا تعلق ہوتا ہے جس کے مطابق جب بھی ان کو جوڑنے والے دو کنارے-جداگانہ راستے ہوتے ہیں تو دو عمودی حصے ایک دوسرے سے متعلق ہوتے ہیں۔ (ہر سرے کا تعلق دو لمبائی-صفر راستوں کے ذریعے خود سے ہوتا ہے، جو ایک جیسے ہوتے ہیں لیکن اس کے باوجود کنارے سے جدا ہوتے ہیں۔) اس تعلق کی مساوات کی کلاسوں کو 2-کنارے سے منسلک اجزاء کہا جاتا ہے، اور گراف کے پل بالکل ایسے کنارے ہوتے ہیں جن کے اختتامی نکات مختلف اجزاء سے تعلق رکھتے ہیں۔ گراف کے برج بلاک ٹری میں ہر غیر معمولی جزو کے لیے ایک ورٹیکس اور ہر پل کے لیے ایک کنارہ ہوتا ہے۔ ورٹیکس کنیکٹیویٹی سے تعلق پلوں کا گہرا تعلق آرکچولیشن ورٹیکس کے تصور سے ہے، وہ ورٹیکس جو دوسرے ورٹیکس کے کسی جوڑے کے درمیان ہر راستے سے تعلق رکھتے ہیں۔ پل کے دو اختتامی نکات اظہار کے عمودی ہوتے ہیں جب تک کہ ان کی ڈگری 1 نہ ہو، حالانکہ غیر پل کے کنارے کے لیے یہ بھی ممکن ہو سکتا ہے کہ اختتامی نکات کے طور پر دو اظہار کے عمودی ہوں۔ برج لیس گرافوں کے متوازی طور پر 2-کنارے سے جڑے ہوئے ہونے کی وجہ سے، آرکچولیشن عمودی کے بغیر گراف 2-ورٹیکس سے جڑے ہوتے ہیں۔ کیوبک گراف میں، ہر کٹ ورٹیکس کم از کم ایک پل کا اختتامی نقطہ ہوتا ہے۔ برج لیس گراف ایک برج لیس گراف ہے جس میں کوئی پل نہیں ہے۔ مساوی شرائط یہ ہیں کہ گراف کے ہر جڑے ہوئے جزو میں ایک کھلا کان سڑنا ہوتا ہے، کہ ہر جڑا ہوا جزو 2 کنارے سے جڑا ہوا ہے، یا (رابنز تھیوریم کے مطابق) کہ ہر جڑے ہوئے جزو کا ایک مضبوط رخ ہوتا ہے۔ پلوں سے متعلق ایک اہم کھلا مسئلہ سائیکل ڈبل کور قیاس ہے، جو سیمور اور زیکیرس (1978 اور 1979، آزادانہ طور پر) کی وجہ سے ہے، جس میں کہا گیا ہے کہ ہر برج لیس گراف سادہ چکروں کے ایک کثیر سیٹ کو قبول کرتا ہے جس میں ہر کنارے پر بالکل دو بار مشتمل ہوتا ہے۔ ٹارجن کا پل تلاش کرنے کا الگورتھم گراف میں پلوں کو تلاش کرنے کے لیے پہلا لکیری ٹائم الگورتھم 1974 میں رابرٹ ٹارجن نے بیان کیا تھا۔ یہ مندرجہ ذیل مراحل انجام دیتا ہے: پھیلے ہوئے جنگل سے جڑوں والا جنگل بنانے کے لیے ایک پھیلا ہوا جنگل تلاش کریں۔ پہلے سے ترتیب میں جنگل سے گزریں اور نوڈس کو نمبر دیں۔ جنگل میں پیرنٹ نوڈس کی تعداد اب چائلڈ نوڈس سے کم ہے۔ پری آرڈر میں ہر نوڈ کے لیے (ہر نوڈ کو اس کے پری آرڈر نمبر کا استعمال کرتے ہوئے ظاہر کرتے ہوئے)، کریں: اس نوڈ کے لیے جنگل کی اولاد کی تعداد کا حساب لگائیں، اس کے بچوں کی اولاد کے مجموعے میں ایک کو شامل کرکے۔ کمپیوٹ، سب سے کم پری آرڈر لیبل جو ایک راستے سے قابل رسائی ہے جس کے لیے آخری کنارے کے علاوہ سب کچھ ذیلی درخت کے اندر رہتا ہے۔ یہ سیٹ کا کم از کم سیٹ ہے جو پری آرڈر لیبل پر مشتمل ہے، چائلڈ نوڈس کی اقدار اور نوڈس کے پری آرڈر لیبلز کے جو کناروں سے قابل رسائی ہیں جن کا تعلق نہیں ہے۔ اسی طرح، سب سے زیادہ پری آرڈر لیبل کا حساب لگائیں جو کسی راستے سے قابل رسائی ہو جس کے لیے آخری کنارے کے علاوہ سب کچھ ذیلی درخت کے اندر رہتا ہے۔ یہ سیٹ کا زیادہ سے زیادہ حصہ ہے جو پری آرڈر لیبل پر مشتمل ہے، چائلڈ نوڈس کی اقدار اور نوڈس کے پری آرڈر لیبلز کے جو کناروں سے قابل رسائی ہیں جن کا تعلق نہیں ہے۔ پیرنٹ نوڈ والے ہر نوڈ کے لیے، اگر اور پھر سے کنارے تک ایک پل ہے۔ زنجیر کے سڑنے کے ساتھ پل تلاش کرنا ایک بہت ہی آسان پل تلاش کرنے والا الگورتھم زنجیر کے سڑنے کا استعمال کرتا ہے۔ زنجیر کے سڑنے سے نہ صرف گراف کے تمام پلوں کا حساب لگانے کی اجازت ملتی ہے، بلکہ وہ G کے ہر کٹ ورٹیکس (اور G کے بلاک کٹ ٹری) کو پڑھنے کی بھی اجازت دیتے ہیں، جس سے 2-ایج-اور 2-ورٹیکس-کنیکٹوٹی کی جانچ کے لیے ایک عمومی فریم ورک ملتا ہے (جو لکیری ٹائم 3-ایج-اور 3-ورٹیکس-کنیکٹوٹی ٹیسٹ تک پھیلا ہوا ہے)۔ زنجیر کی سڑن کان کی خاص سڑن ہوتی ہے جو جی کے ڈی ایف ایس-ٹری ٹی پر منحصر ہوتی ہے اور اس کا حساب بہت آسانی سے لگایا جا سکتا ہے: ہر سرے کو غیر دیکھے ہوئے کے طور پر نشان زد کیا جائے۔ چڑھتے ہوئے DFS-نمبروں 1. n میں ہر ورٹیکس v کے لیے، ہر بیکج کو عبور کریں (یعنی۔ ہر کنارہ جو ڈی ایف ایس ٹری میں نہیں ہے) جو کہ وی سے منسلک ہوتا ہے اور ٹری ایجز کے راستے پر واپس ٹی کی جڑ تک جاتا ہے، پہلے سرے پر رکتا ہے جسے وزٹ کے طور پر نشان زد کیا گیا ہے۔ اس طرح کے سفر کے دوران، ہر گزرتے ہوئے سرے کو وزٹ کے طور پر نشان زد کیا جاتا ہے۔ اس طرح، ایک ٹریورسل تازہ ترین v پر رکتا ہے اور یا تو ایک ہدایت شدہ راستہ یا سائیکل بناتا ہے، جس کا آغاز v سے ہوتا ہے۔ ہم اس راستے یا سائیکل کو سلسلہ کہتے ہیں۔ اس طریقہ کار کے ذریعے پائی جانے والی ith زنجیر کو Ci کہا جاتا ہے۔ C = C1، C2،. اس کے بعد G کا ایک سلسلہ سڑنا ہے۔ مندرجہ ذیل خصوصیات پھر G کی کئی خصوصیات کو C سے مؤثر طریقے سے پڑھنے کی اجازت دیتی ہیں، بشمول G کے تمام پل۔ آئیے C ایک سادہ منسلک گراف G = (V، E) کا سلسلہ سڑنا ہے۔ جی 2 کنارے سے جڑا ہوا ہے اگر اور صرف اس صورت میں جب سی پارٹیشن ای میں زنجیراں ہوں۔ جی میں ایک کنارے ای ایک پل ہے اگر اور صرف اس صورت میں جب ای سی میں کسی زنجیر میں موجود نہ ہو۔ اگر جی 2 کنارے سے جڑا ہوا ہے، تو سی کان کی سڑن ہے۔ G 2-ورٹیکس سے جڑا ہوا ہے اگر اور صرف اس صورت میں جب G میں کم از کم ڈگری 2 ہو اور C1 C میں واحد سائیکل ہو۔ 2 کنارے سے جڑے گراف G میں A ورٹیکس V ایک کٹ ورٹیکس ہے اگر اور صرف اس صورت میں جب V C-C1 میں کسی سائیکل کا پہلا ورٹیکس ہو۔ اگر G 2-ورٹیکس سے جڑا ہوا ہے، تو C ایک کھلے کان کا سڑنا ہے۔ بائی کنیکٹڈ جزو کٹ (گراف تھیوری) نوٹس گراف کنیکٹوٹی بھی دیکھیں۔