Queen's graph
ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ರಾಣಿಯ ರೇಖಾಚಿತ್ರವು ಚತುರಂಗದ ಹಲಗೆಯ ಮೇಲೆ ರಾಣಿಯ ಎಲ್ಲಾ ಕಾನೂನುಬದ್ಧ ಚಲನೆಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ನಿರ್ದೇಶಿಸದ ರೇಖಾಚಿತ್ರವಾಗಿದೆ. ರೇಖಾಚಿತ್ರದಲ್ಲಿ, ಪ್ರತಿ ಶೃಂಗವು ಚದುರಂಗ ಫಲಕದ ಮೇಲೆ ಒಂದು ಚೌಕವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ, ಮತ್ತು ಪ್ರತಿ ಅಂಚು ರಾಣಿ ಮಾಡಬಹುದಾದ ಕಾನೂನುಬದ್ಧ ಚಲನೆ, ಅಂದರೆ, ಯಾವುದೇ ಸಂಖ್ಯೆಯ ಚೌಕಗಳಿಂದ ಸಮತಲ, ಲಂಬ ಅಥವಾ ಕರ್ಣೀಯ ಚಲನೆ. ಚದುರಂಗ ಫಲಕವು ಆಯಾಮಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಪ್ರೇರಿತ ರೇಖಾಚಿತ್ರವನ್ನು ರಾಣಿಯ ರೇಖಾಚಿತ್ರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಗ್ರಾಫ್ಗಳ ಸ್ವತಂತ್ರ ಸೆಟ್ಗಳು ಅನೇಕ ರಾಣಿಯರ ನಿಯೋಜನೆಗಳಿಗೆ ಅನುಗುಣವಾಗಿರುತ್ತವೆ, ಅಲ್ಲಿ ಯಾವುದೇ ಇಬ್ಬರು ರಾಣಿಯರು ಪರಸ್ಪರ ದಾಳಿ ಮಾಡುತ್ತಿಲ್ಲ. ಅವರನ್ನು ಎಂಟು ರಾಣಿಯರ ಒಗಟುಗಳಲ್ಲಿ ಅಧ್ಯಯನ ಮಾಡಲಾಗುತ್ತದೆ, ಅಲ್ಲಿ ಎಂಟು ಆಕ್ರಮಣಕಾರಿಯಲ್ಲದ ರಾಣಿಯರನ್ನು ಪ್ರಮಾಣಿತ ಚದುರಂಗ ಫಲಕದಲ್ಲಿ ಇರಿಸಲಾಗುತ್ತದೆ. ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ಗಳು ರಾಣಿಯರ ವ್ಯವಸ್ಥೆಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಚೌಕದ ಮೇಲೆ ರಾಣಿಯು ದಾಳಿ ಮಾಡುತ್ತಾಳೆ ಅಥವಾ ಆಕ್ರಮಿಸಿಕೊಳ್ಳುತ್ತಾಳೆ; ಐದು ರಾಣಿಯರು, ಆದರೆ ಕಡಿಮೆ ಇಲ್ಲ, ಚದುರಂಗ ಫಲಕದಲ್ಲಿ ಪ್ರಾಬಲ್ಯ ಸಾಧಿಸಬಹುದು. ರೇಖಾಚಿತ್ರಗಳ ಬಣ್ಣಗಳು ಪ್ರತಿ ಚೌಕಕ್ಕೆ ಬಣ್ಣ ಹಾಕುವ ವಿಧಾನಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ, ಇದರಿಂದಾಗಿ ರಾಣಿಯು ಒಂದೇ ಬಣ್ಣದ ಯಾವುದೇ ಎರಡು ಚೌಕಗಳ ನಡುವೆ ಚಲಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ; ಚದುರಂಗ ಫಲಕಕ್ಕೆ ಕನಿಷ್ಠ n ಬಣ್ಣಗಳು ಬೇಕಾಗುತ್ತವೆ, ಆದರೆ ಫಲಕಕ್ಕೆ 9 ಬಣ್ಣಗಳು ಬೇಕಾಗುತ್ತವೆ. ಗುಣಲಕ್ಷಣಗಳು ಪ್ರತಿ ರಾಣಿಯ ರೇಖಾಚಿತ್ರಕ್ಕೆ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವಿದೆ, ಮತ್ತು ರೇಖಾಚಿತ್ರಗಳನ್ನು ದ್ವಿ-ಸಂಪರ್ಕಿಸಲಾಗಿದೆ (ಯಾವುದೇ ಒಂದು ಶೃಂಗವನ್ನು ತೆಗೆದುಹಾಕಿದರೆ ಅವು ಸಂಪರ್ಕದಲ್ಲಿರುತ್ತವೆ). ದಿ ಮತ್ತು ಕ್ವೀನ್ಸ್ ಗ್ರಾಫ್ಗಳ ವಿಶೇಷ ಪ್ರಕರಣಗಳು ಪೂರ್ಣಗೊಂಡಿವೆ. ಸ್ವತಂತ್ರ ಗ್ರಾಫ್ನ ಒಂದು ಸ್ವತಂತ್ರ ಸೆಟ್ ಚೆಸ್ ಬೋರ್ಡ್ನಲ್ಲಿ ಹಲವಾರು ರಾಣಿಯರ ನಿಯೋಜನೆಗೆ ಅನುರೂಪವಾಗಿದೆ, ಅಂದರೆ ಯಾವುದೇ ಇಬ್ಬರು ರಾಣಿಯರು ಪರಸ್ಪರ ದಾಳಿ ಮಾಡುತ್ತಿಲ್ಲ. ಚೆಸ್ ಬೋರ್ಡ್ನಲ್ಲಿ, ಅತಿದೊಡ್ಡ ಸ್ವತಂತ್ರ ಸೆಟ್ ಗರಿಷ್ಠ n ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಏಕೆಂದರೆ ಯಾವುದೇ ಇಬ್ಬರು ರಾಣಿಯರು ಒಂದೇ ಸಾಲು ಅಥವಾ ಕಾಲಮ್ನಲ್ಲಿರಬಾರದು. ಈ ಮೇಲಿನ ಮಿತಿಯನ್ನು n = 2 ಮತ್ತು n = 3 ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ n ಗಳಿಗೂ ಸಾಧಿಸಬಹುದು. n = 8 ರ ಸಂದರ್ಭದಲ್ಲಿ, ಇದು ಸಾಂಪ್ರದಾಯಿಕ ಎಂಟು ರಾಣಿಯರ ಒಗಟು. ರಾಣಿಯ ರೇಖಾಚಿತ್ರದ ಒಂದು ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ ರಾಣಿಯರ ನಿಯೋಜನೆಗೆ ಅನುರೂಪವಾಗಿದೆ, ಅಂದರೆ ಚದುರಂಗ ಫಲಕದ ಪ್ರತಿಯೊಂದು ಚೌಕವು ರಾಣಿಯಿಂದ ದಾಳಿಗೊಳಗಾಗುತ್ತದೆ ಅಥವಾ ಆಕ್ರಮಿಸಲ್ಪಡುತ್ತದೆ. ಚದುರಂಗ ಫಲಕದಲ್ಲಿ, ಐದು ರಾಣಿಯರು ಪ್ರಾಬಲ್ಯ ಸಾಧಿಸಬಹುದು, ಮತ್ತು ಇದು ಸಾಧ್ಯವಿರುವ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯಾಗಿದೆ (ನಾಲ್ಕು ರಾಣಿಯರು ಕನಿಷ್ಠ ಎರಡು ಚೌಕಗಳನ್ನು ಆಕ್ರಮಣ ಮಾಡದೆ ಬಿಡುತ್ತಾರೆ). ಐದು ರಾಣಿಯರ 4,860 ಅಂತಹ ನಿಯೋಜನೆಗಳಿವೆ, ಇದರಲ್ಲಿ ರಾಣಿಯರು ನಿಯಂತ್ರಿಸುವ ಎಲ್ಲಾ ಆಕ್ರಮಿತ ಚೌಕಗಳೂ ಸೇರಿವೆ, ಅಂದರೆ. ಅವರು ಅನುಕ್ರಮವಾಗಿ ಪರಸ್ಪರ ದಾಳಿ ಮಾಡುತ್ತಾರೆ. ಈ ಉಪಗುಂಪಿನಲ್ಲಿ, ರಾಣಿಗಳು ಮುಖ್ಯ ಕರ್ಣದಲ್ಲಿ ಮಾತ್ರ ಚೌಕಗಳನ್ನು ಆಕ್ರಮಿಸುವ ಸ್ಥಾನಗಳೂ ಇವೆ (ಉದಾಹರಣೆಗೆ. a1 ನಿಂದ h8 ವರೆಗೆ), ಅಥವಾ ಎಲ್ಲವೂ ಉಪ ಕರ್ಣದಲ್ಲಿರುತ್ತವೆ (ಉದಾಹರಣೆಗೆ. a2 ನಿಂದ g8 ವರೆಗೆ). ಲೂಪಿಂಗ್ ಅಲ್ಲದ ಆಯತಾಕಾರದ ಚೆಸ್ ಬೋರ್ಡ್ ಅನ್ನು ಟೋರಸ್ ಅಥವಾ ಸಿಲಿಂಡರ್ನೊಂದಿಗೆ ಬದಲಾಯಿಸುವ ಮೂಲಕ ಗ್ರಾಫ್ ಅನ್ನು ಮಾರ್ಪಡಿಸುವುದರಿಂದ ಕನಿಷ್ಠ ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ ಗಾತ್ರವನ್ನು ನಾಲ್ಕಕ್ಕೆ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ. ರಾಣಿಯ ರೇಖಾಚಿತ್ರವು ಫಲಕದ ಮಧ್ಯಭಾಗದಲ್ಲಿರುವ ಏಕ ಶೃಂಗದ ಪ್ರಾಬಲ್ಯವನ್ನು ಹೊಂದಿದೆ. ರಾಣಿಯ ರೇಖಾಚಿತ್ರದ ಮಧ್ಯದ ಶೃಂಗವು 8 ಶೃಂಗಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲಾ ಶೃಂಗಗಳ ಪಕ್ಕದಲ್ಲಿದೆಃ ಕುದುರೆಯ ರೇಖಾಚಿತ್ರದ ಮಧ್ಯದ ಶೃಂಗದ ಪಕ್ಕದಲ್ಲಿರುವ ಆ ಶೃಂಗಗಳು. ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆಗಳು ರಾಣಿಯ ರೇಖಾಚಿತ್ರದ ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆಯನ್ನು ಡಿ (ಎನ್) ಅನ್ನು ಚಿಕ್ಕ ಪ್ರಾಬಲ್ಯದ ಗುಂಪಿನ ಗಾತ್ರವೆಂದು ಮತ್ತು ಕರ್ಣೀಯ ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆಯನ್ನು ಡಿಡಿ (ಎನ್) ಅನ್ನು ಚಿಕ್ಕ ಪ್ರಾಬಲ್ಯದ ಗುಂಪಿನ ಗಾತ್ರವೆಂದು ವ್ಯಾಖ್ಯಾನಿಸಿ, ಅದು ಉದ್ದನೆಯ ಕರ್ಣೀಯದ ಉಪವಿಭಾಗವಾಗಿದೆ. ಎಲ್ಲ n. ಗಳಿಗೆ ಮಿತಿಯನ್ನು ಸಾಧಿಸಲಾಗುತ್ತದೆ, ಆದರೆ ಅದಕ್ಕೆ ಅಲ್ಲ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆಯು n ನಲ್ಲಿ ರೇಖೀಯವಾಗಿದ್ದು, ಈ ಕೆಳಗಿನವುಗಳಿಂದ ನೀಡಲಾದ ಮಿತಿಗಳೊಂದಿಗೆಃ d (n) ನ ಆರಂಭಿಕ ಮೌಲ್ಯಗಳು 1,1,1,2,3,3,4,5,5. ಪ್ರತಿ ಸಂಖ್ಯೆಯು ಒಂದೇ ಸಮಾನತೆಯನ್ನು ಹೊಂದಿರುವಂತಹ ಉಪಗುಂಪಿನ ಗರಿಷ್ಠ ಗಾತ್ರವು Kn ಆಗಿರಲಿ ಮತ್ತು ಯಾವುದೇ ಮೂರು ಸಂಖ್ಯೆಗಳು ಅಂಕಗಣಿತದ ಪ್ರಗತಿಯನ್ನು ರೂಪಿಸುವುದಿಲ್ಲ (ಸೆಟ್ "ಮಧ್ಯಬಿಂದು-ಮುಕ್ತವಾಗಿದೆ"). ರಾಣಿಯ ರೇಖಾಚಿತ್ರದ ಕರ್ಣೀಯ ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆ. ಸ್ವತಂತ್ರ ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆ ಐ. ಡಿ. (ಎನ್) ಅನ್ನು ರಾಣಿಯ ರೇಖಾಚಿತ್ರದಲ್ಲಿರುವ ಅತ್ಯಂತ ಚಿಕ್ಕ ಸ್ವತಂತ್ರ, ಪ್ರಬಲ ಗುಂಪಿನ ಗಾತ್ರ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಿ. ಎಂಬುದು ಗೊತ್ತಾಗಿದೆ. ರಾಣಿ ರೇಖಾಚಿತ್ರದ ಬಣ್ಣವು ಪ್ರತಿ ಶೃಂಗಕ್ಕೂ ಬಣ್ಣಗಳ ನಿಯೋಜನೆಯಾಗಿದ್ದು, ಯಾವುದೇ ಎರಡು ಪಕ್ಕದ ಶೃಂಗಗಳಿಗೆ ಒಂದೇ ಬಣ್ಣವನ್ನು ನೀಡಲಾಗುವುದಿಲ್ಲ. ಉದಾಹರಣೆಗೆ, ಎ8 ಕೆಂಪು ಬಣ್ಣದ್ದಾಗಿದ್ದರೆ, ಎ-ಕಡತದ ಮೇಲಿನ ಯಾವುದೇ ಚೌಕ, ಎಂಟನೇ ಶ್ರೇಣಿ ಅಥವಾ ಉದ್ದದ ಕರ್ಣೀಯವನ್ನು ಕೆಂಪು ಬಣ್ಣದಿಂದ ಬಣ್ಣಿಸಲಾಗುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ರಾಣಿಯು ಎ8 ನಿಂದ ಈ ಯಾವುದೇ ಚೌಕಗಳಿಗೆ ಚಲಿಸಬಹುದು. ಗ್ರಾಫ್ನ ವರ್ಣತಂತು ಸಂಖ್ಯೆಯು ಅದನ್ನು ಬಣ್ಣ ಮಾಡಲು ಬಳಸಬಹುದಾದ ಬಣ್ಣಗಳ ಅತ್ಯಂತ ಚಿಕ್ಕ ಸಂಖ್ಯೆಯಾಗಿದೆ. ರಾಣಿಯ ರೇಖಾಚಿತ್ರದ ಸಂದರ್ಭದಲ್ಲಿ, ಕನಿಷ್ಠ n ಬಣ್ಣಗಳ ಅಗತ್ಯವಿರುತ್ತದೆ, ಏಕೆಂದರೆ ಶ್ರೇಣಿ ಅಥವಾ ಕಡತದಲ್ಲಿನ ಪ್ರತಿ ಚೌಕಕ್ಕೂ ಬೇರೆ ಬಣ್ಣದ ಅಗತ್ಯವಿರುತ್ತದೆ (ಅಂದರೆ. ಸಾಲುಗಳು ಮತ್ತು ಕಾಲಮ್ಗಳು ಗುಂಪುಗಳಾಗಿವೆ). ವರ್ಣದ ಸಂಖ್ಯೆಯು ನಿಖರವಾಗಿ n ಆಗಿದ್ದರೆ (ಅಂದರೆ. n ಎಂದರೆ 6ರ ಗುಣಾಕಾರಕ್ಕಿಂತ ಒಂದು ಹೆಚ್ಚು ಅಥವಾ ಒಂದು ಕಡಿಮೆ). ರಾಣಿಯ ರೇಖಾಚಿತ್ರದ ವರ್ಣಸಂಖ್ಯೆಯು 9 ಆಗಿದೆ. ಸೆಟ್ನಿಂದ ಯಾವುದೇ ಶೃಂಗವನ್ನು ತೆಗೆದುಹಾಕುವುದರಿಂದ ಸೆಟ್ನ ನೆರೆಹೊರೆಯನ್ನು ಬದಲಾಯಿಸಿದರೆ ಶೃಂಗಗಳ ಒಂದು ಸೆಟ್ ಇರ್ರೆಡಂಡೆಂಟ್ ಆಗಿರುತ್ತದೆ. ಪ್ರತಿ ಶೃಂಗಕ್ಕೂ, ಗುಂಪಿನಲ್ಲಿರುವ ಯಾವುದೇ ಶೃಂಗದ ಪಕ್ಕದಲ್ಲಿರದ ಪಕ್ಕದ ಶೃಂಗವಿದೆ. ಇದು ಕನಿಷ್ಠ ಒಂದು ಚೌಕವನ್ನು ಅನನ್ಯವಾಗಿ ನಿಯಂತ್ರಿಸುವ ರಾಣಿಯರ ಗುಂಪಿಗೆ ಅನುರೂಪವಾಗಿದೆ. ರಾಣಿಯ ರೇಖಾಚಿತ್ರದ ಮೇಲೆ ಇರ್ರೆಡಂಡೆಂಟ್ ಸೆಟ್ನ ಗರಿಷ್ಠ ಗಾತ್ರದ ಐಆರ್ (ಎನ್) ಅನ್ನು ನಿರೂಪಿಸುವುದು ಕಷ್ಟ; ತಿಳಿದಿರುವ ಮೌಲ್ಯಗಳು ಪರ್ಸ್ಯೂಟ್-ತಪ್ಪಿಸಿಕೊಳ್ಳುವ ಆಟವನ್ನು ಒಳಗೊಂಡಿವೆ ಈ ಕೆಳಗಿನ ನಿಯಮಗಳ ಪ್ರಕಾರ ಆಡಿದ ರಾಣಿಯ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಅನ್ವೇಷಣೆ-ತಪ್ಪಿಸಿಕೊಳ್ಳುವ ಆಟವನ್ನು ಪರಿಗಣಿಸಿಃ ಬಿಳಿ ರಾಣಿ ಒಂದು ಮೂಲೆಯಲ್ಲಿ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಮತ್ತು ಕಪ್ಪು ರಾಣಿ ಇನ್ನೊಂದು ಮೂಲೆಯಲ್ಲಿ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ. ಆಟಗಾರರು ಪರ್ಯಾಯ ಚಲನೆಗಳನ್ನು ಮಾಡುತ್ತಾರೆ, ಇದು ರಾಣಿಯನ್ನು ಪಕ್ಕದ ಶೃಂಗಕ್ಕೆ ಚಲಿಸುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಅದನ್ನು (ಅಡ್ಡಲಾಗಿ, ಲಂಬವಾಗಿ ಅಥವಾ ಕರ್ಣೀಯವಾಗಿ) ಹಾದುಹೋಗದೆ ಅಥವಾ ವಿರುದ್ಧ ರಾಣಿಗೆ ಹೊಂದಿಕೊಂಡಿರುವ ಶೃಂಗದ ಮೇಲೆ ಇಳಿಯದೆ ತಲುಪಬಹುದು. ಈ ಆಟವನ್ನು ಜೋಡಿಯ ತಂತ್ರದೊಂದಿಗೆ ಬಿಳಿಯರು ಗೆಲ್ಲಬಹುದು. ಕಿಂಗ್ 'ಸ್ ಗ್ರಾಫ್ ನೈಟ್' ಸ್ ಗ್ರಾಫ್ ರೂಕ್ 'ಸ್ ಗ್ರಾಫ್ ಬಿಷಪ್' ಸ್ ಗ್ರಾಫ್ ಉಲ್ಲೇಖಗಳು ಗಣಿತೀಯ ಚೆಸ್ ಸಮಸ್ಯೆಗಳು ಗ್ರಾಫ್ಗಳ ನಿಯತಾಂಕ ಕುಟುಂಬಗಳನ್ನೂ ಸಹ ನೋಡಿ.