Dijoin
ગણિતમાં, ડીજોઇન એ નિર્દેશિત આલેખની ધારોનો સબસેટ છે, જેમાં એ ગુણધર્મ હોય છે કે જે ડીજોઇનની દરેક ધારને સંકોચાય છે અને મજબૂત રીતે જોડાયેલ આલેખ ઉત્પન્ન કરે છે. તેવી જ રીતે, ડીજોઇન એ કિનારીઓનો એક ઉપસમૂહ છે, જેમાં દરેક ડિકટ માટે, ડિકટને પાર કરતી ઓછામાં ઓછી એક ધારનો સમાવેશ થાય છે. અહીં, ડિકટ એ શિરોબિંદુઓનું બે ઉપગણમાં વિભાજન છે, જેથી બંને ઉપગણમાં અંતિમ બિંદુ ધરાવતી દરેક ધાર પ્રથમ ઉપગણથી બીજા ઉપગણ તરફ નિર્દેશિત થાય. આ વિસ્તારમાં વણઉકેલાયેલી સમસ્યા, વુડલનું અનુમાન જણાવે છે કે કોઈપણ નિર્દેશિત આલેખમાં ડિકટમાં કિનારીઓની લઘુતમ સંખ્યા (અનવેટેડ મિનિમમ ક્લોઝર) એ આલેખમાં મળી શકે તેવા ડિસજોઈન્ટ ડીજોઈન્સની મહત્તમ સંખ્યા (ડીજોઈન્સની પેકિંગ) જેટલી હોય છે. જેક એડમંડ્સ અને રિક જાઇલ્સ દ્વારા રજૂ કરાયેલ અનુમાનના આંશિક ભારિત સંસ્કરણને એલેક્ઝાન્ડર શ્રિવરે નકારી કાઢ્યું હતું. લ્યુચેસી-યંગર થીયરમ જણાવે છે કે કોઈ પણ નિર્દેશિત આલેખમાં ડાઇજોઇનનું લઘુતમ કદ, આલેખમાં મળી શકે તેવા ડિસજોઈન્ટ ડિકટ્સની મહત્તમ સંખ્યા બરાબર છે. ભારિત આલેખમાં લઘુતમ વજનનો જોડ બહુપદી સમયમાં મળી શકે છે, અને તે સબમોડ્યુલર પ્રવાહ સમસ્યાનો એક ખાસ કેસ છે. સમતલીય આલેખમાં, જોડી અને પ્રતિક્રિયા ચાપ સમૂહો બેવડા ખ્યાલો છે. સમતલમાં જડિત નિર્દેશિત આલેખનો બેવડા આલેખ, આપેલ આલેખના દરેક ચહેરા માટે શિરોબિંદુ સાથેનો આલેખ છે, અને જ્યારે અનુરૂપ બે ચહેરાઓ ધાર દ્વારા અલગ કરવામાં આવે છે ત્યારે બે બેવડા શિરોબિંદુઓ વચ્ચેની બેવડી ધાર છે. દરેક બેવડી ધાર મૂળ આલેખ ધારમાંથી એકને પાર કરે છે, જે 90° ઘડિયાળની દિશામાં ફરે છે. પ્રતિસાદ ચાપ સમૂહ એ ધારોનો એક ઉપગણ છે જેમાં દરેક નિર્દેશિત ચક્રમાંથી ઓછામાં ઓછી એક ધારનો સમાવેશ થાય છે. આપેલ આલેખમાં જોડાવા માટે, ધારોનો અનુરૂપ સમૂહ બેવડા આલેખમાં નિર્દેશિત કટ બનાવે છે, અને તેનાથી ઊલટું. આ બે સમસ્યાઓ વચ્ચેનો આ સંબંધ પ્રતિક્રિયા ચાપ સમૂહ સમસ્યાને સમતલીય આલેખ માટે અસરકારક રીતે હલ કરવાની મંજૂરી આપે છે, તેમ છતાં તે અન્ય પ્રકારના આલેખ માટે એન. પી.-હાર્ડ છે. સંદર્ભો નિર્દેશિત આલેખ