Series–parallel graph
গ্রাফ তত্ত্বে, সিরিজ-সমান্তরাল গ্রাফগুলি হল দুটি বিশিষ্ট শীর্ষযুক্ত গ্রাফ যা টার্মিনাল নামে পরিচিত, যা দুটি সহজ রচনা ক্রিয়াকলাপ দ্বারা পুনরাবৃত্তভাবে গঠিত হয়। এগুলি সিরিজ এবং সমান্তরাল বৈদ্যুতিক সার্কিট মডেল করতে ব্যবহার করা যেতে পারে। সংজ্ঞা এবং পরিভাষা এই প্রসঙ্গে গ্রাফ শব্দের অর্থ মাল্টিগ্রাফ। সিরিজ-সমান্তরাল গ্রাফ সংজ্ঞায়িত করার বিভিন্ন উপায় রয়েছে। নিম্নলিখিত সংজ্ঞাটি মূলত ডেভিড এপস্টেইনের ব্যবহৃত সংজ্ঞাটিকে অনুসরণ করে। একটি দ্বি-টার্মিনাল গ্রাফ (টিটিজি) হল দুটি বিশিষ্ট শীর্ষযুক্ত একটি গ্রাফ, যা যথাক্রমে উৎস এবং সিঙ্ক নামে পরিচিত। দুটি টিটিজি এক্স এবং ওয়াই-এর সমান্তরাল গঠন পিসি = পিসি (এক্স, ওয়াই) হল একটি টিটিজি যা এক্স এবং ওয়াই গ্রাফের বিচ্ছিন্ন মিলন থেকে এক্স এবং ওয়াই-এর উৎসগুলিকে একত্রিত করে পিসির উৎস তৈরি করে এবং এক্স এবং ওয়াই-এর সিঙ্কগুলিকে একত্রিত করে পিসির সিঙ্ক তৈরি করে। দুটি টিটিজি এক্স এবং ওয়াই-এর সিরিজ গঠন এসসি = এসসি (এক্স, ওয়াই) হল একটি টিটিজি যা এক্স এবং ওয়াই গ্রাফের বিচ্ছিন্ন মিলন থেকে তৈরি করা হয়েছে এক্স-এর সিঙ্ককে ওয়াই-এর উৎসের সাথে একত্রিত করে। এক্স-এর উৎস হয়ে ওঠে এসসি-র উৎস এবং ওয়াই-এর সিঙ্ক হয়ে যায় এসসি-র সিঙ্ক। টু-টার্মিনাল সিরিজ-প্যারালাল গ্রাফ (টি. টি. এস. পি. জি) হল এমন একটি গ্রাফ যা নির্দিষ্ট টার্মিনাল সহ একক প্রান্তের গ্রাফ কে2-এর অনুলিপিগুলির একটি সেট থেকে শুরু করে সিরিজ এবং সমান্তরাল রচনার একটি ক্রম দ্বারা নির্মিত হতে পারে। সংজ্ঞা 1। পরিশেষে, একটি গ্রাফকে সিরিজ-প্যারালাল (এস. পি-গ্রাফ) বলা হয়, যদি এটি একটি টি. টি. এস. পি. জি হয় যখন এর দুটি শীর্ষকে উৎস এবং সিঙ্ক হিসাবে বিবেচনা করা হয়। একইভাবে কেউ সিরিজ-সমান্তরাল ডিগ্রাফগুলি সংজ্ঞায়িত করতে পারে, যা একক-খিলান গ্রাফের অনুলিপি থেকে নির্মিত, উৎস থেকে সিঙ্ক পর্যন্ত নির্দেশিত খিলান সহ। বিকল্প সংজ্ঞা নিম্নলিখিত সংজ্ঞাটি গ্রাফের একই শ্রেণীকে নির্দিষ্ট করে। সংজ্ঞা 2। একটি গ্রাফ হল একটি এস. পি-গ্রাফ, যদি এটি নিম্নলিখিত ক্রিয়াকলাপগুলির একটি ক্রম দ্বারা কে2-এ রূপান্তরিত হতে পারেঃ একটি জোড়া সমান্তরাল প্রান্তের প্রতিস্থাপন একটি একক প্রান্তের সাথে যা তাদের সাধারণ শেষ বিন্দুকে সংযুক্ত করে একটি জোড়া প্রান্তের প্রতিস্থাপন একটি একক প্রান্তের সাথে এস বা টি ব্যতীত অন্য ডিগ্রি 2-এর শীর্ষে ঘটে। বৈশিষ্ট্য প্রতিটি সিরিজ-সমান্তরাল গ্রাফের ত্রি-প্রস্থ সর্বাধিক 2 এবং শাখা-প্রস্থ সর্বাধিক 2 থাকে। প্রকৃতপক্ষে, একটি গ্রাফের সর্বাধিক 2-এর ত্রি-প্রস্থ থাকে যদি এবং শুধুমাত্র যদি এটির সর্বাধিক 2-এর শাখা-প্রস্থ থাকে, যদি এবং শুধুমাত্র যদি প্রতিটি দ্বি-সংযুক্ত উপাদান একটি সিরিজ-সমান্তরাল গ্রাফ হয়। সর্বাধিক সিরিজ-সমান্তরাল গ্রাফ, গ্রাফ যেখানে তাদের সিরিজ-সমান্তরাল কাঠামো ধ্বংস না করে কোনও অতিরিক্ত প্রান্ত যুক্ত করা যায় না, ঠিক 2-গাছ। 2-সংযুক্ত সিরিজ-সমান্তরাল গ্রাফগুলি কে4-এর কোনও সাবগ্রাফ হোমিওমরফিক না থাকার দ্বারা চিহ্নিত করা হয়। সিরিজের সমান্তরাল গ্রাফগুলি তাদের কানের পচন দ্বারাও চিহ্নিত করা যেতে পারে। গণনামূলক জটিলতা এস. পি-গ্রাফগুলি রৈখিক সময়ে স্বীকৃত হতে পারে এবং তাদের সিরিজ-সমান্তরাল পচন রৈখিক সময়েও তৈরি করা যেতে পারে। নির্দিষ্ট ধরনের বৈদ্যুতিক নেটওয়ার্কের একটি মডেল হওয়া ছাড়াও, এই গ্রাফগুলি গণনামূলক জটিলতা তত্ত্বে আগ্রহী, কারণ এস. পি-গ্রাফগুলিতে রৈখিক সময়ে বেশ কয়েকটি স্ট্যান্ডার্ড গ্রাফ সমস্যা সমাধানযোগ্য, যার মধ্যে রয়েছে সর্বাধিক মিল, সর্বাধিক স্বাধীন সেট, ন্যূনতম প্রভাবশালী সেট এবং হ্যামিল্টনিয়ান সমাপ্তি। এই সমস্যাগুলির মধ্যে কয়েকটি সাধারণ গ্রাফের জন্য এনপি-সম্পূর্ণ। সমাধানটি এই বিষয়টিকে পুঁজি করে যে, যদি এই সমস্যাগুলির মধ্যে একটির উত্তর দুটি এস. পি-গ্রাফের জন্য জানা যায়, তবে কেউ দ্রুত তাদের সিরিজ এবং সমান্তরাল রচনার উত্তর খুঁজে পেতে পারে। সাধারণীকরণ সাধারণীকৃত সিরিজ-সমান্তরাল গ্রাফ (জি. এস. পি-গ্রাফ) হল উল্লিখিত সমস্যাগুলির জন্য একই অ্যালগরিদমিক দক্ষতা সহ এস. পি-গ্রাফের একটি সম্প্রসারণ। জি. এস. পি-গ্রাফের শ্রেণীতে এস. পি-গ্রাফ এবং আউটারপ্ল্যানার গ্রাফের শ্রেণী অন্তর্ভুক্ত। জি. এস. পি গ্রাফগুলি সংজ্ঞা 2 দ্বারা নির্দিষ্ট করা যেতে পারে যা একটি ঝুলন্ত শীর্ষ (ডিগ্রি 1 এর শীর্ষ) মুছে ফেলার তৃতীয় ক্রিয়াকলাপের সাথে বর্ধিত। বিকল্পভাবে, সংজ্ঞা 1 নিম্নলিখিত অপারেশনের সাথে বর্ধিত করা যেতে পারে। দুটি টিটিজি এক্স এবং ওয়াই-এর উৎস এস = এম (এক্স, ওয়াই)-কে একত্রিত করে একটি টিটিজি তৈরি করা হয়েছে এক্স এবং ওয়াই গ্রাফের বিচ্ছিন্ন মিলন থেকে এক্স-এর উৎসকে ওয়াই-এর উৎসের সাথে একত্রিত করে। এক্স-এর উৎস এবং ডুব যথাক্রমে পি-এর উৎস এবং ডুব হয়ে ওঠে। একটি এস. পি. কিউ. আর গাছ হল একটি গাছের কাঠামো যা একটি নির্বিচারে 2-ভার্টেক্স-সংযুক্ত গ্রাফের জন্য সংজ্ঞায়িত করা যেতে পারে। এটিতে এস-নোড রয়েছে, যা সিরিজ-সমান্তরাল গ্রাফের সিরিজ কম্পোজিশন অপারেশনের অনুরূপ, পি-নোড, যা সিরিজ-সমান্তরাল গ্রাফের সমান্তরাল কম্পোজিশন অপারেশনের অনুরূপ এবং আর-নোড রয়েছে, যা সিরিজ-সমান্তরাল কম্পোজিশন অপারেশনের সাথে সামঞ্জস্যপূর্ণ নয়। একটি 2-সংযুক্ত গ্রাফ সিরিজ-সমান্তরাল হয় যদি এবং শুধুমাত্র যদি এর এসপিকিউআর ট্রি-তে কোনও আর-নোড না থাকে। আরও দেখুন থ্রেশহোল্ড গ্রাফ গ্রাফ হ্যানার পলিটোপ সিরিজ-সমান্তরাল আংশিক ক্রম রেফারেন্স গ্রাফ পরিবার গ্রাফ অপারেশন প্ল্যানার গ্রাফ