Graph pebbling
ગ્રાફ પેબ્લિંગ એ એક ગાણિતિક રમત છે જે ગ્રાફ પર તેના દરેક શિરોબિંદુ પર શૂન્ય અથવા વધુ કાંકરા સાથે રમાય છે. 'ગેમ પ્લે' પેબલિંગ ચાલની શ્રેણીથી બનેલું છે. આલેખ પર કાંકરાની ચાલમાં ઓછામાં ઓછા બે કાંકરા સાથેનું શિરોબિંદુ પસંદ કરવું, તેમાંથી બે કાંકરા દૂર કરવા અને એકને નજીકના શિરોબિંદુમાં ઉમેરવાનો સમાવેશ થાય છે (બીજા દૂર કરેલા કાંકરાને રમતમાંથી કાઢી નાખવામાં આવે છે). π (G), ગ્રાફ G ની પેબ્લિંગ સંખ્યા, એ સૌથી નીચી કુદરતી સંખ્યા n છે જે નીચેની શરતને સંતોષે છેઃ ગ્રાફમાં કોઈપણ લક્ષ્ય અથવા 'મૂળ' શિરોબિંદુ અને ગ્રાફ પર n કાંકરાઓની કોઈપણ પ્રારંભિક ગોઠવણીને જોતાં, તે શક્ય છે, પેબ્લિંગ ચાલની શ્રેણી પછી, નવી ગોઠવણી સુધી પહોંચવું જેમાં નિયુક્ત મૂળ શિરોબિંદુ એક અથવા વધુ કાંકરા ધરાવે છે. ઉદાહરણ તરીકે, 2 શિરોબિંદુઓ અને તેમને જોડતી 1 ધારવાળા આલેખ પર પેબ્લિંગ નંબર 2 છે. આલેખના શિરોબિંદુઓ પર બે કાંકરા ગમે તે રીતે મૂકવામાં આવે, તે આલેખમાં કોઈપણ શિરોબિંદુ પર કાંકરાને ખસેડવાનું હંમેશા શક્ય છે. ગ્રાફ પેબ્લિંગના કેન્દ્રિય પ્રશ્નોમાંથી એક આપેલ ગ્રાફ G માટે π (G) નું મૂલ્ય છે. પેબ્લિંગના અન્ય વિષયોમાં કવર પેબ્લિંગ, શ્રેષ્ઠ પેબ્લિંગ, વર્ચસ્વ કવર પેબ્લિંગ, સીમાઓ અને પેબ્લિંગ સંખ્યાઓ માટે થ્રેશોલ્ડ, તેમજ ઊંડા ગ્રાફનો સમાવેશ થાય છે. π (G)-આલેખની પેબ્લિંગ સંખ્યા પેબ્લિંગની રમત સૌપ્રથમ લગારિયાસ અને સાક્સ દ્વારા સંખ્યા સિદ્ધાંતમાં ચોક્કસ સમસ્યાને ઉકેલવા માટેના સાધન તરીકે સૂચવવામાં આવી હતી. 1989માં એફઆરકે. ચંગે સાહિત્યમાં આ ખ્યાલ રજૂ કર્યો અને પેબ્લિંગ નંબર, π (G) ને વ્યાખ્યાયિત કર્યો. n શિરોબિંદુઓ પર સંપૂર્ણ આલેખ માટે કાંકરાઓની સંખ્યા સરળતાથી n હોવાનું ચકાસી શકાય છેઃ જો આપણી પાસે આલેખ પર મૂકવા માટે (n−1) કાંકરા હોય, તો આપણે લક્ષ્ય સિવાય દરેક શિરોબિંદુ પર એક કાંકરા મૂકી શકીએ. કોઈ પણ શિરોબિંદુમાં બે કે તેથી વધુ કાંકરા હોતા નથી, તેથી કોઈ ચાલ શક્ય નથી, તેથી લક્ષ્ય પર કાંકરા મૂકવા અશક્ય છે. આમ, પેબ્લિંગ સંખ્યા n − 1 કરતા મોટી હોવી જોઈએ. n કાંકરા આપવામાં આવે તો, બે સંભવિત કિસ્સાઓ છે. જો દરેક શિરોબિંદુમાં એક કાંકરા હોય, તો કોઈ ચાલની જરૂર નથી. જો કોઈ શિરોબિંદુ ખુલ્લું હોય, તો ઓછામાં ઓછું એક અન્ય શિરોબિંદુ પર બે કાંકરા હોવા જોઈએ, અને એક કાંકરાની ચાલ કાંકરાને સંપૂર્ણ આલેખમાં કોઈપણ લક્ષ્ય શિરોબિંદુમાં ઉમેરવાની મંજૂરી આપે છે. આલેખના પરિવારો માટે π (G) પેબ્લિંગ નંબર આલેખના નીચેના પરિવારો માટે જાણીતો છેઃ, જ્યાં n શિરોબિંદુઓ પર સંપૂર્ણ આલેખ છે. જ્યાં n શિરોબિંદુઓ પર પાથ ગ્રાફ છે. જ્યાં n શિરોબિંદુઓ પર ચક્ર આલેખ છે. ગ્રેહામના પેબલિંગ અનુમાનમાં રોનાલ્ડ ગ્રેહામને આ અનુમાનનો શ્રેય આપવામાં આવ્યો છે કે આલેખના કાર્ટેશિયન ઉત્પાદનની પેબલિંગ સંખ્યા ઉત્પાદનમાં પરિબળોની પેબલિંગ સંખ્યાઓના ઉત્પાદનની સૌથી વધુ સમકક્ષ છે. આને ગ્રેહામની પેબલિંગ અનુમાન તરીકે ઓળખવામાં આવે છે. ખાસ કિસ્સાઓ જાણીતા હોવા છતાં, તે વણઉકેલાયેલી રહે છે. γ (G)-ગ્રાફ ક્રુલ એટ અલનો કવર પેબ્લિંગ નંબર. કવર પેબ્લિંગનો ખ્યાલ રજૂ કર્યો. γ (G), આલેખની આવરણ કંકણ સંખ્યા એ કંકણની ઓછામાં ઓછી સંખ્યા છે, જેથી કંકણની કોઈપણ પ્રારંભિક ગોઠવણીમાંથી, કંકણની ચાલની શ્રેણી પછી, આલેખ આવરી લેવામાં આવેઃ દરેક શિરોબિંદુ પર ઓછામાં ઓછું એક કંકણ હોય. સ્ટેકિંગ થીયરમ તરીકે ઓળખાતું પરિણામ કોઈપણ આલેખ માટે કવર પેબ્લિંગ નંબર શોધે છે. સ્ટેકિંગ થીયરમ સ્ટેકિંગ થીયરમ અનુસાર, જ્યારે બધા કાંકરા એક જ શિરોબિંદુ પર મૂકવામાં આવે છે ત્યારે કાંકરાઓનું પ્રારંભિક રૂપરેખાંકન થાય છે જેને આવરી લેવા માટે સૌથી વધુ કાંકરાઓની જરૂર પડે છે. આ અવલોકનના આધારે, G માં દરેક શિરોબિંદુ v માટે વ્યાખ્યાયિત કરો, જ્યાં d (u, v) એ u થી v વચ્ચેનું અંતર સૂચવે છે. આલેખના પરિવારો માટે γ (G) કવર પેબ્લિંગ નંબર આલેખના નીચેના પરિવારો માટે જાણીતો છેઃ, જ્યાં n શિરોબિંદુઓ પર સંપૂર્ણ આલેખ છે. જ્યાં n શિરોબિંદુઓ પર પાથ છે. જ્યાં n શિરોબિંદુઓ પર ચક્ર આલેખ છે. આ પણ જુઓ પેબલ રમત અવકાશ સંદર્ભોનો પુરાવો વધુ વાંચન આલેખ અપરિવર્તન