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