Series–parallel graph
گراف تھیوری میں، سیریز متوازی گراف وہ گراف ہوتے ہیں جن میں دو ممتاز عمودی ہوتے ہیں جنہیں ٹرمینلز کہا جاتا ہے، جو دو سادہ کمپوزیشن آپریشنز کے ذریعے بار بار تشکیل پاتے ہیں۔ انہیں سیریز اور متوازی برقی سرکٹس کے ماڈل کے لیے استعمال کیا جا سکتا ہے۔ تعریف اور اصطلاحات اس تناظر میں گراف کی اصطلاح کا مطلب ملٹی گراف ہے۔ سیریز متوازی گراف کی وضاحت کرنے کے کئی طریقے ہیں۔ مندرجہ ذیل تعریف بنیادی طور پر ڈیوڈ ایپسٹین کے استعمال کردہ تعریف کی پیروی کرتی ہے۔ دو ٹرمینل گراف (ٹی ٹی جی) ایک گراف ہے جس میں دو ممتاز عمودی، ایس اور ٹی کو بالترتیب ماخذ اور سنک کہا جاتا ہے۔ دو ٹی ٹی جی ایکس اور وائی کی متوازی ساخت پی سی = پی سی (ایکس، وائی) ایک ٹی ٹی جی ہے جو گراف ایکس اور وائی کے جداگانہ اتحاد سے ایکس اور وائی کے ذرائع کو ضم کر کے پی سی کا منبع بناتی ہے اور ایکس اور وائی کے سنک کو ضم کر کے پی سی کا سنک بناتی ہے۔ دو ٹی ٹی جیز ایکس اور وائی کی سیریز کمپوزیشن ایس سی = ایس سی (ایکس، وائی) ایک ٹی ٹی جی ہے جو گراف ایکس اور وائی کے جداگانہ اتحاد سے ایکس کے سنک کو وائی کے ماخذ کے ساتھ ضم کرکے بنایا گیا ہے۔ X کا منبع SC کا منبع بن جاتا ہے اور Y کا سنک SC کا سنک بن جاتا ہے۔ دو ٹرمینل سیریز متوازی گراف (ٹی ٹی ایس پی جی) ایک ایسا گراف ہے جسے تفویض کردہ ٹرمینلز کے ساتھ سنگل ایج گراف کے 2 کی کاپیوں کے سیٹ سے شروع ہونے والی سیریز اور متوازی کمپوزیشن کی ترتیب سے بنایا جا سکتا ہے۔ تعریف 1. آخر میں، گراف کو سیریز متوازی (ایس پی گراف) کہا جاتا ہے، اگر یہ ٹی ٹی ایس پی جی ہے جب اس کے کچھ دو عمودی حصوں کو ماخذ اور سنک سمجھا جاتا ہے۔ اسی طرح کوئی بھی سیریز متوازی ڈیگراف کی وضاحت کر سکتا ہے، جو واحد آرک گراف کی نقول سے بنائے گئے ہیں، جس میں آرکس ماخذ سے سنک تک ہوتے ہیں۔ متبادل تعریف درج ذیل تعریف گراف کی ایک ہی کلاس کی وضاحت کرتی ہے۔ تعریف 2. گراف ایک ایس پی گراف ہے، اگر اسے مندرجہ ذیل کارروائیوں کے سلسلے کے ذریعے کے 2 میں تبدیل کیا جا سکتا ہے: متوازی کناروں کے جوڑے کو ایک کنارے سے تبدیل کرنا جو ان کے مشترکہ اختتامی نکات کو جوڑتا ہے۔ کناروں کے جوڑے کی جگہ ایک کنارے کے ساتھ ایس یا ٹی کے علاوہ ڈگری 2 کے کسی دوسرے سرے سے تبدیل کرنا۔ خصوصیات ہر سلسلہ متوازی گراف کی تین چوڑائی زیادہ سے زیادہ 2 اور شاخ چوڑائی زیادہ سے زیادہ 2 ہوتی ہے۔ درحقیقت، کسی گراف کی تین چوڑائی زیادہ سے زیادہ 2 ہوتی ہے اگر اور صرف اس صورت میں جب اس کی شاخ چوڑائی زیادہ سے زیادہ 2 ہو، اگر اور صرف اس صورت میں جب ہر دو جڑا ہوا جزو سیریز متوازی گراف ہو۔ زیادہ سے زیادہ سیریز متوازی گراف، گراف جن میں ان کی سیریز متوازی ساخت کو تباہ کیے بغیر کوئی اضافی کنارے شامل نہیں کیے جا سکتے، بالکل 2 درخت ہیں۔ 2 منسلک سیریز متوازی گراف کی خصوصیت یہ ہے کہ K4 کے لیے کوئی ذیلی گراف ہومیومورفک نہیں ہے۔ سلسلہ وار متوازی گراف بھی ان کے کان کے سڑنے سے نمایاں ہو سکتے ہیں۔ کمپیوٹیشنل پیچیدگی ایس پی گراف کو لکیری وقت میں پہچانا جا سکتا ہے اور ان کی سیریز متوازی سڑنا لکیری وقت میں بھی بنایا جا سکتا ہے۔ بعض قسم کے برقی نیٹ ورک کا نمونہ ہونے کے علاوہ، یہ گراف کمپیوٹیشنل پیچیدگی کے نظریہ میں دلچسپی رکھتے ہیں، کیونکہ ایس پی گراف پر متعدد معیاری گراف کے مسائل لکیری وقت میں حل کیے جا سکتے ہیں، بشمول زیادہ سے زیادہ ملاپ، زیادہ سے زیادہ آزاد سیٹ، کم سے کم غالب سیٹ اور ہیملٹنین تکمیل۔ ان میں سے کچھ مسائل عام گراف کے لیے این پی مکمل ہیں۔ حل اس حقیقت کا فائدہ اٹھاتا ہے کہ اگر ان میں سے کسی ایک مسئلے کے جوابات دو ایس پی گراف کے لیے جانے جاتے ہیں، تو کوئی بھی ان کی سیریز اور متوازی کمپوزیشن کا جواب جلدی سے تلاش کر سکتا ہے۔ عمومی سیریز متوازی گراف (جی ایس پی گراف) ایس پی گراف کی توسیع ہیں جن میں مذکور مسائل کے لیے یکساں الگورتھمک کارکردگی ہوتی ہے۔ جی ایس پی گراف کی کلاس میں ایس پی گراف اور آؤٹر پلینر گراف کی کلاسیں شامل ہیں۔ جی ایس پی گراف کی وضاحت ڈیفینیشن 2 کے ذریعے کی جا سکتی ہے جسے لٹکتے ہوئے ورٹیکس (ڈگری 1 کا ورٹیکس) کو ہٹانے کے تیسرے آپریشن کے ساتھ بڑھایا جاتا ہے۔ متبادل طور پر، تعریف 1 کو مندرجہ ذیل آپریشن کے ساتھ بڑھایا جا سکتا ہے۔ ماخذ کا دو ٹی ٹی جی ایکس اور وائی کے ایس = ایم (ایکس، وائی) کو ضم کرنا ایک ٹی ٹی جی ہے جو گراف ایکس اور وائی کے جداگانہ اتحاد سے ایکس کے ماخذ کو وائی کے ماخذ کے ساتھ ضم کرکے بنایا گیا ہے۔ ایکس کا ماخذ اور سنک بالترتیب پی کا ماخذ اور سنک بن جاتے ہیں۔ ایس پی کیو آر درخت ایک درخت کا ڈھانچہ ہے جس کی وضاحت صوابدیدی 2-ورٹیکس سے منسلک گراف کے لیے کی جا سکتی ہے۔ اس میں ایس-نوڈس ہیں، جو سیریز متوازی گرافوں میں سیریز کمپوزیشن آپریشنز سے مشابہت رکھتے ہیں، پی-نوڈس، جو سیریز متوازی گرافوں میں متوازی کمپوزیشن آپریشنز سے مطابقت رکھتے ہیں، اور آر-نوڈس، جو سیریز متوازی کمپوزیشن آپریشنز سے مطابقت نہیں رکھتے ہیں۔ 2 منسلک گراف سیریز متوازی ہوتا ہے اگر اور صرف اس صورت میں جب اس کے ایس پی کیو آر ٹری میں کوئی آر نوڈس نہ ہوں۔ تھریشولڈ گراف گراف ہینر پولیٹوپ سیریز متوازی جزوی ترتیب حوالہ جات گراف خاندان گراف آپریشنز پلانر گراف بھی دیکھیں۔