Split graph
گراف تھیوری میں، ریاضی کی ایک شاخ، ایک تقسیم شدہ گراف ایک گراف ہے جس میں عمودی حصوں کو ایک گروہ اور ایک آزاد سیٹ میں تقسیم کیا جا سکتا ہے۔ تقسیم شدہ گراف کا سب سے پہلے مطالعہ کیا گیا، اور آزادانہ طور پر متعارف کرایا گیا۔ ایک تقسیم شدہ گراف میں ایک گروہ اور ایک آزاد سیٹ میں ایک سے زیادہ تقسیم ہو سکتی ہے۔ مثال کے طور پر، راستہ ایک تقسیم شدہ گراف ہے، جس کے عمودی حصوں کو تین مختلف طریقوں سے تقسیم کیا جا سکتا ہے: گروہ اور آزاد سیٹ گروہ اور آزاد سیٹ گروہ اور آزاد سیٹ تقسیم شدہ گراف کو ان کے ممنوع محرک ذیلی گراف کے لحاظ سے نمایاں کیا جا سکتا ہے: گراف کو اس صورت میں تقسیم کیا جاتا ہے جب کوئی محرک ذیلی گراف چار یا پانچ عمودی حصوں پر ایک سائیکل نہ ہو، یا جداگانہ کناروں کا ایک جوڑا (4-سائیکل کی تکمیل) ہو۔ گراف کے دیگر خاندانوں سے تعلق تعریف سے، تقسیم شدہ گراف واضح طور پر تکمیل کے تحت بند ہیں۔ تقسیم شدہ گرافوں کی ایک اور خصوصیت میں تکمیل شامل ہے: وہ کورڈل گراف ہیں جن کی تکمیل بھی کورڈل ہیں۔ جس طرح کورڈل گراف درختوں کے ذیلی درختوں کے انٹرسیکشن گراف ہوتے ہیں، اسی طرح اسپلٹ گراف اسٹار گراف کے الگ الگ سب اسٹارز کے انٹرسیکشن گراف ہوتے ہیں۔ تقریبا تمام کورڈیل گراف تقسیم شدہ گراف ہوتے ہیں ؛ یعنی، اس حد میں جب n انفینیٹی کی طرف جاتا ہے، n-ورٹیکس کورڈیل گراف کا حصہ جو تقسیم شدہ ہوتا ہے ایک کے قریب پہنچ جاتا ہے۔ کیونکہ کورڈل گراف کامل ہیں، اسی طرح تقسیم شدہ گراف بھی ہیں۔ ڈبل اسپلٹ گراف، گرافوں کا ایک خاندان جو ہر سرے کو دوگنا کرکے اسپلٹ گرافوں سے اخذ کیا گیا ہے (اس لیے کلک ایک اینٹی میچنگ کو متاثر کرنے کے لیے آتا ہے اور آزاد سیٹ ایک مماثلت کو متاثر کرنے کے لیے آتا ہے)، کامل گرافوں کی پانچ بنیادی کلاسوں میں سے ایک کے طور پر نمایاں طور پر ظاہر ہوتا ہے جس سے دیگر تمام کو مضبوط کامل گراف تھیوریم کے ذریعے ثبوت میں تشکیل دیا جا سکتا ہے۔ اگر کوئی گراف ایک تقسیم شدہ گراف اور وقفہ گراف دونوں ہے، تو اس کی تکمیل ایک تقسیم شدہ گراف اور تقابلی گراف دونوں ہے، اور اس کے برعکس۔ تقسیم موازنہ گراف، اور اس وجہ سے تقسیم وقفہ گراف، تین ممنوع حوصلہ افزائی ذیلی گراف کے ایک سیٹ کے لحاظ سے نمایاں کیے جا سکتے ہیں۔ تقسیم شدہ گراف بالکل دہلیز گراف ہیں۔ تقسیم شدہ تعدد گراف بالکل وقفہ گراف ہوتے ہیں جن میں وقفہ گراف کی تکمیل ہوتی ہے۔ یہ سکیو ضم شدہ تعدد کے تعدد گراف ہوتے ہیں۔ تقسیم شدہ گرافوں میں کوکرومیٹک نمبر 2 ہوتا ہے۔ الگورتھمک مسائل ایک تقسیم شدہ گراف ہونے دیں، جسے ایک گروہ اور ایک آزاد سیٹ میں تقسیم کیا گیا ہے۔ پھر تقسیم شدہ گراف میں ہر زیادہ سے زیادہ گروہ یا تو خود ہوتا ہے، یا کسی سرے کے پڑوس میں ہوتا ہے۔ اس طرح، زیادہ سے زیادہ گروہ کی شناخت کرنا آسان ہے، اور تکمیل کے طور پر تقسیم شدہ گراف میں زیادہ سے زیادہ آزاد سیٹ۔ کسی بھی تقسیم شدہ گراف میں، درج ذیل تین امکانات میں سے ایک درست ہونا چاہیے: اس طرح کا ایک ورٹیکس موجود ہے جو مکمل ہے۔ اس صورت میں، ایک زیادہ سے زیادہ گروہ ہے اور ایک زیادہ سے زیادہ آزاد سیٹ ہے۔ اس طرح میں ایک ورٹیکس موجود ہے جو آزاد ہے۔ اس صورت میں، ایک زیادہ سے زیادہ آزاد سیٹ ہے اور ایک زیادہ سے زیادہ کلک ہے۔ ایک زیادہ سے زیادہ گروہ ہے اور ایک زیادہ سے زیادہ آزاد سیٹ ہے۔ اس صورت میں، ایک گروہ اور ایک آزاد سیٹ میں ایک منفرد تقسیم ہے، زیادہ سے زیادہ گروہ ہے، اور زیادہ سے زیادہ آزاد سیٹ ہے۔ کچھ دیگر اصلاحاتی مسائل جو زیادہ عام گراف خاندانوں پر این پی مکمل ہیں، بشمول گراف کلرنگ، اسی طرح تقسیم شدہ گرافوں پر سیدھے سیدھے ہیں۔ ہیملٹنین سائیکل تلاش کرنا این پی مکمل رہتا ہے یہاں تک کہ اسپلٹ گراف کے لیے بھی جو مضبوطی سے کورڈل گراف ہیں۔ یہ بھی اچھی طرح سے جانا جاتا ہے کہ کم از کم ڈومینیٹنگ سیٹ کا مسئلہ تقسیم شدہ گراف کے لیے این پی مکمل رہتا ہے۔ درجہ ترتیب تقسیم شدہ گراف کی ایک قابل ذکر خاصیت یہ ہے کہ انہیں صرف ان کے درجہ ترتیب سے پہچانا جا سکتا ہے۔ گراف کی ڈگری کی ترتیب کو ایسا ہونے دیں، اور اس کی سب سے بڑی قیمت ہونے دیں۔ پھر ایک تقسیم شدہ گراف ہے اگر اور صرف اس صورت میں اگر ایسا ہے، تو سب سے بڑی ڈگری والے عمودی حصے زیادہ سے زیادہ کلک بناتے ہیں، اور باقی عمودی حصے ایک آزاد سیٹ تشکیل دیتے ہیں۔ صوابدیدی گراف کی تقسیم اس بات کی پیمائش کرتی ہے کہ یہ عدم مساوات کس حد تک درست نہیں ہے۔ اگر کوئی گراف تقسیم شدہ گراف نہیں ہے، تو کنارے کے اندراج اور ہٹانے کی سب سے چھوٹی ترتیب جو اسے تقسیم شدہ گراف میں بناتی ہے، سب سے بڑی ڈگری کے ساتھ عمودی حصوں کے درمیان تمام گمشدہ کناروں کو شامل کرکے، اور باقی عمودی حصوں کے جوڑوں کے درمیان تمام کناروں کو ہٹا کر حاصل کی جا سکتی ہے۔ تقسیم اس ترتیب میں کارروائیوں کی تعداد کو شمار کرتا ہے۔ تقسیم شدہ گرافوں کی گنتی سے پتہ چلتا ہے کہ n کے ساتھ n-ورٹیکس تقسیم شدہ گراف بعض اسپرنر خاندانوں کے ساتھ ون ٹو ون خط و کتابت میں ہیں۔ اس حقیقت کو استعمال کرتے ہوئے، اس نے n عمودی پر غیر آئسومورفک تقسیم گراف کی تعداد کے لیے ایک فارمولا طے کیا۔ n کی چھوٹی اقدار کے لیے، جو n = 1 سے شروع ہوتی ہیں، یہ اعداد 1، 2، 4، 9، 21، 56، 164، 557، 2223، 10766، 64956، 501696، ہیں۔ اس گنتی کا نتیجہ پہلے بھی ثابت ہو چکا ہے۔ حوالہ جات نوٹ کریں۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ "غیر نشان زدہ مشترکہ اشیاء کی گنتی کا ایک اور طریقہ" (1990) کے طور پر ترجمہ کیا گیا، یو ایس ایس آر کی اکیڈمی آف سائنسز کے ریاضیاتی نوٹ 48 (6): 1239-1245،۔ ۔ ۔ اسپلٹ گراف پر ایک باب مارٹن چارلس گولمبک کی کتاب "الگورتھمک گراف تھیوری اینڈ پرفیکٹ گرافز" میں ظاہر ہوتا ہے۔ گراف خاندان گراف کی انٹرسیکشن کلاسیں کامل گراف