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