Queen's graph
ગણિતમાં, રાણીનો આલેખ એ એક દિશાહીન આલેખ છે જે ચેસબોર્ડ પર રાણીની તમામ કાનૂની ચાલ-ચેસ પીસ-નું પ્રતિનિધિત્વ કરે છે. આલેખમાં, દરેક શિરોબિંદુ ચેસબોર્ડ પર એક ચોરસને રજૂ કરે છે, અને દરેક ધાર એ એક કાનૂની ચાલ છે જે રાણી કરી શકે છે, એટલે કે, કોઈપણ સંખ્યામાં ચોરસ દ્વારા આડી, ઊભી અથવા કર્ણ ચાલ. જો ચેસબોર્ડમાં પરિમાણો હોય, તો પ્રેરિત આલેખને રાણીનો આલેખ કહેવામાં આવે છે. આલેખના સ્વતંત્ર સમૂહો બહુવિધ રાણીઓના પ્લેસમેન્ટને અનુરૂપ હોય છે જ્યાં કોઈ બે રાણીઓ એકબીજા પર હુમલો કરતી નથી. તેમનો અભ્યાસ આઠ રાણીઓની પઝલમાં કરવામાં આવે છે, જ્યાં આઠ બિન-આક્રમક રાણીઓને પ્રમાણભૂત ચેસબોર્ડ પર મૂકવામાં આવે છે. પ્રભુત્વ ધરાવતા સમૂહ રાણીઓની ગોઠવણીનું પ્રતિનિધિત્વ કરે છે જ્યાં દરેક ચોરસ પર રાણી દ્વારા હુમલો કરવામાં આવે છે અથવા કબજો કરવામાં આવે છે; પાંચ રાણીઓ, પરંતુ તેનાથી ઓછી નહીં, ચેસબોર્ડ પર પ્રભુત્વ ધરાવે છે. આલેખના રંગો દરેક ચોરસને રંગવાની રીતોને રજૂ કરે છે જેથી રાણી એક જ રંગના કોઈપણ બે ચોરસ વચ્ચે ખસેડી ન શકે; ચેસબોર્ડ માટે ઓછામાં ઓછા એન રંગો જરૂરી છે, પરંતુ બોર્ડ માટે 9 રંગો જરૂરી છે. ગુણધર્મો દરેક રાણીના આલેખ માટે હેમિલ્ટોનિયન ચક્ર હોય છે, અને આલેખ બે રીતે જોડાયેલા હોય છે (જો કોઈ એક શિરોબિંદુ દૂર કરવામાં આવે તો તે જોડાયેલા રહે છે). અને રાણીના આલેખના વિશેષ કિસ્સાઓ પૂર્ણ થયા છે. સ્વતંત્ર ગ્રાફનો એક સ્વતંત્ર સમૂહ ચેસબોર્ડ પર ઘણી રાણીઓના સ્થાનને અનુરૂપ છે જેમ કે કોઈ બે રાણીઓ એકબીજા પર હુમલો કરતી નથી. ચેસબોર્ડમાં, સૌથી મોટા સ્વતંત્ર સમૂહમાં મહત્તમ n શિરોબિંદુઓ હોય છે, કારણ કે કોઈ બે રાણીઓ એક જ પંક્તિ અથવા સ્તંભમાં હોઈ શકતી નથી. આ ઉપલી સીમા n = 2 અને n = 3 સિવાયના તમામ n માટે પ્રાપ્ત કરી શકાય છે. એન = 8 ના કિસ્સામાં, આ પરંપરાગત આઠ રાણીઓની કોયડો છે. પ્રભુત્વ રાણીના આલેખનો પ્રભુત્વશાળી સમૂહ રાણીઓના સ્થાનને અનુરૂપ છે જેમ કે ચેસબોર્ડ પરના દરેક ચોરસ પર રાણી દ્વારા હુમલો કરવામાં આવે છે અથવા કબજો કરવામાં આવે છે. ચેસબોર્ડ પર, પાંચ રાણીઓ પ્રભુત્વ જમાવી શકે છે, અને આ શક્ય ઓછામાં ઓછી સંખ્યા છે (ચાર રાણીઓ ઓછામાં ઓછા બે ચોરસને હુમલા વગર છોડી દે છે). પાંચ રાણીઓની આવી 4,860 પ્લેસમેન્ટ છે, જેમાં જ્યાં રાણીઓ નિયંત્રિત કરે છે તે સહિત તમામ કબજા હેઠળના ચોરસ, એટલે કે. તેઓ અનુક્રમે હુમલો કરે છે અને એકબીજાનું રક્ષણ કરે છે. આ પેટાજૂથમાં એવી જગ્યાઓ પણ છે જ્યાં રાણીઓ માત્ર મુખ્ય કર્ણ પર ચોરસ પર કબજો કરે છે (દા. ત. a1 થી h8 સુધી), અથવા બધા પેટા કર્ણ પર (દા. ત. a2 થી g8). બિન-લૂપિંગ લંબચોરસ ચેસબોર્ડને ટોરસ અથવા સિલિન્ડરથી બદલીને ગ્રાફમાં ફેરફાર કરવાથી લઘુત્તમ પ્રભુત્વ ધરાવતા સેટનું કદ ઘટીને ચાર થઈ જાય છે. રાણીનો આલેખ બોર્ડના કેન્દ્રમાં એક જ શિરોબિંદુ દ્વારા પ્રભુત્વ ધરાવે છે. રાણીના આલેખનું મધ્ય શિરોબિંદુ 8 શિરોબિંદુઓ સિવાય તમામને અડીને આવેલું છેઃ તે શિરોબિંદુઓ કે જે ઘોડાના આલેખનના મધ્ય શિરોબિંદુને અડીને આવેલા હોય છે. પ્રભુત્વ સંખ્યાઓ રાણીના આલેખની વર્ચસ્વ સંખ્યા d (n) ને સૌથી નાના પ્રભુત્વ ધરાવતા સમૂહના કદ તરીકે વ્યાખ્યાયિત કરે છે, અને કર્ણ વર્ચસ્વ સંખ્યા dd (n) એ સૌથી નાના પ્રભુત્વ ધરાવતા સમૂહના કદ તરીકે વ્યાખ્યાયિત કરે છે જે લાંબા કર્ણનો સબસેટ છે. નોંધ લો કે તમામ n. માટે સીમા પ્રાપ્ત થાય છે, પરંતુ માટે નહીં. વર્ચસ્વ સંખ્યા n માં રેખીય છે, જેના દ્વારા આપવામાં આવેલી સીમાઓ છેઃ d (n) ના પ્રારંભિક મૂલ્યો, માટે, 1,1,1,2,3,4,5,5,5 છે. Kn ને એવા ઉપગણનું મહત્તમ કદ માની લો કે જેમાં દરેક સંખ્યાની સમાનતા સમાન હોય અને કોઈ ત્રણ સંખ્યાઓ અંકગણિત પ્રગતિ ન બનાવે (સમૂહ "મધ્યબિંદુ-મુક્ત" હોય). રાણીના આલેખની કર્ણ વર્ચસ્વ સંખ્યા છે. સ્વતંત્ર વર્ચસ્વ નંબર ID (n) ને રાણીના આલેખમાં સૌથી નાના સ્વતંત્ર, પ્રબળ સમૂહના કદ તરીકે વ્યાખ્યાયિત કરો. તે જાણીતું છે. રંગ રાણીના આલેખનો રંગ એ દરેક શિરોબિંદુને રંગોની સોંપણી છે કે જેથી કોઈ પણ બે અડીને આવેલા શિરોબિંદુઓને સમાન રંગ આપવામાં ન આવે. દાખલા તરીકે, જો a8 લાલ રંગનો હોય તો a-ફાઇલ પરનો કોઈ અન્ય ચોરસ, આઠમો ક્રમ અથવા લાંબો કર્ણ લાલ રંગનો હોઈ શકતો નથી, કારણ કે રાણી a8 થી આમાંથી કોઈપણ ચોરસ પર જઈ શકે છે. આલેખની રંગીન સંખ્યા એ રંગોની સૌથી નાની સંખ્યા છે જેનો ઉપયોગ તેને રંગવા માટે કરી શકાય છે. રાણીના આલેખના કિસ્સામાં, ઓછામાં ઓછા n રંગો જરૂરી છે, કારણ કે ક્રમ અથવા ફાઇલમાં દરેક ચોરસને અલગ રંગની જરૂર હોય છે (એટલે કે. પંક્તિઓ અને સ્તંભો સમૂહ છે). રંગીન સંખ્યા બરાબર n છે જો (એટલે કે. n એ 6 ના ગુણાંક કરતાં એક વધારે અથવા એક ઓછું છે). રાણીના આલેખની રંગીન સંખ્યા 9 છે. જો સમૂહમાંથી કોઈપણ શિરોબિંદુને દૂર કરવાથી સમૂહના પડોશમાં ફેરફાર થાય છે એટલે કે શિરોબિંદુઓનો સમૂહ અનિવાર્ય છે. દરેક શિરોબિંદુ માટે, એક અડીને આવેલું શિરોબિંદુ હોય છે જે સમૂહમાં અન્ય કોઈપણ શિરોબિંદુને અડીને નથી. આ રાણીઓના સમૂહને અનુરૂપ છે જે દરેક અનન્ય રીતે ઓછામાં ઓછા એક ચોરસને નિયંત્રિત કરે છે. રાણીના આલેખ પર અનિવાર્ય સમૂહના મહત્તમ કદ IR (n) ની લાક્ષણિકતા દર્શાવવી મુશ્કેલ છે; જાણીતા મૂલ્યોમાં પર્સ્યુટ-ઇવેઝન ગેમનો સમાવેશ થાય છે રાણીના આલેખ પર પીછો-ચોરીની રમતને ધ્યાનમાં લો જે નીચેના નિયમો અનુસાર રમાય છેઃ સફેદ રાણી એક ખૂણામાં શરૂ થાય છે અને કાળી રાણી વિરુદ્ધ ખૂણામાં. ખેલાડીઓ વૈકલ્પિક ચાલ કરે છે, જેમાં રાણીને અડીને આવેલા શિરોબિંદુ પર ખસેડવાનો સમાવેશ થાય છે, જે (આડા, ઊભી અથવા ત્રાંસા) પસાર થયા વિના અથવા વિરુદ્ધ રાણીની બાજુમાં આવેલા શિરોબિંદુ પર ઉતર્યા વિના પહોંચી શકાય છે. આ રમત સફેદ દ્વારા જોડી બનાવવાની વ્યૂહરચના સાથે જીતી શકાય છે. કિંગ્સ ગ્રાફ નાઈટનો ગ્રાફ રુકનો ગ્રાફ બિશપનો ગ્રાફ સંદર્ભો ગાણિતિક ચેસ સમસ્યાઓ ગ્રાફના પેરામેટ્રિક પરિવારો પણ જુઓ.