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