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