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