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