Well-covered graph
گراف تھیوری میں، ایک اچھی طرح سے ڈھکا ہوا گراف ایک غیر ہدایت شدہ گراف ہے جس میں ہر کم سے کم ورٹیکس کور کا سائز ہر دوسرے کم سے کم ورٹیکس کور کے برابر ہوتا ہے۔ مساوی طور پر، یہ وہ گراف ہیں جن میں تمام زیادہ سے زیادہ آزاد سیٹوں کا سائز برابر ہوتا ہے۔ اچھی طرح سے ڈھکے ہوئے گراف کی وضاحت کی گئی اور سب سے پہلے 1970 میں مائیکل ڈی پلمر نے ان کا مطالعہ کیا۔ اچھی طرح سے ڈھکے ہوئے گرافوں میں تمام مکمل گراف، متوازن مکمل دو طرفہ گراف شامل ہیں، اور روک کے گراف جن کے عمودی حصے شطرنج بورڈ کے مربع کی نمائندگی کرتے ہیں اور کنارے شطرنج کے روک کی چالوں کی نمائندگی کرتے ہیں۔ اچھی طرح سے ڈھکے ہوئے کیوبک گرافوں کی معروف خصوصیات، اچھی طرح سے ڈھکے ہوئے پنجے سے پاک گراف، اور اعلی گرتھ کے اچھی طرح سے ڈھکے ہوئے گراف ان گرافوں کو کثیر الجہتی وقت میں پہچاننے کی اجازت دیتے ہیں، لیکن یہ جانچنا کہ آیا دوسری قسم کے گراف اچھی طرح سے ڈھکے ہوئے ہیں، ایک سی او این پی مکمل مسئلہ ہے۔ تعریف گراف میں ورٹیکس کا احاطہ عمودی حصوں کا ایک مجموعہ ہے جو گراف کے ہر کنارے کو چھوتا ہے۔ ایک ورٹیکس کور کم سے کم، یا ناقابل تلافی ہوتا ہے، اگر اس سے کسی ورٹیکس کو ہٹانے سے کورنگ پراپرٹی تباہ ہو جائے گی۔ یہ کم سے کم ہے اگر کم عمودی کے ساتھ کوئی دوسرا عمودی احاطہ نہ ہو۔ ایک اچھی طرح سے ڈھکا ہوا گراف وہ ہوتا ہے جس میں ہر کم سے کم احاطہ بھی کم سے کم ہوتا ہے۔ اصل مقالے میں اچھی طرح سے ڈھکے ہوئے گراف کی وضاحت کرتے ہوئے، پلمر لکھتے ہیں کہ یہ "واضح طور پر اس خاصیت کے مساوی" ہے کہ ہر دو کم سے کم کور میں ایک دوسرے کے برابر عمودی نمبر ہوتے ہیں۔ گراف میں ایک آزاد سیٹ عمودی کا ایک مجموعہ ہے جس میں سے کوئی دو ایک دوسرے سے متصل نہیں ہیں۔ اگر گراف میں ورٹیکس کور ہے، تو اس کی تکمیل ایک آزاد سیٹ ہونی چاہیے، اور اس کے برعکس۔ کم سے کم ورٹیکس کور ہے اگر اور صرف اس صورت میں جب اس کی تکمیل زیادہ سے زیادہ آزاد سیٹ ہو، اور کم سے کم ورٹیکس کور ہے اگر اور صرف اس صورت میں جب اس کی تکمیل زیادہ سے زیادہ آزاد سیٹ ہو۔ لہذا، ایک اچھی طرح سے ڈھکا ہوا گراف، مساوی طور پر، ایک گراف ہے جس میں ہر زیادہ سے زیادہ آزاد سیٹ کا سائز ایک جیسا ہوتا ہے، یا ایک گراف جس میں ہر زیادہ سے زیادہ آزاد سیٹ زیادہ سے زیادہ ہوتا ہے۔ اصل مقالے میں اچھی طرح سے ڈھکے ہوئے گرافوں کی وضاحت کرتے ہوئے، یہ تعریفیں منسلک گرافوں تک محدود تھیں، حالانکہ وہ منقطع گرافوں کے لیے بھی معنی خیز ہیں۔ کچھ بعد کے مصنفین نے رابطے کی ضرورت کو کمزور ضرورت کے ساتھ تبدیل کر دیا ہے کہ ایک اچھی طرح سے ڈھکے ہوئے گراف میں کوئی الگ تھلگ عمودی نہیں ہونا چاہیے۔ جڑے ہوئے اچھی طرح سے ڈھکے ہوئے گراف اور الگ تھلگ عمودی کے بغیر اچھی طرح سے ڈھکے ہوئے گراف دونوں کے لیے، کوئی ضروری عمودی، عمودی نہیں ہو سکتے جو ہر کم از کم عمودی احاطے سے تعلق رکھتے ہوں۔ مزید برآں، ہر اچھی طرح سے ڈھکا ہوا گراف ورٹیکس کا احاطہ کرنے کے لیے ایک اہم گراف ہے اس معنی میں کہ، ہر ورٹیکس کے لیے، گراف سے حذف کرنے سے ایک چھوٹا کم از کم ورٹیکس کور والا گراف تیار ہوتا ہے۔ گراف کا آزادی کمپلیکس ایک آسان کمپلیکس ہے جس میں ہر آزاد سیٹ کے لیے ایک سمپلیکس ہوتا ہے۔ ایک سادہ کمپلیکس کو خالص کہا جاتا ہے اگر اس کی تمام زیادہ سے زیادہ سادگی ایک جیسی ہو، تو ایک اچھی طرح سے ڈھکا ہوا گراف مساوی طور پر خالص آزادی کمپلیکس والا گراف ہوتا ہے۔ مثال چار یا پانچ لمبائی کا ایک سائیکل گراف اچھی طرح سے احاطہ کرتا ہے: ہر معاملے میں، ہر زیادہ سے زیادہ آزاد سیٹ کا سائز دو ہوتا ہے۔ سات لمبائی کا ایک چکر، اور تین لمبائی کا راستہ بھی اچھی طرح سے ڈھکا ہوا ہے۔ ہر مکمل گراف اچھی طرح سے احاطہ کرتا ہے: ہر زیادہ سے زیادہ آزاد سیٹ ایک واحد سرے پر مشتمل ہوتا ہے۔ اسی طرح، ہر کلسٹر گراف (مکمل گراف کا ایک جداگانہ اتحاد) اچھی طرح سے احاطہ کرتا ہے۔ ایک مکمل دو طرفہ گراف اچھی طرح سے احاطہ کرتا ہے اگر اس کی دو طرفہ تقسیم کے دونوں اطراف میں عمودی کی تعداد مساوی ہو، کیونکہ یہ اس کے صرف دو زیادہ سے زیادہ آزاد سیٹ ہیں۔ مثلث سے پاک گراف کا تکمیل گراف جس میں کوئی الگ تھلگ عمودی نہیں ہے اچھی طرح سے ڈھکا ہوا ہے: اس میں دو سے بڑا کوئی آزاد سیٹ نہیں ہے، اور ہر ایک عمودی کو دو عمودی آزاد سیٹ تک بڑھایا جا سکتا ہے۔ رک کا گراف اچھی طرح سے ڈھکا ہوا ہے: اگر کوئی شطرنج بورڈ پر رکوں کا کوئی سیٹ رکھتا ہے تاکہ کوئی دو رک ایک دوسرے پر حملہ نہ کریں، تو ہمیشہ زیادہ غیر حملہ آور روکوں کو رکھنا جاری رکھنا ممکن ہے جب تک کہ شطرنج بورڈ کی ہر قطار اور کالم پر ایک نہ ہو۔ وہ گراف جس کے عمودی حصے ایک سادہ کثیر الاضحی کے اخترن ہوتے ہیں اور جس کے کنارے ایک دوسرے کو عبور کرنے والے اخترن کے جوڑوں کو جوڑتے ہیں وہ اچھی طرح سے ڈھکے ہوئے ہوتے ہیں، کیونکہ اس کے زیادہ سے زیادہ آزاد سیٹ کثیر الاضحی کے مثلث ہوتے ہیں اور تمام مثلثوں کے کنارے ایک جیسے ہوتے ہیں۔ اگر کوئی-ورٹیکس گراف ہے، تو ایک کنارے والے گراف کا جڑا ہوا پروڈکٹ (یعنی، نئے عمودی حصوں کو شامل کرکے تشکیل دیا گیا گراف، ہر ایک ڈگری ایک اور ہر ایک ایک الگ سرے سے متصل) اچھی طرح سے ڈھکا ہوا ہے۔ کیونکہ، ایک زیادہ سے زیادہ آزاد سیٹ لازمی طور پر ایک صوابدیدی آزاد سیٹ پر مشتمل ہونا چاہیے جو تکمیل سیٹ کے ڈگری-ایک پڑوسیوں کے ساتھ مل کر ہونا چاہیے، اور اس لیے اس کا سائز ہونا چاہیے۔ زیادہ عام طور پر، کسی بھی گراف کو ایک کلک کور (کلکس میں عمودی حصوں کی تقسیم) کے ساتھ مل کر دیا گیا ہے، ہر کلک میں ایک اور عمودی حصے کو شامل کرکے تشکیل دیا گیا گراف اچھی طرح سے ڈھکا ہوا ہے۔ جڑی ہوئی مصنوعات اس تعمیر کا خاص معاملہ ہے جب ایک ورٹیکس کلکس پر مشتمل ہوتا ہے۔ اس طرح، ہر گراف ایک اچھی طرح سے ڈھکے ہوئے گراف کا ایک محرک ذیلی گراف ہے۔ دو طرفہ، بہت اچھی طرح سے ڈھکے ہوئے گراف، اور گرتھ ایک بہت اچھی طرح سے ڈھکے ہوئے گراف کی وضاحت کرتے ہیں کہ وہ ایک اچھی طرح سے ڈھکے ہوئے گراف (ممکنہ طور پر منقطع، لیکن کوئی الگ تھلگ عمودی نہیں) ہے جس میں ہر زیادہ سے زیادہ آزاد سیٹ (اور اس وجہ سے ہر کم سے کم عمودی احاطہ بھی) بالکل نصف پر مشتمل ہوتا ہے۔ عمودی. اس تعریف میں گراف کی جڑیں اور ایک جدید گراف شامل ہیں۔ اس میں، مثال کے طور پر، دو طرفہ اچھی طرح سے ڈھکے ہوئے گراف بھی شامل ہیں جن کا مطالعہ کیا گیا ہے اور: دو طرفہ گراف میں الگ تھلگ عمودی کے بغیر، کسی بھی دو طرفہ کے دونوں اطراف زیادہ سے زیادہ آزاد سیٹ (اور کم سے کم عمودی احاطہ) بناتے ہیں، لہذا اگر گراف اچھی طرح سے ڈھکا ہوا ہے تو دونوں اطراف میں یکساں طور پر بہت سے عمودی ہونے چاہئیں۔ عمودی کے ساتھ اچھی طرح سے ڈھکے ہوئے گراف میں، الگ تھلگ عمودی کے بغیر، زیادہ سے زیادہ آزاد سیٹ کا سائز زیادہ سے زیادہ ہوتا ہے، اس لیے بہت اچھی طرح سے ڈھکے ہوئے گراف اچھی طرح سے ڈھکے ہوئے گراف ہوتے ہیں جن میں زیادہ سے زیادہ آزاد سیٹ کا سائز جتنا ممکن ہو اتنا بڑا ہوتا ہے۔ ایک دو طرفہ گراف اچھی طرح سے احاطہ کرتا ہے اگر اور صرف اس صورت میں جب اس میں اس پراپرٹی کے ساتھ کامل مماثلت ہو جو، ہر کنارے کے لیے، پڑوسیوں کا محرک ذیلی گراف اور ایک مکمل دو طرفہ گراف بناتا ہے۔ ملاپ کے لحاظ سے خصوصیت کو دو طرفہ گرافوں سے بہت اچھی طرح سے ڈھکے ہوئے گرافوں تک بڑھایا جا سکتا ہے: ایک گراف بہت اچھی طرح سے احاطہ کرتا ہے اگر اور صرف اس صورت میں جب اس کا مندرجہ ذیل دو خصوصیات کے ساتھ کامل ملاپ ہو: مثلث کا کوئی کنارہ نہیں ہے، اور اگر کا کنارہ تین کنارے والے راستے کا مرکزی کنارہ ہے، تو راستے کے دو اختتامی نکات ملحقہ ہونے چاہئیں۔ مزید برآں، اگر بہت اچھی طرح سے احاطہ کیا گیا ہے، تو ہر کامل ملاپ ان خصوصیات کو مطمئن کرتا ہے۔ درخت دو طرفہ گراف کا ایک خاص معاملہ ہے، اور یہ جانچنا کہ آیا کوئی درخت اچھی طرح سے ڈھکا ہوا ہے، اسے اچھی طرح سے ڈھکے ہوئے دو طرفہ گراف کی خصوصیت کے ایک بہت آسان خاص معاملے کے طور پر سنبھالا جا سکتا ہے: اگر دو سے زیادہ عمودی درخت ہے، تو یہ اچھی طرح سے ڈھکا ہوا ہے اگر اور صرف اس صورت میں جب درخت کا ہر غیر پتوں والا نوڈ بالکل ایک پتی سے متصل ہو۔ یہی خصوصیت ان گرافوں پر بھی لاگو ہوتی ہے جو مقامی طور پر درخت کی طرح ہوتے ہیں، اس معنی میں کہ ہر سرے کے کم قطر والے محلے چکنا ہوتے ہیں: اگر کسی گراف کا گرتھ آٹھ یا اس سے زیادہ ہے (تاکہ، ہر سرے کے لیے، تین کے فاصلے کے اندر عمودی کا ذیلی گراف چکنا ہو) تو یہ اچھی طرح سے ڈھکا ہوا ہے اگر اور صرف اس صورت میں جب ایک سے زیادہ ڈگری کے ہر سرے کا بالکل ایک پڑوسی ہو۔ قریب سے متعلق لیکن زیادہ پیچیدہ خصوصیت پانچ یا اس سے زیادہ دائرے کے اچھی طرح سے ڈھکے ہوئے گرافوں پر لاگو ہوتی ہے۔ باقاعدگی اور منصوبہ بندی کیوبک (3-باقاعدہ) اچھی طرح سے ڈھکے ہوئے گرافوں کی درجہ بندی کی گئی ہے: وہ کم رابطے والے کیوبک گراف کے تین لامحدود خاندانوں کے ساتھ مل کر سات 3 منسلک مثالوں پر مشتمل ہیں۔ تین جڑے ہوئے مکعب اچھی طرح سے ڈھکے ہوئے سات گراف مکمل گراف، مثلث پریزم اور پینٹاگونل پریزم کے گراف، ڈیورر گراف، یوٹیلیٹی گراف، یوٹیلیٹی گراف سے حاصل کردہ آٹھ ورٹیکس گراف Y-δ ٹرانسفارم، اور 14-ورٹیکس جنرلائزڈ پیٹرسن گراف ہیں۔ ان گرافوں میں سے پہلے چار پلانر گراف ہیں۔ وہ صرف چار کیوبک پولی ہیڈرل گراف (سادہ کنویکس پولی ہیڈرا کے گراف) ہیں جو اچھی طرح سے ڈھکے ہوئے ہیں۔ چار گراف (دو پریزم، ڈیورر گراف، اور) عام پیٹرسن گراف ہیں۔ 1-اور 2-جڑے ہوئے مکعب اچھی طرح سے ڈھکے ہوئے گراف تمام راستے یا سائیکل کے نوڈس کو گراف کے تین ٹکڑوں سے تبدیل کرکے بنائے جاتے ہیں جو لیبل لگاتے ہیں، اور۔ ٹکڑے یا کسی سائیکل کے نوڈس یا کسی راستے کے اندرونی نوڈس کو تبدیل کرنے کے لیے استعمال کیے جا سکتے ہیں، جبکہ ٹکڑا راستے کے دو اختتامی نوڈس کو تبدیل کرنے کے لیے استعمال کیا جاتا ہے۔ ٹکڑے میں ایک پل ہوتا ہے، لہذا اس متبادل عمل کو راستے پر انجام دینے اور کچھ پاتھ نوڈس (اور باقی نوڈس کے لیے دیگر دو ٹکڑے) کو تبدیل کرنے کے لیے ٹکڑے کا استعمال کرنے کا نتیجہ 1-ورٹیکس سے منسلک مکعب اچھی طرح سے ڈھکا ہوا گراف ہے۔ تمام 1-ورٹیکس سے منسلک مکعب اچھی طرح سے ڈھکے ہوئے گرافوں کی یہ شکل ہوتی ہے، اور اس طرح کے تمام گراف ہموار ہوتے ہیں۔ 2-ورٹیکس سے منسلک مکعب اچھی طرح سے ڈھکے ہوئے گراف کی دو قسمیں ہیں۔ ان دو خاندانوں میں سے ایک سائیکل کے نوڈس کو ٹکڑوں سے بدل کر تشکیل پاتا ہے، جس میں کم از کم دو ٹکڑے قسم کے ہوتے ہیں۔ اس قسم کا گراف پلانر ہوتا ہے اگر اور صرف اس صورت میں جب اس میں قسم کے کوئی ٹکڑے نہ ہوں۔ دوسرا خاندان راستے کے نوڈس کو قسم کے ٹکڑوں سے تبدیل کرکے تشکیل پاتا ہے اور اس طرح کے تمام گراف طیارہ دار ہوتے ہیں۔ تین جہتوں میں اچھی طرح سے ڈھکے ہوئے سادہ پولی ہیڈرا کی خصوصیت کی تکمیل کرتے ہوئے، محققین نے اچھی طرح سے ڈھکے ہوئے سادہ پولی ہیڈرا، یا مساوی طور پر اچھی طرح سے ڈھکے ہوئے زیادہ سے زیادہ پلانر گراف پر بھی غور کیا ہے۔ پانچ یا اس سے زیادہ چوٹیوں والے ہر زیادہ سے زیادہ طیارہ گراف میں ورٹیکس کنیکٹوٹی 3، 4، یا 5 ہوتی ہے۔ کوئی اچھی طرح سے ڈھکے ہوئے 5 منسلک زیادہ سے زیادہ پلانر گراف نہیں ہیں، اور صرف چار 4 منسلک اچھی طرح سے ڈھکے ہوئے زیادہ سے زیادہ پلانر گراف ہیں: باقاعدہ آکٹھیڈرون کے گراف، پینٹاگنل ڈائپیرامڈ، سنب ڈسپینائڈ، اور ایک بے قاعدہ پولی ہیڈرون (ایک نان کنویکس ڈیلٹا ہیڈرون) جس میں 12 عمودی، 30 کنارے، اور 20 مثلث چہرے ہیں۔ تاہم، لامحدود طور پر بہت سے 3 جڑے ہوئے اچھی طرح سے ڈھکے ہوئے زیادہ سے زیادہ طیارہ گراف موجود ہیں۔ مثال کے طور پر، اگر ایک-ورٹیکس زیادہ سے زیادہ طیارہ گراف میں جداگانہ مثلث کے چہرے ہیں، تو یہ چہرے ایک کلیک کور بنائیں گے۔ لہذا، کلیک کور کی تعمیر، جو ان گرافوں کے لیے ان مثلثوں میں سے ہر ایک کو مرکزی سرے پر ملنے والے تین نئے مثلثوں میں تقسیم کرنے پر مشتمل ہے، ایک اچھی طرح سے ڈھکا ہوا زیادہ سے زیادہ طیارہ گراف تیار کرتا ہے۔ پیچیدگی کی جانچ کرنا کہ آیا گراف میں مختلف سائز کے دو زیادہ سے زیادہ آزاد سیٹ ہیں، این پی مکمل ہے ؛ یعنی، تکمیل کے طور پر، یہ جانچنا کہ آیا گراف اچھی طرح سے ڈھکا ہوا ہے، سی او این پی مکمل ہے۔ اگرچہ گرافوں میں زیادہ سے زیادہ آزاد سیٹ تلاش کرنا آسان ہے جو اچھی طرح سے احاطہ کیے جانے کے لیے جانا جاتا ہے، لیکن کسی الگورتھم کے لیے یہ بھی NP-مشکل ہے کہ وہ آؤٹ پٹ کے طور پر، تمام گرافوں پر، یا تو زیادہ سے زیادہ آزاد سیٹ یا اس بات کی ضمانت دے کہ ان پٹ اچھی طرح سے احاطہ نہیں کیا گیا ہے۔ اس کے برعکس، یہ جانچنا ممکن ہے کہ آیا دیا ہوا گراف کثیر الجہتی وقت میں بہت اچھی طرح سے احاطہ کرتا ہے۔ ایسا کرنے کے لیے، ان کناروں پر مشتمل ذیلی گراف تلاش کریں جو ایک بہت اچھی طرح سے ڈھکے ہوئے گراف میں مماثل کنارے کی دو خصوصیات کو پورا کرتے ہیں، اور پھر یہ جانچنے کے لیے کہ آیا اس میں کامل مماثلت ہے یا نہیں، مماثل الگورتھم کا استعمال کریں۔ کچھ مسائل جو صوابدیدی گرافوں کے لیے این پی مکمل ہیں، جیسے کہ ہیملٹنین سائیکل تلاش کرنے کا مسئلہ، بہت اچھی طرح سے ڈھکے ہوئے گرافوں کے لیے کثیر الجہتی وقت میں بھی حل کیا جا سکتا ہے۔ اگر ہر زیادہ سے زیادہ ملاپ زیادہ سے زیادہ ہو تو گراف کو مساوی کہا جاتا ہے ؛ یعنی، اگر اس کا لائن گراف اچھی طرح سے ڈھکا ہوا ہو تو یہ مساوی ہے۔ زیادہ مضبوطی سے اسے بے ترتیب طور پر مماثل کہا جاتا ہے اگر ہر زیادہ سے زیادہ مماثلت ایک کامل مماثلت ہو۔ صرف مربوط بے ترتیب طور پر مماثل گراف مکمل گراف اور متوازن مکمل دو طرفہ گراف ہیں۔ یہ جانچنا ممکن ہے کہ آیا لائن گراف، یا زیادہ عام طور پر پنکھ سے پاک گراف، کثیر الجہتی وقت میں اچھی طرح سے ڈھکا ہوا ہے۔ گھیر پانچ یا اس سے زیادہ کے ساتھ اچھی طرح سے ڈھکے ہوئے گرافوں کی خصوصیات، اور اچھی طرح سے ڈھکے ہوئے گراف جو 3-باقاعدہ ہیں، ان گرافوں کو پہچاننے کے لیے موثر کثیر الجہتی وقت کے الگورتھم کا باعث بھی بنتے ہیں۔ حوالہ جات نوٹ کریں۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ ۔ جیسا کہ حوالہ دیا گیا ہے۔ ۔ ۔ ۔ گراف خاندان