Treewidth
گراف تھیوری میں، غیر ہدایت شدہ گراف کی تین چوڑائی ایک عدد عدد ہے جو غیر رسمی طور پر یہ بتاتا ہے کہ گراف درخت ہونے سے کتنا دور ہے۔ سب سے چھوٹی تین چوڑائی 1 ہے ؛ تین چوڑائی 1 والے گراف بالکل درخت اور جنگلات ہیں۔ زیادہ سے زیادہ 2 تین چوڑائی والے گراف سیریز متوازی گراف ہوتے ہیں۔ بالکل تین چوڑائی والے زیادہ سے زیادہ گراف کو-درخت کہا جاتا ہے، اور زیادہ سے زیادہ تین چوڑائی والے گراف کو جزوی درخت کہا جاتا ہے۔ بہت سے دوسرے اچھی طرح سے مطالعہ شدہ گراف خاندانوں نے بھی تین چوڑائی کو محدود کیا ہے۔ ٹری وڈتھ کو باضابطہ طور پر کئی مساوی طریقوں سے بیان کیا جا سکتا ہے: گراف کے درخت کے سڑنے میں سب سے بڑے ورٹیکس سیٹ کے سائز کے لحاظ سے، گراف کی کورڈل تکمیل میں سب سے بڑے گروہ کے سائز کے لحاظ سے، گراف پر تعاقب سے بچنے والے کھیل کی حکمت عملی بیان کرنے والی پناہ گاہ کی زیادہ سے زیادہ ترتیب کے لحاظ سے، یا برانبل کی زیادہ سے زیادہ ترتیب کے لحاظ سے، منسلک ذیلی گرافوں کا مجموعہ جو سب ایک دوسرے کو چھوتے ہیں۔ ٹری وڈتھ عام طور پر گراف الگورتھم کے پیرامیٹرائزڈ پیچیدگی تجزیہ میں ایک پیرامیٹر کے طور پر استعمال ہوتا ہے۔ بہت سے الگورتھم جو عام گراف کے لیے NP-سخت ہوتے ہیں، آسان ہو جاتے ہیں جب تین چوڑائی ایک مستقل سے جڑی ہوتی ہے۔ تین چوڑائی کا تصور اصل میں طول و عرض کے نام سے متعارف کرایا گیا تھا۔ بعد میں اسے ایک مختلف گراف پیرامیٹر، ہاڈوگر نمبر کے ساتھ مشترک خصوصیات کی بنیاد پر دوبارہ دریافت کیا گیا۔ بعد میں اسے دوبارہ دریافت کیا گیا اور اس کے بعد سے بہت سے دوسرے مصنفین نے اس کا مطالعہ کیا ہے۔ تعریف گراف کی ٹری سڑنا نوڈس کے ساتھ ایک ٹری ہے، جہاں ہر ایک کا ذیلی سیٹ ہے، جو درج ذیل خصوصیات کو مطمئن کرتا ہے (نوڈ کی اصطلاح کے عمودی حصوں کے ساتھ الجھن سے بچنے کے لیے نوڈ کا حوالہ دینے کے لیے استعمال کیا جاتا ہے): تمام سیٹوں کا اتحاد برابر ہوتا ہے۔ یعنی ہر گراف ورٹیکس کم از کم ایک ٹری نوڈ میں موجود ہوتا ہے۔ اگر اور دونوں میں ایک ورٹیکس ہوتا ہے، تو اس کے درمیان (منفرد) راستے کے تمام نوڈس بھی ہوتے ہیں۔ مساوی طور پر، ٹری نوڈس جس میں ورٹیکس ہوتا ہے ایک منسلک ذیلی ٹری بناتا ہے۔ گراف کے ہر کنارے کے لیے، ایک ذیلی سیٹ ہے جس میں اور دونوں شامل ہیں۔ یعنی گراف میں عمودی حصے صرف اس وقت ملحقہ ہوتے ہیں جب متعلقہ ذیلی درختوں میں ایک نوڈ مشترک ہوتا ہے۔ درخت کے سڑنے کی چوڑائی اس کے سب سے بڑے سیٹ مائنس ون کا سائز ہے۔ گراف کی تین چوڑائی درخت کے تمام ممکنہ سڑنے کے درمیان کم از کم چوڑائی ہے۔ اس تعریف میں، درخت کی تین چوڑائی کو ایک کے برابر بنانے کے لیے سب سے بڑے سیٹ کا سائز ایک سے کم کیا جاتا ہے۔ مساوی طور پر، کی تین چوڑائی سب سے چھوٹے کلک نمبر پر مشتمل کورڈل گراف میں سب سے بڑے کلک کے سائز سے ایک کم ہے۔ اس کلیک سائز کے ساتھ ایک کورڈل گراف ہر دو عمودی کے درمیان ایک کنارے میں شامل کرکے حاصل کیا جاسکتا ہے کہ دونوں کا تعلق کم از کم ایک سیٹ سے ہو۔ تین چوڑائی کو پناہ گاہوں کے لحاظ سے بھی نمایاں کیا جا سکتا ہے، وہ افعال جو گراف پر بیان کردہ کسی خاص تعاقب سے بچنے والے کھیل کے لیے چوری کی حکمت عملی کو بیان کرتے ہیں۔ گراف میں تین چوڑائی ہوتی ہے اگر اور صرف اس صورت میں جب اس میں ترتیب کی پناہ گاہ ہو لیکن کوئی اعلی ترتیب نہ ہو، جہاں ترتیب کی پناہ گاہ ایک فنکشن ہے جو زیادہ سے زیادہ عمودی حصوں کے ہر سیٹ کو منسلک اجزاء میں سے کسی ایک میں نقشہ بناتی ہے اور جو یکسانیت کی خاصیت کی پابندی کرتی ہے۔ اسی طرح کی خصوصیت برانبلز، منسلک ذیلی گراف کے خاندانوں کا استعمال کرتے ہوئے بھی بنائی جا سکتی ہے جو سب ایک دوسرے کو چھوتے ہیں (مطلب یہ ہے کہ یا تو وہ ایک سرے کا اشتراک کرتے ہیں یا ایک کنارے سے جڑے ہوئے ہیں)۔ برانبل کا آرڈر ذیلی گراف کے خاندان کے لیے سب سے چھوٹا مارنے والا سیٹ ہے، اور گراف کی تین چوڑائی برانبل کے زیادہ سے زیادہ آرڈر سے ایک کم ہوتی ہے۔ مثالیں ہر مکمل گراف میں تین چوڑائی ہوتی ہے۔ یہ کورڈل گراف کے لحاظ سے تین چوڑائی کی تعریف کا استعمال کرتے ہوئے سب سے زیادہ آسانی سے دیکھا جاتا ہے: مکمل گراف پہلے سے ہی کورڈل ہے، اور مزید کناروں کو شامل کرنے سے اس کے سب سے بڑے گروہ کے سائز کو کم نہیں کیا جا سکتا۔ کم از کم دو عمودی کے ساتھ منسلک گراف کی تین چوڑائی 1 ہوتی ہے اگر اور صرف اس صورت میں جب وہ ایک درخت ہو۔ ایک درخت کی تین چوڑائی ایک ہوتی ہے اسی استدلال سے جو مکمل گراف کے لیے ہوتی ہے (یعنی، یہ کورڈل ہوتا ہے، اور اس کا زیادہ سے زیادہ کلک سائز دو ہوتا ہے)۔ اس کے برعکس، اگر گراف میں ایک سائیکل ہے، تو گراف کی ہر کورڈل تکمیل میں کم از کم ایک مثلث شامل ہوتا ہے جو سائیکل کے لگاتار تین عمودی حصوں پر مشتمل ہوتا ہے، جس سے اس کی تین چوڑائی کم از کم دو ہوتی ہے۔ باؤنڈڈ ٹری وڈتھ گراف خاندان باؤنڈڈ ٹری وڈتھ کے ساتھ کسی بھی مقررہ مستقل کے لیے، زیادہ سے زیادہ ٹری وڈتھ کے گراف کو جزوی ٹری کہا جاتا ہے۔ باؤنڈڈ ٹری وڈتھ والے گراف کے دیگر خاندانوں میں کیکٹس گراف، سیوڈو فاریسٹ، سیریز متوازی گراف، آؤٹر پلینر گراف، ہیلن گراف، اور اپولونین نیٹ ورک شامل ہیں۔ منظم پروگراموں کی تالیف میں پیدا ہونے والے کنٹرول فلو گراف میں تین چوڑائی بھی ہوتی ہے، جو کچھ کاموں جیسے رجسٹر الاٹمنٹ کو ان پر مؤثر طریقے سے انجام دینے کی اجازت دیتی ہے۔ پلانر گراف میں تین چوڑائی کی حد نہیں ہوتی ہے، کیونکہ گرڈ گراف بالکل تین چوڑائی کے ساتھ ایک پلانر گراف ہوتا ہے۔ لہذا، اگر محدود تین چوڑائی والا ایک معمولی بند گراف خاندان ہے، تو اس میں تمام پلینر گراف شامل نہیں ہو سکتے۔ اس کے برعکس، اگر کچھ طیارہ گراف خاندان میں گراف کے لیے معمولی کے طور پر نہیں ہو سکتا، تو ایک مستقل ایسا ہوتا ہے کہ تمام گراف میں زیادہ سے زیادہ تین چوڑائی ہوتی ہے۔ یعنی، مندرجہ ذیل تین شرائط ایک دوسرے کے مساوی ہیں: باؤنڈڈ-ٹری وڈتھ گراف کا ایک معمولی بند خاندان ہے ؛ محدود طور پر بہت سے ممنوع نابالغوں میں سے ایک پلانر ہے ؛ ایک معمولی بند گراف خاندان ہے جس میں تمام پلانر گراف شامل نہیں ہیں۔ ہر محدود قیمت کے لیے، زیادہ سے زیادہ تین چوڑائی کے گراف کو ممنوع نابالغوں کے ایک محدود سیٹ کی طرف سے نمایاں کیا جا سکتا ہے۔ (یعنی، تین چوڑائی کے کسی بھی گراف میں سیٹ میں موجود گراف میں سے ایک کو معمولی کے طور پر شامل کیا جاتا ہے۔) ممنوعہ نابالغوں کے ان سیٹوں میں سے ہر ایک میں کم از کم ایک پلانر گراف شامل ہوتا ہے۔ کیونکہ، منفرد ممنوع نابالغ 3-ورٹیکس سائیکل گراف ہے۔ کیونکہ، منفرد ممنوع نابالغ 4-ورٹیکس مکمل گراف ہے۔ کیونکہ، چار ممنوع نابالغ ہیں: آکٹاہیڈرون کا گراف، پینٹاگنل پریزم گراف، اور ویگنر گراف۔ ان میں سے دو پولی ہیڈرل گراف پلینر ہیں۔ کی بڑی اقدار کے لیے، ممنوعہ نابالغوں کی تعداد کم از کم اتنی ہی تیزی سے بڑھتی ہے جتنی کہ کے مربع جڑ کا ایکسپونینشل۔ تاہم، ممنوعہ نابالغوں کے سائز اور تعداد پر معلوم اوپری حدود اس نچلی حد سے بہت زیادہ ہیں۔ الگورتھم تین چوڑائی کا حساب لگانا اس بات کا تعین کرنے کے لیے NP مکمل ہے کہ آیا دیئے گئے گراف میں زیادہ سے زیادہ ایک متغیر تین چوڑائی ہے۔ تاہم، جب کوئی فکسڈ مستقل ہوتا ہے، تو تین چوڑائی والے گراف کو پہچانا جا سکتا ہے، اور لکیری وقت میں ان کے لیے چوڑائی والے درخت کی سڑن تعمیر کی جا سکتی ہے۔ اس الگورتھم کا وقت پر انحصار ایکسپونینشل ہے۔ بہت سے شعبوں میں تین چوڑائی کے کرداروں کی وجہ سے، گراف کی تین چوڑائی کا حساب لگانے والے مختلف عملی اور نظریاتی الگورتھم تیار کیے گئے۔ ہاتھ پر موجود درخواست پر منحصر ہے، کوئی بھی بہتر تخمینہ تناسب، یا ان پٹ کے سائز یا تین چوڑائی سے چلنے والے وقت میں بہتر انحصار کو ترجیح دے سکتا ہے۔ نیچے دیا گیا جدول تین چوڑائی کے کچھ الگورتھم کا جائزہ فراہم کرتا ہے۔ یہاں تین چوڑائی ہے اور یہ ان پٹ گراف کے عمودی حصوں کی تعداد ہے۔ ہر الگورتھم وقت کے ساتھ اپروکسیمیشن کالم میں دی گئی چوڑائی کے سڑنے کا نتیجہ پیش کرتا ہے۔ مثال کے طور پر، ان ٹائم کا الگورتھم یا تو زیادہ سے زیادہ چوڑائی کے ان پٹ گراف کے درخت کے سڑنے کی تعمیر کرتا ہے یا رپورٹ کرتا ہے کہ اس کی تین چوڑائی اس سے زیادہ ہے۔ اسی طرح، ان ٹائم کا الگورتھم یا تو زیادہ سے زیادہ چوڑائی کے ان پٹ گراف کے درخت کے سڑنے کی تعمیر کرتا ہے یا رپورٹ کرتا ہے کہ اس کی تین چوڑائی اس سے زیادہ ہے۔ اسی چل رہے وقت میں اس میں بہتری لائی۔ یہ معلوم نہیں ہے کہ پلانر گراف کی تین چوڑائی کا تعین کرنا این پی مکمل ہے، یا ان کی تین چوڑائی کا حساب کثیر الجہتی وقت میں کیا جا سکتا ہے۔ عملی طور پر، کا ایک الگورتھم 100 عمودی اور 11 تک تین چوڑائی والے گرافوں کی تین چوڑائی کا تعین کر سکتا ہے، ان گرافوں کی کورڈل تکمیل کو زیادہ سے زیادہ تین چوڑائی کے ساتھ تلاش کر سکتا ہے۔ بڑے گرافوں کے لیے، تین چوڑائی کا حساب لگانے کے لیے سرچ پر مبنی تکنیک جیسے برانچ اینڈ باؤنڈ سرچ (بی این بی) اور بیسٹ فرسٹ سرچ کا استعمال کیا جا سکتا ہے۔ یہ الگورتھم کسی بھی وقت اس میں ہوتے ہیں کہ جب انہیں جلدی روک دیا جائے تو وہ تین چوڑائی پر ایک اوپری باؤنڈ آؤٹ پٹ کریں گے۔ تین چوڑائی کی کمپیوٹنگ کے لیے پہلا بی این بی الگورتھم، جسے کوئیک بی بی الگورتھم کہا جاتا ہے، گوگیٹ اور ڈیچر نے تجویز کیا تھا۔ چونکہ کسی بھی بی این بی الگورتھم کا معیار استعمال شدہ نچلی باؤنڈ کے معیار پر بہت زیادہ منحصر ہوتا ہے، اس لیے گوگیٹ اور ڈیچر نے تین چوڑائی پر نچلی باؤنڈ کی کمپیوٹنگ کے لیے ایک نیا الگورتھم بھی تجویز کیا جسے معمولی-کم-چوڑائی کہا جاتا ہے۔ اعلی سطح پر، معمولی-کم-چوڑائی الگورتھم ان حقائق کو یکجا کرتا ہے کہ گراف کی تین چوڑائی کبھی بھی اس کی کم از کم ڈگری سے بڑی نہیں ہوتی ہے یا تین چوڑائی پر کم حد حاصل کرنے کے لیے معمولی ہوتی ہے۔ معمولی-کم-چوڑائی الگورتھم بار بار کم سے کم ڈگری ورٹیکس اور اس کے پڑوسیوں میں سے ایک کے درمیان کنارے کو سکڑ کر ایک گراف معمولی بناتا ہے، جب تک کہ صرف ایک ورٹیکس باقی نہ رہے۔ ان تعمیر شدہ نابالغوں پر کم سے کم ڈگری کی زیادہ سے زیادہ حد گراف کی تین چوڑائی پر نچلی حد کی ضمانت ہے۔ ڈاؤ اور کورف نے بہترین پہلی تلاش کا استعمال کرتے ہوئے کوئیک بی بی الگورتھم کو بہتر بنایا۔ بعض گرافوں پر، یہ بہترین فرسٹ سرچ الگورتھم کوئیک بی بی سے زیادہ تیزی سے شدت کی ترتیب ہے۔ چھوٹے تین چوڑائی کے گرافوں پر دیگر مسائل کو حل کرنا 1970 کی دہائی کے آغاز میں، یہ مشاہدہ کیا گیا کہ گرافوں پر بیان کردہ مشترکہ اصلاح کے مسائل کی ایک بڑی کلاس کو غیر سیریل متحرک پروگرامنگ کے ذریعے مؤثر طریقے سے حل کیا جا سکتا ہے جب تک کہ گراف کا ایک محدود طول و عرض ہو، ایک پیرامیٹر جو تین چوڑائی کے برابر دکھایا گیا ہے۔ بعد میں، متعدد مصنفین نے 1980 کی دہائی کے آخر میں آزادانہ طور پر مشاہدہ کیا کہ بہت سے الگورتھمک مسائل جو صوابدیدی گرافوں کے لیے این پی مکمل ہیں، ان گرافوں کے ٹری-ڈیکمپزیشن کا استعمال کرتے ہوئے باؤنڈڈ ٹری وڈتھ کے گرافوں کے لیے متحرک پروگرامنگ کے ذریعے مؤثر طریقے سے حل کیے جا سکتے ہیں۔ مثال کے طور پر، تین چوڑائی کے گراف کو رنگنے کا مسئلہ گراف کے درخت کے سڑنے پر متحرک پروگرامنگ الگورتھم کا استعمال کرکے حل کیا جا سکتا ہے۔ درخت کے سڑنے کے ہر سیٹ کے لیے، اور رنگین کلاسوں میں عمودی حصوں کی ہر تقسیم کے لیے، الگورتھم اس بات کا تعین کرتا ہے کہ آیا وہ رنگ درست ہے اور درخت کے سڑنے میں تمام نسل نوڈس تک بڑھایا جا سکتا ہے، اسی طرح کی قسم کی معلومات کو جوڑ کر اور ان نوڈس پر ذخیرہ کیا جا سکتا ہے۔ نتیجے میں آنے والا الگورتھم وقت کے ساتھ-ورٹیکس گراف کا ایک بہترین رنگ تلاش کرتا ہے، ایک مقررہ وقت جو اس مسئلے کو فکسڈ-پیرامیٹر ٹریک ایبل بناتا ہے۔ کورسل کا نظریہ مسائل کی ایک بڑی کلاس کے لیے، کلاس سے کسی مسئلے کو حل کرنے کے لیے ایک لکیری ٹائم الگورتھم موجود ہے اگر مستقل باؤنڈڈ ٹری وڈتھ کے ساتھ ٹری-ڈکمپوزیشن فراہم کی جائے۔ خاص طور پر، کورسل کے نظریہ میں کہا گیا ہے کہ اگر گراف کے مسئلے کو موناڈک سیکنڈ آرڈر منطق کا استعمال کرتے ہوئے گراف کی منطق میں ظاہر کیا جا سکتا ہے، تو اسے پابند تین چوڑائی والے گراف پر لکیری وقت میں حل کیا جا سکتا ہے۔ موناڈک سیکنڈ آرڈر منطق گراف کی خصوصیات کو بیان کرنے کے لیے ایک زبان ہے جو مندرجہ ذیل تعمیرات کا استعمال کرتی ہے: منطق آپریشنز، جیسے ممبرشپ ٹیسٹ، جیسے کہ عمودی، کناروں، عمودی سیٹوں، اور/یا کناروں کے سیٹوں، جیسے،،، ایڈجسینسی ٹیسٹ (کا ایک اختتامی نقطہ ہے)، اور کچھ توسیعات جو اصلاح جیسی چیزوں کی اجازت دیتی ہیں۔ مثال کے طور پر گراف کے لیے 3 رنگوں کے مسئلے پر غور کریں۔ گراف کے لیے، یہ مسئلہ پوچھتا ہے کہ کیا ہر سرے کو 3 رنگوں میں سے ایک اس طرح تفویض کرنا ممکن ہے کہ کسی بھی دو ملحقہ سرے کو ایک ہی رنگ تفویض نہ کیا جائے۔ اس مسئلے کا اظہار موناڈک سیکنڈ آرڈر منطق میں مندرجہ ذیل طور پر کیا جا سکتا ہے:، جہاں، 3 رنگوں میں سے ہر ایک والے عمودی ذیلی سیٹوں کی نمائندگی کرتا ہے۔ لہذا، کورسل کے نتائج سے، 3 رنگوں کے مسئلے کو ایک گراف کے لیے لکیری وقت میں حل کیا جا سکتا ہے جس میں باؤنڈڈ کانسٹینٹ ٹری وڈتھ کی ٹری-ڈکمپوزیشن دی گئی ہو۔ متعلقہ پیرامیٹرز پاتھ چوڑائی گراف کی پاتھ چوڑائی کی تعریف درختوں کے سڑنے کے ذریعے ٹری چوڑائی سے بہت ملتی جلتی ہے، لیکن یہ درختوں کے سڑنے تک محدود ہے جس میں سڑنے کا بنیادی درخت ایک پاتھ گراف ہے۔ متبادل طور پر، راستے کی چوڑائی کو وقفہ گراف سے کورڈل گراف سے تین چوڑائی کی تعریف کے مطابق بیان کیا جا سکتا ہے۔ نتیجے کے طور پر، گراف کی راستے کی چوڑائی ہمیشہ کم از کم اس کی تین چوڑائی جتنی بڑی ہوتی ہے، لیکن یہ صرف لوگرتھمک عنصر سے بڑی ہو سکتی ہے۔ ایک اور پیرامیٹر، گراف بینڈوڈتھ، مناسب وقفہ گرافوں سے مماثل تعریف رکھتا ہے، اور کم از کم راستے کی چوڑائی جتنا بڑا ہوتا ہے۔ دیگر متعلقہ پیرامیٹرز میں درخت کی گہرائی شامل ہے، ایک ایسی تعداد جو ایک معمولی بند گراف فیملی کے لیے پابند ہے اگر اور صرف اس صورت میں جب خاندان کسی راستے کو خارج کرتا ہے، اور انحطاط، گراف کی تیز رفتار کی پیمائش جو زیادہ سے زیادہ اس کی تین چوڑائی کے برابر ہے۔ گرڈ کا چھوٹا سائز کیونکہ گرڈ گراف کی تین چوڑائی ہوتی ہے، اس لیے گراف کی تین چوڑائی ہمیشہ سب سے بڑے مربع گرڈ کے چھوٹے سائز سے زیادہ یا اس کے برابر ہوتی ہے۔ دوسری سمت میں، رابرٹسن اور سیمور کے گرڈ مائنر تھیوریم سے پتہ چلتا ہے کہ ایک بے حد فنکشن موجود ہے جیسے کہ سب سے بڑے مربع گرڈ مائنر کا سائز کم از کم جہاں تین چوڑائی ہے۔ معلوم ہونے والی بہترین حدود یہ ہیں کہ کم از کم کچھ مقررہ مستقل کے لیے ہونی چاہئیں، اور زیادہ سے زیادہ نچلی حد میں اشارے کے لیے، بگ O اشارے دیکھیں۔ سخت حدود محدود گراف خاندانوں کے لیے جانی جاتی ہیں، جو نظریہ دو جہتی کے ذریعے ان خاندانوں پر گراف کو بہتر بنانے کے بہت سے مسائل کے لیے موثر الگورتھم کا باعث بنتی ہیں۔ ہیلن کا گرڈ تھیوریم لامحدود گرافوں کے لیے تین چوڑائی اور گرڈ معمولی سائز کے درمیان تعلق کا ایک ینالاگ فراہم کرتا ہے۔ قطر اور مقامی تین چوڑائی ذیلی گراف لینے کے تحت بند گرافوں کے ایک خاندان کے بارے میں کہا جاتا ہے کہ اس نے مقامی تین چوڑائی، یا قطر-تین چوڑائی کی خاصیت کو محدود کیا ہے، اگر خاندان میں گرافوں کی تین چوڑائی ان کے قطر کے فنکشن سے بالائی حد میں ہے۔ اگر کلاس کو نابالغوں کو لینے کے تحت بھی بند سمجھا جاتا ہے، تو اس نے مقامی تین چوڑائی کو محدود کیا ہے اگر اور صرف اس صورت میں جب ممنوع نابالغوں میں سے ایک اپیکس گراف ہو۔ اس نتیجے کے اصل شواہد سے پتہ چلتا ہے کہ اپیکس-مائنر فری گراف فیملی میں تین چوڑائی قطر کی تقریب کے طور پر زیادہ سے زیادہ دوگنا تیزی سے بڑھتی ہے۔ بعد میں اسے کم کر کے سنگل ایکسپونینشل اور آخر میں لکیری باؤنڈ کر دیا گیا۔ باؤنڈڈ لوکل ٹری وڈتھ کا دو جہتی کے الگورتھمک تھیوری سے گہرا تعلق ہے، اور فرسٹ آرڈر منطق میں قابل تعریف ہر گراف پراپرٹی کا فیصلہ ایک اپیکس-مائنر فری گراف فیملی کے لیے اس وقت میں کیا جا سکتا ہے جو صرف قدرے سپر لائنر ہو۔ یہ بھی ممکن ہے کہ گراف کی ایک کلاس کے لیے جو نابالغوں کے تحت بند نہیں ہے وہ مقامی تین چوڑائی سے منسلک ہو۔ خاص طور پر یہ باؤنڈ ڈگری گراف کی کلاس کے لیے معمولی طور پر درست ہے، کیونکہ باؤنڈ ڈایمیٹر سب گراف کا سائز باؤنڈ ہوتا ہے۔ ایک اور مثال 1-پلینر گراف کے ذریعے دی گئی ہے، وہ گراف جو فی کنارے ایک کراسنگ کے ساتھ ہوائی جہاز میں کھینچے جا سکتے ہیں، اور زیادہ عام طور پر ان گرافوں کے لیے جو فی کنارے کراسنگ کی محدود تعداد کے ساتھ باؤنڈڈ جینس کی سطح پر کھینچے جا سکتے ہیں۔ جیسا کہ محدود مقامی تین چوڑائی کے معمولی بند گراف خاندانوں کے ساتھ، اس خاصیت نے ان گرافوں کے لیے موثر تخمینہ الگورتھم کی طرف اشارہ کیا ہے۔ ہاڈوگر نمبر اور ایس فنکشن گراف پیرامیٹرز کی ایک کلاس کی وضاحت کرتے ہیں جسے وہ فنکشن کہتے ہیں، جس میں تین چوڑائی شامل ہے۔ گراف سے لے کر انٹیجرز تک کے ان افعال کو بغیر کناروں والے گرافوں پر صفر ہونا ضروری ہے، معمولی-مونوٹون ہونے کے لیے (ایک فنکشن کو "معمولی-مونوٹون" کہا جاتا ہے اگر، جب بھی کوئی معمولی ہو، کسی کے پاس ہو)، جب ایک نیا ورٹیکس شامل کیا جاتا ہے جو پچھلے تمام عمودی حصوں سے متصل ہوتا ہے، اور کلک علیحدگی کے دونوں طرف دو ذیلی گرافوں سے بڑی قیمت لینے کے لیے۔ اس طرح کے تمام افعال کا مجموعہ عنصر وار کم سے کم کرنے اور زیادہ سے زیادہ کرنے کی کارروائیوں کے تحت ایک مکمل جالی بناتا ہے۔ اس جالی میں سب سے اوپر کا عنصر تین چوڑائی ہے، اور نیچے کا عنصر ہاڈوگر نمبر ہے، جو دیئے گئے گراف میں سب سے بڑے مکمل معمولی کا سائز ہے۔ حوالہ جات نوٹ کریں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ گراف غیر متغیر گراف معمولی نظریہ