Random regular graph
ಯಾದೃಚ್ಛಿಕ ಆರ್-ನಿಯಮಿತ ರೇಖಾಚಿತ್ರವು ಆಯ್ಕೆ ಮಾಡಲಾದ ರೇಖಾಚಿತ್ರವಾಗಿದೆ, ಇದು ಶೃಂಗಗಳ ಮೇಲಿನ ಎಲ್ಲಾ ಆರ್-ನಿಯಮಿತ ರೇಖಾಚಿತ್ರಗಳ ಸಂಭವನೀಯ ಸ್ಥಳವನ್ನು ಸೂಚಿಸುತ್ತದೆ, ಎಲ್ಲಿ ಮತ್ತು ಸಮವಾಗಿದೆ. ಆದ್ದರಿಂದ ಇದು ಒಂದು ನಿರ್ದಿಷ್ಟ ರೀತಿಯ ಯಾದೃಚ್ಛಿಕ ಗ್ರಾಫ್ ಆಗಿದೆ, ಆದರೆ ನಿಯಮಿತತೆಯ ನಿರ್ಬಂಧವು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳುವ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಗಮನಾರ್ಹವಾಗಿ ಬದಲಾಯಿಸುತ್ತದೆ, ಏಕೆಂದರೆ ಹೆಚ್ಚಿನ ಗ್ರಾಫ್ಗಳು ನಿಯಮಿತವಾಗಿಲ್ಲ. ಯಾದೃಚ್ಛಿಕ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳ ಗುಣಲಕ್ಷಣಗಳು ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಯಾದೃಚ್ಛಿಕ ಗ್ರಾಫ್ಗಳಂತೆ, ಯಾದೃಚ್ಛಿಕ-ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳ ಕೆಲವು ಗುಣಲಕ್ಷಣಗಳು ಬಹುತೇಕ ಖಚಿತವಾಗಿ ಲಕ್ಷಣರಹಿತವಾಗಿರುತ್ತವೆ ಎಂದು ಸಾಬೀತುಪಡಿಸಲು ಸಾಧ್ಯವಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ದೊಡ್ಡ ಗಾತ್ರದ ಯಾದೃಚ್ಛಿಕ ಆರ್-ನಿಯಮಿತ ಗ್ರಾಫ್ ಲಕ್ಷಣರಹಿತವಾಗಿ ಬಹುತೇಕ ಖಚಿತವಾಗಿ ಆರ್-ಸಂಪರ್ಕ ಹೊಂದಿದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಸಂಪರ್ಕವನ್ನು ಹೊಂದಿರುವ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲದಿದ್ದರೂ, ಅಂತಹ ಗ್ರಾಫ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಸಂಭವನೀಯತೆಯು ಹೆಚ್ಚಾದಂತೆ 0 ಆಗಿರುತ್ತದೆ. ಧನಾತ್ಮಕ ಸ್ಥಿರಾಂಕವಾಗಿದ್ದರೆ ಮತ್ತು ಕನಿಷ್ಠ ಪೂರ್ಣಾಂಕವು ತೃಪ್ತಿಕರವಾಗಿದ್ದರೆ, ಲಕ್ಷಣರಹಿತವಾಗಿ ಬಹುತೇಕ ಖಚಿತವಾಗಿ, ಯಾದೃಚ್ಛಿಕ ಆರ್-ನಿಯಮಿತ ರೇಖಾಚಿತ್ರವು ಗರಿಷ್ಠ ಡಿ ವ್ಯಾಸವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಆರ್-ನಿಯಮಿತ ರೇಖಾಚಿತ್ರಗಳ ವ್ಯಾಸದ ಮೇಲೆ (ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾದ) ಕಡಿಮೆ ಬಂಧವೂ ಇರುತ್ತದೆ, ಆದ್ದರಿಂದ ಬಹುತೇಕ ಎಲ್ಲಾ ಆರ್-ನಿಯಮಿತ ರೇಖಾಚಿತ್ರಗಳು (ಒಂದೇ ಗಾತ್ರದ) ಬಹುತೇಕ ಒಂದೇ ವ್ಯಾಸವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಸಣ್ಣ ಚಕ್ರಗಳ ಸಂಖ್ಯೆಯ ವಿತರಣೆಯೂ ಸಹ ತಿಳಿದಿದೆಃ ಸ್ಥಿರವಾದದ್ದಕ್ಕಾಗಿ, ವರೆಗೆ ಇರುವ ಉದ್ದದ ಚಕ್ರಗಳ ಸಂಖ್ಯೆಯಾಗಿರಲಿ. ನಂತರ ಅವು ಯಾದೃಚ್ಛಿಕ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳಿಗೆ ಕ್ರಮಾವಳಿಗಳೊಂದಿಗೆ ಲಕ್ಷಣರಹಿತವಾಗಿ ಸ್ವತಂತ್ರವಾದ ಪಾಯ್ಸನ್ ಯಾದೃಚ್ಛಿಕ ಅಸ್ಥಿರಗಳಾಗಿವೆ, ಹೆಚ್ಚಿನ ಗ್ರಾಫ್ಗಳು ನಿಯಮಿತವಾಗಿರದ ಕಾರಣ ಆರ್-ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳ ಯಾದೃಚ್ಛಿಕ ಆಯ್ಕೆಯನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮತ್ತು ಪಕ್ಷಪಾತವಿಲ್ಲದ ರೀತಿಯಲ್ಲಿ ಕಾರ್ಯಗತಗೊಳಿಸುವುದು ಕ್ಷುಲ್ಲಕವಲ್ಲ. ಜೋಡಿಸುವ ಮಾದರಿಯು (ಸಂರಚನೆಯ ಮಾದರಿಯೂ ಸಹ) ಎನ್ಆರ್ ಅಂಕಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಒಂದು ವಿಧಾನವಾಗಿದೆ, ಮತ್ತು ಅವುಗಳನ್ನು ಪ್ರತಿಯೊಂದರಲ್ಲೂ ಆರ್ ಅಂಕಗಳೊಂದಿಗೆ ಎನ್ ಬಕೆಟ್ಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ. ಎನ್ಆರ್ ಬಿಂದುಗಳ ಯಾದೃಚ್ಛಿಕ ಹೊಂದಾಣಿಕೆಯನ್ನು ತೆಗೆದುಕೊಂಡು, ನಂತರ ಪ್ರತಿ ಬಕೆಟ್ನಲ್ಲಿರುವ ಆರ್ ಬಿಂದುಗಳನ್ನು ಒಂದೇ ಶೃಂಗವಾಗಿ ಸಂಕುಚಿತಗೊಳಿಸಿ, ಆರ್-ನಿಯಮಿತ ಗ್ರಾಫ್ ಅಥವಾ ಮಲ್ಟಿಗ್ರ್ಯಾಫ್ ಅನ್ನು ನೀಡುತ್ತದೆ. ಈ ವಸ್ತುವು ಅನೇಕ ಅಂಚುಗಳು ಅಥವಾ ಲೂಪ್ಗಳನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ (ಅಂದರೆ. ಇದು ಗ್ರಾಫ್ ಆಗಿದೆ), ನಂತರ ಇದು ಅಗತ್ಯವಾದ ಫಲಿತಾಂಶವಾಗಿದೆ. ಇಲ್ಲದಿದ್ದರೆ, ಮರುಪ್ರಾರಂಭದ ಅಗತ್ಯವಿದೆ. ಈ ವಿಧಾನದ ಪರಿಷ್ಕರಣೆಯನ್ನು ಬ್ರೆಂಡನ್ ಮೆಕ್ಕೇ ಮತ್ತು ನಿಕೋಲಸ್ ವೋರ್ಮಾಲ್ಡ್ ಅಭಿವೃದ್ಧಿಪಡಿಸಿದರು. ಉಲ್ಲೇಖಗಳು ಯಾದೃಚ್ಛಿಕ ರೇಖಾಚಿತ್ರಗಳು ನಿಯಮಿತ ರೇಖಾಚಿತ್ರಗಳು