Series–parallel graph
આલેખ સિદ્ધાંતમાં, શ્રેણી-સમાંતર આલેખ એ બે વિશિષ્ટ શિરોબિંદુઓ ધરાવતા આલેખ છે જેને ટર્મિનલ કહેવાય છે, જે બે સરળ રચના કામગીરીઓ દ્વારા પુનરાવર્તિત રીતે રચાય છે. તેનો ઉપયોગ શ્રેણીબદ્ધ અને સમાંતર વિદ્યુત સર્કિટના નમૂના બનાવવા માટે થઈ શકે છે. વ્યાખ્યા અને પરિભાષા આ સંદર્ભમાં આલેખ શબ્દનો અર્થ બહુલેખન થાય છે. શ્રેણી-સમાંતર આલેખને વ્યાખ્યાયિત કરવાની ઘણી રીતો છે. નીચેની વ્યાખ્યા મૂળભૂત રીતે ડેવિડ એપસ્ટીન દ્વારા ઉપયોગમાં લેવાતી વ્યાખ્યાને અનુસરે છે. બે-ટર્મિનલ આલેખ (TTG) એ બે વિશિષ્ટ શિરોબિંદુઓ સાથેનો આલેખ છે, s અને t જેને અનુક્રમે સ્રોત અને સિંક કહેવાય છે. બે TTG X અને Y ની સમાંતર રચના Pc = Pc (X, Y) એ TTG છે જે X અને Y આલેખના અસંબદ્ધ જોડાણમાંથી X અને Y ના સ્રોતોને ભેળવીને Pc નો સ્રોત બનાવે છે અને X અને Y ના સિંકને ભેળવીને Pc નું સિંક બનાવે છે. બે TTG X અને Y ની શ્રેણી રચના SC = SC (X, Y) એ TTG છે જે X અને Y આલેખના અસંબદ્ધ જોડાણમાંથી X ના સિંકને Y ના સ્ત્રોત સાથે ભેળવીને બનાવવામાં આવી છે. X નો સ્રોત SC નો સ્રોત બને છે અને Y નું સિંક SC નું સિંક બને છે. બે-ટર્મિનલ શ્રેણી-સમાંતર આલેખ (ટી. ટી. એસ. પી. જી.) એ એક આલેખ છે જે શ્રેણી અને સમાંતર રચનાઓના ક્રમ દ્વારા બનાવવામાં આવી શકે છે, જે સોંપાયેલ ટર્મિનલ સાથે એક-ધાર ગ્રાફ કે 2 ની નકલોના સમૂહથી શરૂ થાય છે. વ્યાખ્યા 1. છેવટે, ગ્રાફને શ્રેણી-સમાંતર (એસ. પી.-ગ્રાફ) કહેવામાં આવે છે, જો તે ટી. ટી. એસ. પી. જી. હોય, જ્યારે તેના કેટલાક બે શિરોબિંદુઓને સ્રોત અને સિંક તરીકે ગણવામાં આવે છે. તેવી જ રીતે શ્રેણી-સમાંતર ડિગ્રાફ્સને વ્યાખ્યાયિત કરી શકાય છે, જે સિંગલ-આર્ક ગ્રાફ્સની નકલોમાંથી બનાવવામાં આવે છે, જેમાં સ્ત્રોતથી સિંક સુધી નિર્દેશિત ચાપ હોય છે. વૈકલ્પિક વ્યાખ્યા નીચેની વ્યાખ્યા આલેખના સમાન વર્ગને સ્પષ્ટ કરે છે. વ્યાખ્યા 2. ગ્રાફ એ એસ. પી.-ગ્રાફ છે, જો તેને નીચેની કામગીરીઓના ક્રમ દ્વારા કે2માં ફેરવી શકાયઃ એક જ ધાર સાથે સમાંતર ધારની જોડીને બદલવી જે તેમના સામાન્ય અંતિમ બિંદુઓને જોડે છે. ગુણધર્મો દરેક શ્રેણી-સમાંતર આલેખમાં મહત્તમ 2 ત્રિ-પહોળાઈ અને મહત્તમ 2 શાખા-પહોળાઈ હોય છે. ખરેખર, ગ્રાફની ત્રિ-પહોળાઈ વધુમાં વધુ 2 હોય છે જો અને માત્ર ત્યારે જ જો તેની શાખા-પહોળાઈ વધુમાં વધુ 2 હોય, જો અને માત્ર ત્યારે જ જો દરેક દ્વિ-જોડાયેલ ઘટક શ્રેણી-સમાંતર ગ્રાફ હોય. મહત્તમ શ્રેણી-સમાંતર આલેખ, આલેખ કે જેમાં તેમની શ્રેણી-સમાંતર રચનાને નષ્ટ કર્યા વિના કોઈ વધારાની ધાર ઉમેરી શકાતી નથી, તે બરાબર 2-વૃક્ષો છે. 2-જોડાયેલ શ્રેણી-સમાંતર આલેખ K4 માટે કોઈ સબગ્રાફ હોમોમોર્ફિક ન હોવા દ્વારા વર્ગીકૃત થયેલ છે. શ્રેણીબદ્ધ સમાંતર આલેખ પણ તેમના કાનના વિઘટન દ્વારા વર્ગીકૃત થઈ શકે છે. કોમ્પ્યુટેશનલ જટિલતા એસ. પી.-ગ્રાફને રેખીય સમયમાં ઓળખી શકાય છે અને તેમની શ્રેણી-સમાંતર વિઘટન રેખીય સમયમાં પણ બનાવી શકાય છે. ચોક્કસ પ્રકારના વિદ્યુત નેટવર્કનું નમૂના હોવા ઉપરાંત, આ આલેખ કોમ્પ્યુટેશનલ કોમ્પ્લેક્સિટી થિયરીમાં રસ ધરાવે છે, કારણ કે સંખ્યાબંધ પ્રમાણભૂત આલેખ સમસ્યાઓ એસ. પી.-આલેખ પર રેખીય સમયમાં ઉકેલી શકાય છે, જેમાં મહત્તમ મેળ ખાતા, મહત્તમ સ્વતંત્ર સમૂહ, લઘુત્તમ પ્રભુત્વ ધરાવતા સમૂહ અને હેમિલ્ટોનિયન પૂર્ણતાનો સમાવેશ થાય છે. આમાંની કેટલીક સમસ્યાઓ સામાન્ય આલેખ માટે એન. પી.-પૂર્ણ છે. ઉકેલ એ હકીકત પર ભાર મૂકે છે કે જો આમાંથી કોઈ એક સમસ્યાનો જવાબ બે એસ. પી.-આલેખ માટે જાણીતો હોય, તો વ્યક્તિ ઝડપથી તેમની શ્રેણી અને સમાંતર રચનાઓનો જવાબ શોધી શકે છે. સામાન્યીકરણ સામાન્યીકૃત શ્રેણી-સમાંતર આલેખ (જી. એસ. પી.-આલેખ) એ ઉલ્લેખિત સમસ્યાઓ માટે સમાન અલ્ગોરિધમિક કાર્યક્ષમતા સાથે એસ. પી.-આલેખનું વિસ્તરણ છે. જી. એસ. પી.-ગ્રાફના વર્ગમાં એસ. પી.-ગ્રાફ અને બાહ્ય સમતલ ગ્રાફના વર્ગોનો સમાવેશ થાય છે. જી. એસ. પી. આલેખને વ્યાખ્યા 2 દ્વારા નિર્દિષ્ટ કરી શકાય છે, જે લટકતા શિરોબિંદુ (ડિગ્રી 1 નું શિરોબિંદુ) ને દૂર કરવાની ત્રીજી કામગીરી સાથે વધારવામાં આવે છે. વૈકલ્પિક રીતે, વ્યાખ્યા 1 ને નીચેની કામગીરી સાથે વધારી શકાય છે. બે TTG X અને Y ના સ્ત્રોત S = M (X, Y) નું વિલિનીકરણ એ TTG છે જે X અને Y આલેખના અસંબદ્ધ જોડાણમાંથી X ના સ્ત્રોતને Y ના સ્ત્રોત સાથે વિલિનીકરણ કરીને બનાવવામાં આવ્યું છે. X નો સ્રોત અને સિંક અનુક્રમે P નો સ્રોત અને સિંક બની જાય છે. એસ. પી. ક્યુ. આર. વૃક્ષ એ એક વૃક્ષ માળખું છે જેને મનસ્વી 2-વર્ટેક્સ-જોડાયેલ આલેખ માટે વ્યાખ્યાયિત કરી શકાય છે. તેમાં એસ-નોડ્સ છે, જે શ્રેણી-સમાંતર આલેખમાં શ્રેણી રચના કામગીરીને અનુરૂપ છે, પી-નોડ્સ, જે શ્રેણી-સમાંતર આલેખમાં સમાંતર રચના કામગીરીને અનુરૂપ છે, અને આર-નોડ્સ, જે શ્રેણી-સમાંતર રચના કામગીરીને અનુરૂપ નથી. 2-જોડાયેલ આલેખ શ્રેણી-સમાંતર હોય છે જો અને માત્ર ત્યારે જ જો તેના એસ. પી. ક્યુ. આર. વૃક્ષમાં કોઈ આર-નોડ ન હોય. થ્રેશોલ્ડ આલેખ ગ્રાફ હેનર પોલીટોપ શ્રેણી-સમાંતર આંશિક ક્રમ સંદર્ભ આલેખ પરિવારો આલેખ કામગીરી પ્લાનર આલેખ પણ જુઓ.