Trémaux tree
گراف تھیوری میں، غیر ہدایت شدہ گراف کا ٹریماکس ٹری پھیلے ہوئے درخت کی ایک قسم ہے، جو گہرائی سے پہلے تلاش کرنے والے درختوں کو عام کرتا ہے۔ ان کی تعریف اس خاصیت سے کی جاتی ہے کہ درخت کا ہر کنارہ درخت میں آباؤ اجداد کے جوڑے کو جوڑتا ہے۔ ٹریماکس کے درختوں کا نام 19 ویں صدی کے فرانسیسی مصنف چارلس پیئر ٹریماکس کے نام پر رکھا گیا ہے جس نے میز کو حل کرنے کی حکمت عملی کے طور پر ڈیپتھ فرسٹ سرچ کی ایک شکل استعمال کی تھی۔ انہیں عام پھیلے ہوئے درخت بھی کہا جاتا ہے، خاص طور پر لامحدود گراف کے تناظر میں۔ تمام ڈیپتھ-فرسٹ سرچ ٹری اور تمام ہیملٹنین راستے ٹریماکس ٹری ہیں۔ محدود گرافوں میں، ہر ٹریماکس ٹری ایک ڈیپتھ-فرسٹ سرچ ٹری ہے، لیکن اگرچہ ڈیپتھ-فرسٹ سرچ خود فطری طور پر ترتیب وار ہے، ٹریماکس ٹری کو پیچیدگی کلاس آر این سی میں بے ترتیب متوازی الگورتھم کے ذریعے بنایا جا سکتا ہے۔ انہیں گراف کی درخت کی گہرائی کی وضاحت کے لیے استعمال کیا جا سکتا ہے، اور یہ جانچنے کے لیے کہ آیا گراف پلانر گراف ہے، بائیں دائیں پلانریٹی ٹیسٹ کے حصے کے طور پر استعمال کیا جا سکتا ہے۔ گراف کی موناڈک سیکنڈ آرڈر منطق میں ٹریماکس کے درختوں کی خصوصیت کورسل کے نظریہ کا استعمال کرتے ہوئے باؤنڈڈ ٹری وڈتھ کے گراف کے لیے واقفیت پر مشتمل گراف کی خصوصیات کو مؤثر طریقے سے پہچاننے کی اجازت دیتی ہے۔ ہر لامحدود منسلک گراف میں ٹریماکس ٹری نہیں ہوتا ہے، اور نہ ہی ہر لامحدود ٹریماکس ٹری ڈیپتھ فرسٹ سرچ ٹری ہوتا ہے۔ جن گرافوں میں ٹریماکس کے درخت ہوتے ہیں ان کی خصوصیت ممنوعہ نابالغوں سے کی جا سکتی ہے۔ ایک لامحدود ٹریماکس ٹری میں گراف کے ہر سرے کے لیے بالکل ایک لامحدود راستہ ہونا چاہیے، اور ٹریماکس ٹری کا وجود ان گرافوں کی خصوصیت رکھتا ہے جن کی ٹپوولوجیکل تکمیل، ہر سرے کے لیے انفینیٹی پر ایک نقطہ شامل کرنے سے بنتی ہے، وہ میٹرک خالی جگہیں ہیں۔ تعریف اور مثالیں ٹریماکس ٹری، گراف کے لیے، ایک پھیلا ہوا درخت ہے جس کی خاصیت یہ ہے کہ، ہر کنارے کے لیے، دو اختتامی نکات میں سے ایک اور دوسرے کا آباؤ اجداد ہے۔ ایک پھیلا ہوا درخت بننے کے لیے، اسے صرف کناروں کا استعمال کرنا چاہیے، اور ہر سرے کو شامل کرنا چاہیے، جس میں ہر جوڑے کے درمیان ایک منفرد محدود راستہ ہو۔ مزید برآں، اس درخت میں آباؤ اجداد اور اولاد کے تعلق کی وضاحت کے لیے، اس کے عمودی حصوں میں سے ایک کو اس کی جڑ کے طور پر نامزد کیا جانا چاہیے۔ اگر ایک محدود گراف میں ہیملٹنین راستہ ہے، تو اس راستے کو اس کے دو اختتامی نکات میں سے کسی ایک پر جڑ سے جڑنے سے ٹریماکس درخت پیدا ہوتا ہے۔ اس طرح کے راستے کے لیے، چوٹیوں کا ہر جوڑا آباؤ اجداد کی نسل کا جوڑا ہوتا ہے۔ ذیل میں دکھائے گئے گراف میں، 1-3,2-3، اور 3-4 کناروں والا درخت ایک ٹریماکس درخت ہے جب اس کی جڑیں ورٹیکس 1 یا ورٹیکس 2 پر ہوتی ہیں: گراف کا ہر کنارہ درخت سے تعلق رکھتا ہے سوائے کنارہ 1-2 کے، جو (جڑ کے ان انتخاب کے لیے) آباؤ اجداد کی نسل کے جوڑے کو جوڑتا ہے۔ تاہم، ایک ہی درخت کو ورٹیکس 3 یا ورٹیکس 4 پر جڑنے سے ایک جڑا ہوا درخت پیدا ہوتا ہے جو ٹریماکس درخت نہیں ہے، کیونکہ اس جڑ کے ساتھ 1 اور 2 اب ایک دوسرے کے آباؤ اجداد اور اولاد نہیں ہیں۔ محدود گرافوں میں وجود ہر محدود منسلک غیر ہدایت شدہ گراف میں کم از کم ایک ٹریماکس ٹری ہوتا ہے۔ کوئی بھی ایسا درخت گہرائی سے پہلے تلاش کرکے اور ہر سرے کو (تلاش کے ابتدائی سرے کے علاوہ) پہلے سرے سے جوڑ کر تعمیر کر سکتا ہے جہاں سے اسے دریافت کیا گیا تھا۔ اس طرح بنائے گئے درخت کو ڈیپتھ فرسٹ سرچ ٹری کہا جاتا ہے۔ اگر گراف میں ایک صوابدیدی کنارے ہے، اور تلاش کے ذریعے پہنچنے والے دو عمودی حصوں میں سے پہلا ہے، تو اس کا تعلق ڈیپتھ-فرسٹ سرچ ٹری سے اترتے ہوئے ذیلی درخت سے ہونا چاہیے، کیونکہ اس ذیلی درخت کو تلاش کرتے وقت تلاش لازمی طور پر دریافت کرے گی، یا تو ذیلی درخت کے دوسرے عمودی حصوں میں سے کسی ایک سے یا، ایسا نہ کرنے پر، براہ راست سے۔ ہر محدود ٹریماکس ٹری کو ڈیپتھ فرسٹ سرچ ٹری کے طور پر تیار کیا جا سکتا ہے: اگر ایک محدود گراف کا ٹریماکس ٹری ہے، اور ڈیپتھ فرسٹ سرچ کسی دوسرے عمودی حصے کو تلاش کرنے سے پہلے ہر سرے کے بچوں کی کھوج کرتی ہے، تو یہ لازمی طور پر اس کے ڈیپتھ فرسٹ سرچ ٹری کے طور پر پیدا ہوگا۔ متوازی تعمیر ٹریماکس درخت کو تلاش کرنا پی مکمل ہے جو ایک ترتیب وار ڈیپتھ-فرسٹ سرچ الگورتھم کے ذریعے پایا جائے گا، جس میں ہر سرے کے پڑوسیوں کو ان کی شناخت کے مطابق تلاش کیا جاتا ہے۔ اس کے باوجود، بے ترتیب متوازی الگورتھم کے ذریعے ایک مختلف ٹریماکس درخت تلاش کرنا ممکن ہے، جس سے یہ ظاہر ہوتا ہے کہ ٹریماکس درختوں کی تعمیر کا تعلق پیچیدگی کلاس آر این سی سے ہے۔ الگورتھم ایک اور بے ترتیب متوازی الگورتھم پر مبنی ہے، تاکہ 0-1 وزن والے گرافوں میں کم از کم وزن کے کامل ملاپ کو تلاش کیا جا سکے۔ 1997 تک، یہ معلوم نہیں تھا کہ آیا ٹریماکس درخت کی تعمیر پیچیدگی کلاس این سی میں ایک تعیناتی متوازی الگورتھم کے ذریعے کی جا سکتی ہے۔ اگر ملاپ این سی میں پایا جا سکتا ہے، تو ٹریماکس کے درخت بھی مل سکتے ہیں۔ منطقی اظہار اس خاصیت کا اظہار کرنا ممکن ہے کہ جڑ کے سرے کے انتخاب کے ساتھ کناروں کا ایک مجموعہ ٹریماکس ٹری بناتا ہے، گراف کی موناڈک سیکنڈ آرڈر منطق میں، اور خاص طور پر اس منطق کی شکل میں جسے ایم ایس او 2 کہا جاتا ہے، جو سرے اور کنارے دونوں سیٹوں پر مقدار کی اجازت دیتا ہے۔ اس خاصیت کو درج ذیل خصوصیات کے امتزاج کے طور پر ظاہر کیا جا سکتا ہے: گراف اندر کے کناروں سے جڑا ہوا ہے۔ اس کا اظہار منطقی طور پر اس بیان کے طور پر کیا جا سکتا ہے کہ، گراف کے عمودی حصوں کے ہر غیر خالی مناسب ذیلی سیٹ کے لیے، دیئے گئے ذیلی سیٹ میں بالکل ایک اختتامی نقطہ کے ساتھ ایک کنارے موجود ہے۔ ایسائکلک ہے۔ اس کا اظہار منطقی طور پر اس بیان کے طور پر کیا جا سکتا ہے کہ کوئی غیر خالی ذیلی سیٹ موجود نہیں ہے جس کے لیے ہر ورٹیکس صفر یا دو کناروں پر واقع ہو۔ ہر وہ کنارہ جو آباؤ اجداد کے آباؤ اجداد کے جوڑے کو جوڑتا ہے۔ یہ اس وقت درست ہوتا ہے جب دونوں اختتامی نکات کسی راستے سے تعلق رکھتے ہوں۔ اس کا اظہار منطقی طور پر اس بیان کے طور پر کیا جا سکتا ہے کہ، تمام کناروں کے لیے، اس طرح کا ایک ذیلی مجموعہ موجود ہے کہ بالکل دو عمودی، ان میں سے ایک، کے ایک کنارے پر واقع ہوتے ہیں، اور اس طرح کہ دونوں اختتامی نکات کم از کم ایک کنارے پر واقع ہوتے ہیں۔ ایک بار جب ٹریماکس کے درخت کی شناخت اس طرح کی جاتی ہے، تو کوئی بھی دیئے گئے گراف کی واقفیت کو بیان کر سکتا ہے، موناڈک سیکنڈ آرڈر منطق میں بھی، کناروں کے سیٹ کی وضاحت کر کے جس کی واقفیت آبائی اختتامی نقطہ سے نسل کے اختتامی نقطہ تک ہے۔ اس سیٹ کے باہر باقی کناروں کو دوسری سمت میں ہونا چاہیے۔ یہ تکنیک گراف کی خصوصیات کو موناڈک سیکنڈ آرڈر منطق میں متعین کرنے کی اجازت دیتی ہے، جس سے کورسل کے نظریہ کا استعمال کرتے ہوئے ان خصوصیات کو باؤنڈڈ ٹری وڈتھ کے گراف پر مؤثر طریقے سے آزمایا جا سکتا ہے۔ متعلقہ خصوصیات اگر کسی گراف میں ہیملٹنین راستہ ہے، تو وہ راستہ (جس کی جڑیں اس کے اختتامی نکات میں سے ایک پر ہیں) بھی ٹریماکس ٹری ہے۔ غیر ہدایت شدہ گراف جن کے لیے ہر ٹریماکس ٹری کی یہ شکل ہوتی ہے وہ سائیکل گراف، مکمل گراف، اور متوازن مکمل دو طرفہ گراف ہیں۔ ٹریماکس کے درختوں کا درخت کی گہرائی کے تصور سے گہرا تعلق ہے۔ گراف کی درخت کی گہرائی کو سب سے چھوٹی تعداد کے طور پر بیان کیا جا سکتا ہے جس کے لیے ایک گراف موجود ہے، جس میں گہرائی کا ٹریماکس درخت ہے، جیسا کہ اس کا ذیلی گراف ہے۔ گراف کے ایک خاندان میں، بائونڈڈ ٹری ڈیپتھ، ایک ایسے راستے کے وجود کے برابر ہے جو خاندان میں گراف کے چھوٹے گراف کے طور پر نہیں ہو سکتا۔ گراف پر بہت سے سخت کمپیوٹیشنل مسائل میں الگورتھم ہوتے ہیں جو فکسڈ پیرامیٹر ٹریک ایبل ہوتے ہیں جب ان کے ان پٹ کی ٹری ڈیپتھ کے ذریعے پیرامیٹرائز کیے جاتے ہیں۔ ٹریماکس کے درخت یہ جانچنے کے لیے کہ آیا دیا گیا گراف پلینر ہے، فریسیکس-روزنسٹیل پلانریٹی کے معیار میں بھی کلیدی کردار ادا کرتے ہیں۔ اس معیار کے مطابق، ایک گراف ہموار ہوتا ہے اگر، کسی دیئے گئے ٹریماکس درخت کے لیے، باقی کناروں کو درخت کے بائیں یا دائیں طرف مستقل انداز میں رکھا جا سکتا ہے، جو ان رکاوٹوں کے تابع ہیں جو ایک ہی جگہ والے کناروں کو ایک دوسرے کو عبور کرنے سے روکتی ہیں۔ لامحدود گرافوں میں وجود ہر لامحدود گراف میں ایک عام پھیلا ہوا درخت نہیں ہوتا ہے۔ مثال کے طور پر، عمودی حصوں کے ایک بے شمار سیٹ پر ایک مکمل گراف میں ایک نہیں ہوتا ہے: ایک مکمل گراف میں ایک عام پھیلا ہوا درخت صرف ایک راستہ ہو سکتا ہے، لیکن ایک راستے میں صرف قابل شمار عمودی حصے ہوتے ہیں۔ تاہم، عمودی شمار کے قابل سیٹ پر ہر گراف میں ایک عام پھیلا ہوا درخت ہوتا ہے۔ یہاں تک کہ قابل گنتی گرافوں میں بھی، گہرائی سے پہلے تلاش بالآخر پورے گراف کو تلاش کرنے میں کامیاب نہیں ہو سکتی ہے، اور ہر عام پھیلے ہوئے درخت کو گہرائی سے پہلے تلاش سے پیدا نہیں کیا جا سکتا ہے: گہرائی سے پہلے تلاش کرنے والے درخت ہونے کے لیے، ایک قابل گنتی عام پھیلے ہوئے درخت میں صرف ایک لامحدود راستہ یا ایک نوڈ ہونا چاہیے جس میں لامحدود تعداد میں بچے ہوں (اور دونوں نہیں)۔ نابالغ اگر ایک لامحدود گراف میں ایک عام پھیلا ہوا درخت ہوتا ہے، تو اسی طرح ہر منسلک گراف کا چھوٹا ہوتا ہے۔ اس سے یہ پتہ چلتا ہے کہ جن گرافوں میں عام طور پر پھیلے ہوئے درخت ہوتے ہیں ان میں ممنوعہ نابالغوں کی خصوصیت ہوتی ہے۔ ممنوعہ نابالغوں کی دو کلاسوں میں سے ایک دو طرفہ گراف پر مشتمل ہوتا ہے جس میں دو طرفہ کا ایک رخ قابل گنتی ہوتا ہے، دوسرا رخ ناقابل شمار ہوتا ہے، اور ہر سرے پر لامحدود ڈگری ہوتی ہے۔ ممنوعہ نابالغوں کی دوسری کلاس آرونزاجن کے درختوں سے اخذ کردہ بعض گرافوں پر مشتمل ہے۔ اس خصوصیت کی تفصیلات کا انحصار ریاضی کو باقاعدہ بنانے کے لیے استعمال ہونے والے سیٹ تھیوریٹک محوریت کے انتخاب پر ہے۔ خاص طور پر، سیٹ تھیوری کے نمونوں میں جن کے لیے مارٹن کا محور درست ہے اور تسلسل مفروضہ غلط ہے، اس خصوصیت میں دو طرفہ گراف کی کلاس کو ایک ممنوع معمولی سے تبدیل کیا جا سکتا ہے۔ تاہم، ان ماڈلز کے لیے جن میں تسلسل مفروضہ درست ہے، اس کلاس میں ایسے گراف ہوتے ہیں جو معمولی ترتیب میں ایک دوسرے کے ساتھ بے مثال ہوتے ہیں۔ اختتام اور پیمائش عام پھیلے ہوئے درختوں کا ایک لامحدود گراف کے سروں سے بھی گہرا تعلق ہوتا ہے، لامحدود راستوں کی مساوات کی کلاسیں جو بدیہی طور پر ایک ہی سمت میں لامحدود تک جاتی ہیں۔ اگر کسی گراف میں ایک عام پھیلا ہوا درخت ہے، تو اس درخت میں گراف کے ہر سرے کے لیے بالکل ایک لامحدود راستہ ہونا چاہیے۔ ایک لامحدود گراف کو خود گراف کو ایک آسان کمپلیکس کے طور پر دیکھ کر اور گراف کے ہر سرے کے لیے لامحدود پر ایک نقطہ شامل کر کے ٹپوولوجیکل اسپیس بنانے کے لیے استعمال کیا جا سکتا ہے۔ اس ٹوپولوجی کے ساتھ، گراف میں ایک عام پھیلا ہوا درخت ہوتا ہے اگر اور صرف اس صورت میں جب اس کے عمودی سیٹ کو بند سیٹوں کے قابل شمار اتحاد میں تحلیل کیا جا سکے۔ مزید برآں، اس ٹپوولوجیکل اسپیس کی نمائندگی میٹرک اسپیس کے ذریعے کی جا سکتی ہے اگر اور صرف اس صورت میں جب گراف میں ایک عام پھیلا ہوا درخت ہو۔ حوالہ جات گراف تھیوری آبجیکٹ اسپاننگ ٹری گراف معمولی نظریہ لامحدود گراف