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