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