Graph pebbling
ಗ್ರಾಫ್ ಬೆಣಚುಕಲ್ಲು ಎನ್ನುವುದು ಅದರ ಪ್ರತಿಯೊಂದು ಶೃಂಗಗಳ ಮೇಲೆ ಶೂನ್ಯ ಅಥವಾ ಹೆಚ್ಚಿನ ಬೆಣಚುಕಲ್ಲುಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ನಲ್ಲಿ ಆಡಲಾಗುವ ಗಣಿತದ ಆಟವಾಗಿದೆ. 'ಗೇಮ್ ಪ್ಲೇ' ಪೆಬ್ಲಿಂಗ್ ಚಲನೆಗಳ ಸರಣಿಯಿಂದ ಕೂಡಿದೆ. ಒಂದು ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಬೆಣಚುಕಲ್ಲುಗಳ ಚಲನೆಯು ಕನಿಷ್ಠ ಎರಡು ಬೆಣಚುಕಲ್ಲುಗಳನ್ನು ಹೊಂದಿರುವ ಶೃಂಗವನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದು, ಅದರಿಂದ ಎರಡು ಬೆಣಚುಕಲ್ಲುಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದು ಮತ್ತು ಒಂದನ್ನು ಪಕ್ಕದ ಶೃಂಗಕ್ಕೆ ಸೇರಿಸುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ (ಎರಡನೇ ತೆಗೆದುಹಾಕಲಾದ ಬೆಣಚುಕಲ್ಲುಗಳನ್ನು ಆಟದಿಂದ ತಿರಸ್ಕರಿಸಲಾಗುತ್ತದೆ). ಗ್ರಾಫ್ G ಯ ಬೆಣಚುಕಲ್ಲು ಸಂಖ್ಯೆಯಾದ π (G), ಈ ಕೆಳಗಿನ ಷರತ್ತನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಅತ್ಯಂತ ಕಡಿಮೆ ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆ n ಆಗಿದೆಃ ಗ್ರಾಫ್ನಲ್ಲಿನ ಯಾವುದೇ ಗುರಿ ಅಥವಾ 'ಮೂಲ' ಶೃಂಗವನ್ನು ಮತ್ತು ಗ್ರಾಫ್ನಲ್ಲಿನ n ಬೆಣಚುಕಲ್ಲುಗಳ ಯಾವುದೇ ಆರಂಭಿಕ ಸಂರಚನೆಯನ್ನು ನೀಡಿದರೆ, ಬೆಣಚುಕಲ್ಲು ಚಲನೆಗಳ ಸರಣಿಯ ನಂತರ, ಗೊತ್ತುಪಡಿಸಿದ ಮೂಲ ಶೃಂಗವು ಒಂದು ಅಥವಾ ಹೆಚ್ಚಿನ ಬೆಣಚುಕಲ್ಲುಗಳನ್ನು ಹೊಂದಿರುವ ಹೊಸ ಸಂರಚನೆಯನ್ನು ತಲುಪಲು ಸಾಧ್ಯವಿದೆ. ಉದಾಹರಣೆಗೆ, 2 ಶೃಂಗಗಳು ಮತ್ತು ಅವುಗಳನ್ನು ಸಂಪರ್ಕಿಸುವ 1 ಅಂಚನ್ನು ಹೊಂದಿರುವ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಬೆಣಚುಕಲ್ಲುಗಳ ಸಂಖ್ಯೆ 2 ಆಗಿದೆ. ಗ್ರಾಫ್ನ ಶೃಂಗಗಳ ಮೇಲೆ ಎರಡು ಉಂಡೆಗಳನ್ನು ಹೇಗೆ ಇರಿಸಲಾಗಿದ್ದರೂ, ಗ್ರಾಫ್ನಲ್ಲಿರುವ ಯಾವುದೇ ಶೃಂಗಕ್ಕೆ ಒಂದು ಉಂಡೆಯನ್ನು ಸರಿಸಲು ಯಾವಾಗಲೂ ಸಾಧ್ಯವಿದೆ. ಗ್ರಾಫ್ ಪೆಬ್ಲಿಂಗ್ನ ಕೇಂದ್ರ ಪ್ರಶ್ನೆಗಳಲ್ಲಿ ಒಂದು ನಿರ್ದಿಷ್ಟ ಗ್ರಾಫ್ ಜಿಗೆ π (ಜಿ) ಮೌಲ್ಯವಾಗಿದೆ. ಪೆಬ್ಲಿಂಗ್ನಲ್ಲಿನ ಇತರ ವಿಷಯಗಳಲ್ಲಿ ಕವರ್ ಪೆಬ್ಲಿಂಗ್, ಆಪ್ಟಿಮಲ್ ಪೆಬ್ಲಿಂಗ್, ಡೊಮಿನೇಷನ್ ಕವರ್ ಪೆಬ್ಲಿಂಗ್, ಬೌಂಡರಿಗಳು ಮತ್ತು ಪೆಬ್ಲಿಂಗ್ ಸಂಖ್ಯೆಗಳಿಗೆ ಮಿತಿಗಳು ಮತ್ತು ಆಳವಾದ ಗ್ರಾಫ್ಗಳು ಸೇರಿವೆ. π (G)-ಗ್ರಾಫ್ನ ಬೆಣಚುಕಲ್ಲುಗಳ ಸಂಖ್ಯೆ ಬೆಣಚುಕಲ್ಲುಗಳ ಆಟವನ್ನು ಮೊದಲು ಲಾಗರಿಯಾಸ್ ಮತ್ತು ಸಾಕ್ಸ್ ಅವರು ಸಂಖ್ಯೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಒಂದು ನಿರ್ದಿಷ್ಟ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಸಾಧನವಾಗಿ ಸೂಚಿಸಿದರು. 1989ರಲ್ಲಿ ಎಫ್. ಆರ್. ಕೆ. ಚುಂಗ್ ಈ ಪರಿಕಲ್ಪನೆಯನ್ನು ಸಾಹಿತ್ಯದಲ್ಲಿ ಪರಿಚಯಿಸಿದರು ಮತ್ತು ಪೆಬ್ಲಿಂಗ್ ಸಂಖ್ಯೆ, π (G) ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿದರು. n ಶೃಂಗಗಳ ಮೇಲೆ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ಗೆ ಬೆಣಚುಕಲ್ಲು ಸಂಖ್ಯೆಯನ್ನು n ಎಂದು ಸುಲಭವಾಗಿ ಪರಿಶೀಲಿಸಲಾಗುತ್ತದೆಃ ನಾವು ಗ್ರಾಫ್ ಅನ್ನು ಹಾಕಲು (n−1) ಬೆಣಚುಕಲ್ಲುಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ನಾವು ಗುರಿಯನ್ನು ಹೊರತುಪಡಿಸಿ ಪ್ರತಿ ಶೃಂಗದ ಮೇಲೆ ಒಂದು ಬೆಣಚುಕಲ್ಲು ಹಾಕಬಹುದು. ಯಾವುದೇ ಶೃಂಗವು ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ಉಂಡೆಗಳನ್ನು ಹೊಂದಿಲ್ಲದ ಕಾರಣ, ಯಾವುದೇ ಚಲನೆಗಳು ಸಾಧ್ಯವಿಲ್ಲ, ಆದ್ದರಿಂದ ಗುರಿಯ ಮೇಲೆ ಉಂಡೆಯನ್ನು ಇಡುವುದು ಅಸಾಧ್ಯ. ಹೀಗಾಗಿ, ಬೆಣಚುಕಲ್ಲುಗಳ ಸಂಖ್ಯೆಯು n-1ಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿರಬೇಕು. n ಉಂಡೆಗಳನ್ನು ನೀಡಿದರೆ, ಎರಡು ಸಂಭವನೀಯ ಪ್ರಕರಣಗಳಿವೆ. ಪ್ರತಿ ಶೃಂಗವು ಒಂದು ಕಲ್ಲನ್ನು ಹೊಂದಿದ್ದರೆ, ಯಾವುದೇ ಚಲನೆಗಳ ಅಗತ್ಯವಿಲ್ಲ. ಯಾವುದೇ ಶೃಂಗವು ಬರಿದಾಗಿದ್ದರೆ, ಕನಿಷ್ಠ ಒಂದು ಇತರ ಶೃಂಗವು ಅದರ ಮೇಲೆ ಎರಡು ಉಂಡೆಗಳನ್ನು ಹೊಂದಿರಬೇಕು, ಮತ್ತು ಒಂದು ಬೆಣಚುಕಲ್ಲು ಚಲನೆ ಸಂಪೂರ್ಣ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಯಾವುದೇ ಗುರಿ ಶೃಂಗಕ್ಕೆ ಒಂದು ಉಂಡೆಯನ್ನು ಸೇರಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳಿಗೆ π (G) ಪೆಬ್ಲಿಂಗ್ ಸಂಖ್ಯೆಯು ಈ ಕೆಳಗಿನ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳಿಗೆ ಹೆಸರುವಾಸಿಯಾಗಿದೆಃ, ಇಲ್ಲಿ n ಶೃಂಗಗಳ ಮೇಲೆ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ ಇರುತ್ತದೆ. , n ಶೃಂಗಗಳ ಮೇಲೆ ಪಥದ ರೇಖಾಚಿತ್ರ ಎಲ್ಲಿದೆ. , n ಶೃಂಗಗಳ ಮೇಲೆ ಚಕ್ರದ ರೇಖಾಚಿತ್ರ ಎಲ್ಲಿದೆ. ಗ್ರಾಫ್ಗಳ ಕಾರ್ಟೇಶಿಯನ್ ಉತ್ಪನ್ನದ ಬೆಣಚುಕಲ್ಲು ಸಂಖ್ಯೆಯು ಉತ್ಪನ್ನದಲ್ಲಿನ ಅಂಶಗಳ ಬೆಣಚುಕಲ್ಲು ಸಂಖ್ಯೆಗಳ ಉತ್ಪನ್ನಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ ಎಂಬ ಊಹೆಯೊಂದಿಗೆ ಗ್ರಹಾಂನ ಬೆಣಚುಕಲ್ಲು ಊಹೆಯು ರೊನಾಲ್ಡ್ ಗ್ರಹಾಂಗೆ ಮನ್ನಣೆ ನೀಡಿತು. ಇದನ್ನು ಗ್ರಹಾಂ ಅವರ ಬೆಣಚುಕಲ್ಲು ಊಹೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ವಿಶೇಷ ಪ್ರಕರಣಗಳು ತಿಳಿದಿದ್ದರೂ, ಇದು ಬಗೆಹರಿಯದೆ ಉಳಿದಿದೆ. γ (G)-ಗ್ರಾಫ್ ಕ್ರಲ್ ಮತ್ತು ಇತರರ ಕವರ್ ಪೆಬ್ಲಿಂಗ್ ಸಂಖ್ಯೆ. ಕವರ್ ಪೆಬ್ಲಿಂಗ್ ಪರಿಕಲ್ಪನೆಯನ್ನು ಪರಿಚಯಿಸಲಾಯಿತು. γ (G), ಗ್ರಾಫ್ನ ಕವರ್ ಬೆಣಚುಕಲ್ಲು ಸಂಖ್ಯೆಯು ಅಗತ್ಯವಿರುವ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಬೆಣಚುಕಲ್ಲುಗಳಾಗಿದ್ದು, ಇದರಿಂದಾಗಿ ಬೆಣಚುಕಲ್ಲುಗಳ ಯಾವುದೇ ಆರಂಭಿಕ ಜೋಡಣೆಯಿಂದ, ಬೆಣಚುಕಲ್ಲುಗಳ ಸರಣಿಯ ಚಲನೆಗಳ ನಂತರ, ಗ್ರಾಫ್ ಅನ್ನು ಮುಚ್ಚಲಾಗುತ್ತದೆಃ ಪ್ರತಿ ಶೃಂಗದ ಮೇಲೆ ಕನಿಷ್ಠ ಒಂದು ಬೆಣಚುಕಲ್ಲು ಇರುತ್ತದೆ. ಸ್ಟ್ಯಾಕಿಂಗ್ ಪ್ರಮೇಯ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಒಂದು ಫಲಿತಾಂಶವು ಯಾವುದೇ ಗ್ರಾಫ್ಗೆ ಕವರ್ ಪೆಬ್ಲಿಂಗ್ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ಸ್ಟ್ಯಾಕಿಂಗ್ ಪ್ರಮೇಯವು ಸ್ಟ್ಯಾಕಿಂಗ್ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಎಲ್ಲಾ ಉಂಡೆಗಳನ್ನು ಒಂದೇ ಶೃಂಗದ ಮೇಲೆ ಇರಿಸಿದಾಗ ಹೆಚ್ಚಿನ ಉಂಡೆಗಳನ್ನು ಪರಿಹರಿಸುವ ಅಗತ್ಯವಿರುವ ಉಂಡೆಗಳ ಆರಂಭಿಕ ಸಂರಚನೆಯು ಸಂಭವಿಸುತ್ತದೆ. ಈ ಅವಲೋಕನದ ಆಧಾರದ ಮೇಲೆ, Gಯಲ್ಲಿನ ಪ್ರತಿ ಶೃಂಗ v ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿ, ಅಲ್ಲಿ d (u, v) ಯು ಯು ನಿಂದ ವಿ ವರೆಗಿನ ದೂರವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳಿಗೆ γ (G) ಕವರ್ ಪೆಬ್ಲಿಂಗ್ ಸಂಖ್ಯೆಯು ಈ ಕೆಳಗಿನ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳಿಗೆ ಹೆಸರುವಾಸಿಯಾಗಿದೆಃ, ಇಲ್ಲಿ n ಶೃಂಗಗಳ ಮೇಲೆ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ ಇದೆ. , n ಶೃಂಗಗಳ ಮೇಲೆ ಒಂದು ಮಾರ್ಗ ಎಲ್ಲಿದೆ. , n ಶೃಂಗಗಳ ಮೇಲೆ ಚಕ್ರದ ರೇಖಾಚಿತ್ರ ಎಲ್ಲಿದೆ. ಪೆಬಲ್ ಗೇಮ್ ಪ್ರೂಫ್ ಆಫ್ ಸ್ಪೇಸ್ ರೆಫೆರೆನ್ಸಸ್ ಅನ್ನು ಸಹ ನೋಡಿ