Ear decomposition
گراف تھیوری میں، غیر ہدایت شدہ گراف G کا کان ایک راستہ P ہے جہاں راستے کے دو اختتامی نکات موافق ہو سکتے ہیں، لیکن جہاں بصورت دیگر کناروں یا چوٹیوں کی تکرار کی اجازت نہیں ہے، لہذا P کے ہر اندرونی سرے کی ڈگری G میں دو ہوتی ہے۔ غیر ہدایت شدہ گراف G کا کان سڑنا اس کے کناروں کے سیٹ کو کانوں کی ترتیب میں تقسیم کرنا ہے، جیسے کہ ہر کان کے ایک یا دو اختتامی نکات ترتیب میں پہلے کانوں سے تعلق رکھتے ہیں اور اس طرح کہ ہر کان کے اندرونی عمودی کسی پہلے کان سے تعلق نہیں رکھتے ہیں۔ مزید برآں، زیادہ تر معاملات میں ترتیب میں پہلا کان ایک چکر ہونا چاہیے۔ کھلے کان کا سڑنا یا کان کا مناسب سڑنا ایک کان کا سڑنا ہے جس میں پہلے کے بعد ہر کان کے دو اختتامی نکات ایک دوسرے سے الگ ہوتے ہیں۔ کان کے سڑنے کو کئی اہم گراف کلاسوں کی خصوصیت کے لیے اور موثر گراف الگورتھم کے حصے کے طور پر استعمال کیا جا سکتا ہے۔ انہیں گراف سے لے کر میٹروئڈز تک عام کیا جا سکتا ہے۔ گراف کی کلاسوں کی خصوصیت گراف کی کئی اہم کلاسوں کو مخصوص قسم کے کان کے سڑنے والے گراف کے طور پر نمایاں کیا جا سکتا ہے۔ گراف کنیکٹوٹی ایک گراف k-ورٹیکس سے منسلک ہوتا ہے اگر کسی بھی (k−1) عمودی کو ہٹانے سے منسلک ذیلی گراف نکل جاتا ہے، اور k-کنارے سے منسلک ہوتا ہے اگر کسی بھی (k−1) کناروں کو ہٹانے سے منسلک ذیلی گراف نکل جاتا ہے۔ مندرجہ ذیل نتیجہ اس کی وجہ سے ہے: ایک گراف 2-ورٹیکس سے جڑا ہوا ہے اگر اور صرف اس صورت میں جب اس میں کھلے کان کا سڑنا ہو۔ مندرجہ ذیل نتیجہ اس کی وجہ سے ہے: ایک گراف 2 کنارے سے جڑا ہوا ہے اگر اور صرف اس صورت میں جب اس میں کان کا سڑنا ہو۔ دونوں صورتوں میں کانوں کی تعداد لازمی طور پر دیئے گئے گراف کے سرکٹ رینک کے برابر ہوتی ہے۔ رابنز نے رابنز تھیوریم کو ثابت کرنے کے لیے ایک آلے کے طور پر 2 کنارے سے منسلک گرافوں کے کان کے سڑنے کو متعارف کرایا، کہ یہ بالکل وہی گراف ہیں جنہیں مضبوطی سے منسلک واقفیت دی جا سکتی ہے۔ کان کے سڑنے پر وٹنی اور رابنز کے اہم کام کی وجہ سے، کان کے سڑنے کو بعض اوقات وٹنی-رابنز کی ترکیب بھی کہا جاتا ہے۔ کان کا غیر الگ ہونے والا سڑنا ایک کھلے کان کا سڑنا ہے جس میں، صرف ایک رعایت کے ساتھ ہر ورٹیکس v کے لیے، v کا ایک پڑوسی ہوتا ہے جس کی سڑنے میں پہلی ظاہری شکل v کے پہلے ظہور کے مقابلے بعد کے کان میں ہوتی ہے۔ اس قسم کے کان کے سڑنے کو وٹنی کے نتیجے کو عام کرنے کے لیے استعمال کیا جا سکتا ہے: 3-ورٹیکس کے ساتھ ایک گراف 3-ورٹیکس سے منسلک ہوتا ہے اگر اور صرف اس صورت میں جب G میں کان کا غیر الگ ہونے والا سڑنا ہو۔ اگر اس طرح کا سڑنا موجود ہے، تو اسے G کے کسی خاص کنارے uv کے حوالے سے اس طرح سے منتخب کیا جا سکتا ہے کہ u پہلے کان میں ہو، v آخری کان میں ایک سے زیادہ کنارے والا نیا ورٹیکس ہو، اور uv ایک کنارے والا کان ہو۔ یہ نتیجہ سب سے پہلے واضح طور پر بیان کیا گیا تھا، لیکن جیسا کہ بیان کیا گیا ہے، یہ 1971 کے پی ایچ ڈی کے نتیجے کے برابر ہے۔ لی مونڈشین کا مقالہ۔ زیادہ سے زیادہ پلانر گراف کے غیر الگ ہونے والے کان کے سڑنے سے قریب سے متعلق ڈھانچے، جنہیں کینونکل آرڈرنگ کہا جاتا ہے، بھی گراف ڈرائنگ میں ایک معیاری ٹول ہیں۔ ہدایت شدہ گرافوں کا مضبوط رابطہ مندرجہ بالا تعریفیں ہدایت شدہ گرافوں پر بھی لاگو کی جا سکتی ہیں۔ اس کے بعد کان ایک ہدایت شدہ راستہ ہوگا جہاں تمام اندرونی چوٹیوں میں 1 کے برابر انڈیگری اور آؤٹ ڈگری ہوتی ہے۔ ایک ہدایت شدہ گراف مضبوطی سے جڑا ہوا ہے اگر اس میں ہر سرے سے ہر دوسرے سرے تک ایک ہدایت شدہ راستہ ہو۔ پھر ہمارے پاس مندرجہ ذیل نظریہ ہے: ایک ہدایت شدہ گراف مضبوطی سے جڑا ہوا ہے اگر اور صرف اس صورت میں جب اس میں کان کا سڑنا ہو۔ عنصر-اہم گراف کان کی سڑنا عجیب ہے اگر اس کے ہر کان میں عجیب تعداد میں کناروں کا استعمال کیا جائے۔ فیکٹر کریٹیکل گراف ایک ایسا گراف ہے جس میں عمودی حصوں کی ایک عجیب تعداد ہوتی ہے، جیسے کہ ہر عمودی v کے لیے، اگر v کو گراف سے ہٹا دیا جائے تو باقی عمودی حصوں کا ایک کامل ملاپ ہوتا ہے۔ پتہ چلا کہ: ایک گراف G عنصر اہم ہے اگر اور صرف اس صورت میں جب G میں کان کا عجیب سا سڑنا ہو۔ زیادہ عام طور پر، اس کا نتیجہ کسی بھی گراف G میں کم سے کم برابر کانوں کے ساتھ کان کی سڑن کو تلاش کرنا ممکن بناتا ہے۔ سلسلہ متوازی گراف ایک درخت کے کان کی سڑنا ایک مناسب کان کی سڑنا ہے جس میں پہلا کان ایک کنارے پر ہوتا ہے اور اس کے بعد کے ہر کان کے لیے ایک کان ہوتا ہے، جس پر دونوں اختتامی نکات ہوتے ہیں۔ گھونسلے والے کان کا سڑنا درخت کے کان کا سڑنا ہے جس طرح، ہر کان کے اندر، دوسرے کانوں کے اختتامی نکات کے جوڑوں کا مجموعہ جو گھونسلے والے وقفوں کے ایک سیٹ کے اندر ہوتا ہے۔ سیریز متوازی گراف ایک ایسا گراف ہے جس میں دو نامزد ٹرمینلز s اور t ہوتے ہیں جنہیں چھوٹے سیریز متوازی گرافوں کو دو میں سے کسی ایک طریقے سے ملا کر بار بار بنایا جا سکتا ہے: سیریز کمپوزیشن (ایک چھوٹے گراف سے ایک ٹرمینل کی شناخت دوسرے چھوٹے گراف سے ایک ٹرمینل کے ساتھ کرنا، اور دوسرے دو ٹرمینلز کو مشترکہ گراف کے ٹرمینلز کے طور پر رکھنا) اور متوازی کمپوزیشن (دو چھوٹے گرافوں سے ٹرمینلز کے دونوں جوڑوں کی شناخت کرنا)۔ مندرجہ ذیل نتیجہ اس کی وجہ سے ہے: 2-ورٹیکس سے منسلک گراف سیریز متوازی ہے اگر اور صرف اس صورت میں جب اس میں گھونسلے والے کان کا سڑنا ہو۔ مزید برآں، 2-ورٹیکس سے منسلک سیریز-متوازی گراف کے کسی بھی کھلے کان کے سڑنے کو گھونسلہ بنایا جانا چاہیے۔ نتیجہ کو سیریز متوازی گرافوں تک بڑھایا جا سکتا ہے جو کھلے کان کے سڑنے کا استعمال کرتے ہوئے 2-ورٹیکس سے منسلک نہیں ہیں جو دونوں ٹرمینلز کے درمیان راستے سے شروع ہوتے ہیں۔ میٹرائڈز کان کے سڑنے کے تصور کو گراف سے لے کر میٹرائڈز تک بڑھایا جا سکتا ہے۔ میٹرائڈ کے کان کے سڑنے کو میٹرائڈ کے سرکٹس کی ایک ترتیب کے طور پر بیان کیا گیا ہے، جس میں دو خصوصیات ہیں: ترتیب میں ہر سرکٹ کا پچھلے سرکٹس کے ساتھ ایک غیر خالی چوراہا ہوتا ہے، اور ترتیب میں ہر سرکٹ ایک سرکٹ ہی رہتا ہے چاہے ترتیب میں پچھلے تمام سرکٹس سکڑ جائیں۔ جب گراف G کے گرافک میٹرائڈ پر لاگو کیا جاتا ہے، تو کان کے سڑنے کی یہ تعریف G کے کان کے مناسب سڑنے کی تعریف کے ساتھ موافق ہوتی ہے: نامناسب سڑنے کو اس ضرورت سے خارج کیا جاتا ہے کہ ہر سرکٹ میں کم از کم ایک کنارے شامل ہو جس کا تعلق پچھلے سرکٹس سے بھی ہو۔ اس تعریف کا استعمال کرتے ہوئے، ایک میٹرائڈ کو فیکٹر کریٹیکل کے طور پر بیان کیا جا سکتا ہے جب اس میں کان کا سڑنا ہوتا ہے جس میں ترتیب میں ہر سرکٹ میں نئے عناصر کی ایک عجیب تعداد ہوتی ہے۔ الگورتھم کلاسیکی کمپیوٹرز پر، 2-کنارے سے منسلک گرافوں کے کان کے سڑنے اور 2-ورٹیکس سے منسلک گرافوں کے کھلے کان کے سڑنے کو لالچی الگورتھم کے ذریعے پایا جا سکتا ہے جو ایک وقت میں ہر کان کو تلاش کرتے ہیں۔ ایک سادہ لالچی نقطہ نظر جو ایک ہی وقت میں کان کے سڑنے، کھلے کان کے سڑنے، ایس ٹی نمبرنگ اور لکیری وقت (اگر موجود ہو) میں-واقفیت کا حساب لگاتا ہے۔ یہ نقطہ نظر ایک خاص کان کے سڑنے کی گنتی پر مبنی ہے جسے ایک راستہ پیدا کرنے والے اصول کے ذریعہ زنجیر سڑنا کہا جاتا ہے۔ یہ ظاہر کرتا ہے کہ غیر الگ ہونے والے کان کی سڑن بھی لکیری وقت میں تعمیر کی جا سکتی ہے۔ ،، اور مختلف اقسام کے کان کے سڑنے کی تعمیر کے لیے موثر متوازی الگورتھم فراہم کیے۔ مثال کے طور پر، 2-کنارے سے منسلک گراف کے کان کے سڑنے کو تلاش کرنے کے لیے، درج ذیل مراحل کے مطابق آمدنی کا الگورتھم: دیئے گئے گراف کا ایک پھیلا ہوا درخت تلاش کریں اور درخت کے لیے جڑ کا انتخاب کریں۔ ہر کنارے کے لیے یو وی کا تعین کریں جو درخت کا حصہ نہیں ہے، جڑ اور یو اور وی کے سب سے نچلے مشترکہ آباؤ اجداد کے درمیان فاصلہ طے کریں۔ ہر کنارے کے لیے یو وی جو درخت کا حصہ ہے، متعلقہ "ماسٹر ایج" تلاش کریں، ایک غیر درخت کا کنارہ ڈبلیو ایکس ایسا کہ درخت میں ڈبلیو ایکس شامل کرنے سے بننے والا چکر یو وی سے گزرتا ہے اور اس طرح کہ ایسے کناروں میں، ڈبلیو اور ایکس کا سب سے کم مشترکہ آباؤ اجداد ہو جو جڑ کے جتنا ممکن ہو اتنا قریب ہو (کناروں کی شناخت کرنے والوں کے ذریعے ٹوٹے ہوئے تعلقات کے ساتھ)۔ ہر غیر درخت کے کنارے کے لیے ایک کان بنائیں، جو اس پر مشتمل ہے اور درخت کے کناروں پر جس کے لیے وہ مالک ہے، اور کانوں کو جڑ سے ان کے ماسٹر کناروں کے فاصلے سے ترتیب دیں (اسی ٹائی بریکنگ اصول کے ساتھ)۔ ان الگورتھم کو دیگر مسائل کے لیے ذیلی روٹین کے طور پر استعمال کیا جا سکتا ہے جن میں ٹیسٹنگ کنیکٹوٹی، سیریز متوازی گراف کو پہچاننا، اور گراف کی ایس ٹی نمبرنگ کی تعمیر (پلانریٹی ٹیسٹنگ میں ایک اہم ذیلی روٹین) شامل ہیں۔ کسی دیئے گئے میٹرائڈ کی کان کی سڑنا، اس اضافی رکاوٹ کے ساتھ کہ ہر کان میں میٹرائڈ کا ایک ہی مقررہ عنصر ہوتا ہے، میٹرائڈ کے لیے ایک آزاد اوریکل تک رسائی کو دیکھتے ہوئے کثیر الجہتی وقت میں پایا جا سکتا ہے۔ حوالہ جات۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ گراف تھیوری آبجیکٹ میٹرائڈ تھیوری