Forcing graph
આલેખ સિદ્ધાંતમાં, દબાણ આલેખ એ છે કે જેની ઘનતા નક્કી કરે છે કે આલેખ ક્રમ અર્ધ-યાદૃચ્છિક છે કે નહીં. આ શબ્દ સૌપ્રથમ 1989 માં ચુંગ, ગ્રેહામ અને વિલ્સન દ્વારા રચવામાં આવ્યો હતો, અને ગ્રાફ સિક્વન્સમાં સ્યુડોરાન્ડમના અભ્યાસમાં ફોર્સ્ડ ગ્રાફ મહત્વપૂર્ણ ભૂમિકા ભજવે છે. વ્યાખ્યાઓ ચાલો, સબગ્રાફ ઘનતા તરીકે ઓળખાય છે (ખાસ કરીને, ની ધાર ઘનતા છે). આલેખના ક્રમને અર્ધ-યાદૃચ્છિક કહેવામાં આવે છે, જો તમામ આલેખ માટે, ધારની ઘનતા અમુકની નજીક પહોંચે છે અને જેમ જેમ વધે છે તેમ પહોંચે છે, તો તેમાં ધારની સંખ્યા ક્યાં છે. સાહજિક રીતે, આનો અર્થ એ છે કે આપેલ ધાર ઘનતા સાથે ગ્રાફ ક્રમમાં ગ્રાફ હોમોમોર્ફિઝમ્સની સંખ્યા હોય છે જે કોઈ રેન્ડમ ગ્રાફ ક્રમમાં અપેક્ષા રાખશે. ગ્રાફને ફોર્સિંગ કહેવામાં આવે છે જો તમામ ગ્રાફ સિક્વન્સ માટે જ્યાં અનંત સુધી પહોંચે છે, જો પહોંચે તો અર્ધ-યાદૃચ્છિક હોય છે. બીજા શબ્દોમાં કહીએ તો, માત્ર એક જ આલેખની હોમોમોર્ફિઝમ ઘનતા ચકાસીને ગ્રાફનો ક્રમ અર્ધ-યાદૃચ્છિક છે તેની ચકાસણી કરી શકાય છે. ગ્રાફોનની ભાષાનો ઉપયોગ કરીને ગ્રાફને દબાણ કરવાની બીજી વ્યાખ્યા છે. ઔપચારિક રીતે, ગ્રાફને ફોર્સિંગ કહેવામાં આવે છે જો દરેક ગ્રાફોન સ્થિર હોય. સાહજિક રીતે, તે અર્થમાં છે કે આ વ્યાખ્યાઓ સંબંધિત છે. સતત ગ્રાફોન એર્ડોસ-રેની રેન્ડમ ગ્રાફનું પ્રતિનિધિત્વ કરે છે, તેથી કોઈ તેની અર્ધ-રેન્ડમ ગ્રાફ સાથે ગાઢ સંબંધ હોવાની અપેક્ષા રાખી શકે છે. હકીકતમાં, આ વ્યાખ્યાઓ સમકક્ષ છે. ઉદાહરણો ધ્યાનમાં લેવાનો પ્રથમ દબાણ આલેખ એ 4-ચક્ર છે, કારણ કે તે અર્ધ-યાદૃચ્છિકતાની અન્ય શરતો સાથે ગાઢ સંબંધ ધરાવે છે. ચુંગ, ગ્રેહામ અને વિલ્સન દ્વારા એક જ પેપરમાં દર્શાવવામાં આવ્યું હતું કે દરેક સમ ચક્ર અને સાથે ફોર્મના સંપૂર્ણ દ્વિપક્ષી આલેખ દબાણકારી છે. કોનલોન, ફોક્સ અને સુદાકોવે આ છેલ્લા પરિણામનું વિસ્તરણ કરીને એક ભાગમાં બે શિરોબિંદુઓ સાથેના તમામ દ્વિપક્ષી આલેખનો સમાવેશ કર્યો હતો જે બીજા ભાગમાં સંપૂર્ણ છે. ગ્રાફનો પરિવાર જ્યારે પણ બધા માટે નજીક આવે છે ત્યારે તે અર્ધ-યાદૃચ્છિક હોય છે. બળજબરીથી પરિવારોને લાક્ષણિકતા આપવી એ બળજબરીથી આલેખ દર્શાવવા કરતાં વધુ પડકારજનક છે, તેથી એવા ઘણા ઓછા લોકો છે જે જાણીતા છે. જાણીતા દબાણકારી પરિવારોમાં નીચેનાનો સમાવેશ થાય છેઃ, ક્યાં હકારાત્મક પૂર્ણાંક છે;, ક્યાં અને સાથે હકારાત્મક પૂર્ણાંકો છે;, ક્યાં; અને, ક્યાં અને. દબાણકારી અનુમાન 2004માં સ્કોકન અને થોમા દ્વારા રજૂ કરવામાં આવ્યું હતું અને 2010માં કોનલોન, ફોક્સ અને સુદાકોવ દ્વારા તેને ઔપચારિક સ્વરૂપ આપવામાં આવ્યું હતું. તે ફોર્સ્ડ ગ્રાફ માટે લાક્ષણિકતા પ્રદાન કરે છે, જે નીચે પ્રમાણે ઔપચારિક છેઃ આ દાવાની એક દિશા જાણીતી છે. ચુંગ, ગ્રેહામ અને વિલ્સને દર્શાવ્યું હતું કે જો આલેખમાં વિચિત્ર ચક્ર હોય, તો તે દબાણ કરી શકાતું નથી, તેથી જો આલેખ દબાણ કરી રહ્યો હોય, તો તે દ્વિપક્ષી હોવું જોઈએ. ઉપરાંત, કોનલોન, ફોક્સ અને સુદાકોવે એવી દલીલ કરી હતી કે દરેક જંગલ માટે સંપર્ક ત્યારે થાય છે જ્યારે તે લગભગ નિયમિત (અને જરૂરી નથી કે અર્ધ-યાદૃચ્છિક) આલેખ ક્રમ હોય. આમ, ફોર્સિંગ ગ્રાફ દ્વિપક્ષી હોવો જોઈએ અને તેમાં ઓછામાં ઓછું એક ચક્ર હોવું જોઈએ. બીજી દિશા હજુ સાબિત થવાની બાકી છે, પરંતુ આ બંને ગુણધર્મો ન હોય તેવો કોઈ ફોર્સિંગ ગ્રાફ મળી આવ્યો નથી. દબાણકારી અનુમાન પણ સિડોરેન્કોના અનુમાનને સૂચવે છે, જે ક્ષેત્રમાં લાંબા સમયથી ચાલતું અનુમાન છે. તે જાણીતું છે કે તમામ દબાણ આલેખ સિડોરેન્કો છે, તેથી જો દબાણ અનુમાન સાચું છે, તો ઓછામાં ઓછું એક ચક્ર ધરાવતા તમામ દ્વિપક્ષી આલેખ સિડોરેન્કો હશે. વૃક્ષો સિડોરેન્કો હોવાથી, તમામ દ્વિપક્ષી આલેખ સિડોરેન્કો હશે. સંદર્ભો આલેખ પરિવારો