Ear decomposition
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ G ಯ ಕಿವಿಯು P ಮಾರ್ಗವಾಗಿದ್ದು, ಅಲ್ಲಿ ಮಾರ್ಗದ ಎರಡು ಅಂತಿಮ ಬಿಂದುಗಳು ಹೊಂದಿಕೆಯಾಗಬಹುದು, ಆದರೆ ಅಲ್ಲಿ ಅಂಚುಗಳು ಅಥವಾ ಶೃಂಗಗಳ ಪುನರಾವರ್ತನೆಯನ್ನು ಅನುಮತಿಸಲಾಗುವುದಿಲ್ಲ, ಆದ್ದರಿಂದ P ಯ ಪ್ರತಿಯೊಂದು ಆಂತರಿಕ ಶೃಂಗವು G ಯಲ್ಲಿ ಎರಡು ಡಿಗ್ರಿಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಹೆಚ್ಚುವರಿಯಾಗಿ, ಹೆಚ್ಚಿನ ಸಂದರ್ಭಗಳಲ್ಲಿ ಅನುಕ್ರಮದಲ್ಲಿ ಮೊದಲ ಕಿವಿ ಒಂದು ಚಕ್ರವಾಗಿರಬೇಕು. ತೆರೆದ ಕಿವಿ ವಿಭಜನೆ ಅಥವಾ ಸರಿಯಾದ ಕಿವಿ ವಿಭಜನೆಯು ಕಿವಿ ವಿಭಜನೆಯಾಗಿದ್ದು, ಇದರಲ್ಲಿ ಮೊದಲನೆಯದರ ನಂತರ ಪ್ರತಿ ಕಿವಿಯ ಎರಡು ಅಂತಿಮ ಬಿಂದುಗಳು ಪರಸ್ಪರ ಭಿನ್ನವಾಗಿರುತ್ತವೆ. ಹಲವಾರು ಪ್ರಮುಖ ಗ್ರಾಫ್ ವರ್ಗಗಳನ್ನು ನಿರೂಪಿಸಲು ಮತ್ತು ದಕ್ಷ ಗ್ರಾಫ್ ಕ್ರಮಾವಳಿಗಳ ಭಾಗವಾಗಿ ಕಿವಿಯ ವಿಭಜನೆಗಳನ್ನು ಬಳಸಬಹುದು. ಅವುಗಳನ್ನು ಗ್ರಾಫ್ಗಳಿಂದ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳವರೆಗೆ ಸಾಮಾನ್ಯೀಕರಿಸಬಹುದು. ಗ್ರಾಫ್ ವರ್ಗಗಳನ್ನು ನಿರೂಪಿಸುವುದು ಗ್ರಾಫ್ಗಳ ಹಲವಾರು ಪ್ರಮುಖ ವರ್ಗಗಳನ್ನು ಕೆಲವು ರೀತಿಯ ಕಿವಿ ವಿಭಜನೆಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳೆಂದು ನಿರೂಪಿಸಬಹುದು. ಗ್ರಾಫ್ ಸಂಪರ್ಕವು ಯಾವುದೇ (k−1) ಶೃಂಗಗಳ ತೆಗೆದುಹಾಕುವಿಕೆಯು ಸಂಪರ್ಕಿತ ಉಪಗ್ರ್ಯಾಫ್ ಅನ್ನು ಬಿಟ್ಟುಹೋದರೆ ಗ್ರಾಫ್ ಅನ್ನು k-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಯಾವುದೇ (k−1) ಅಂಚುಗಳ ತೆಗೆದುಹಾಕುವಿಕೆಯು ಸಂಪರ್ಕಿತ ಉಪಗ್ರ್ಯಾಫ್ ಅನ್ನು ಬಿಟ್ಟುಹೋದರೆ k-ಅಂಚನ್ನು ಸಂಪರ್ಕಿಸಲಾಗುತ್ತದೆ. ಈ ಕೆಳಗಿನ ಫಲಿತಾಂಶವು ಈ ಕೆಳಗಿನ ಕಾರಣದಿಂದಾಗಿರುತ್ತದೆಃ ತೆರೆದ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಗ್ರಾಫ್ 2-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತವಾಗಿರುತ್ತದೆ. ಈ ಕೆಳಗಿನ ಫಲಿತಾಂಶವು ಇದಕ್ಕೆ ಕಾರಣವಾಗಿದೆಃ ಒಂದು ಗ್ರಾಫ್ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಅದು 2-ಅಂಚಿನ ಸಂಪರ್ಕವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಎರಡೂ ಸಂದರ್ಭಗಳಲ್ಲಿ ಕಿವಿಗಳ ಸಂಖ್ಯೆಯು ನೀಡಲಾದ ಗ್ರಾಫ್ನ ಸರ್ಕ್ಯೂಟ್ ಶ್ರೇಣಿಗೆ ಸಮನಾಗಿರುತ್ತದೆ. ರಾಬಿನ್ಸ್ ಪ್ರಮೇಯವನ್ನು ಸಾಬೀತುಪಡಿಸುವ ಸಾಧನವಾಗಿ 2-ಅಂಚಿನ-ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ಗಳ ಕಿವಿ ವಿಭಜನೆಯನ್ನು ರಾಬಿನ್ಸ್ ಪರಿಚಯಿಸಿದರು, ಇವು ನಿಖರವಾಗಿ ಬಲವಾಗಿ ಸಂಪರ್ಕಿತವಾದ ದೃಷ್ಟಿಕೋನವನ್ನು ನೀಡಬಹುದಾದ ಗ್ರಾಫ್ಗಳಾಗಿವೆ. ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯ ಮೇಲೆ ವಿಟ್ನಿ ಮತ್ತು ರಾಬಿನ್ಸ್ ಅವರ ಪ್ರವರ್ತಕ ಕಾರ್ಯದಿಂದಾಗಿ, ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯನ್ನು ಕೆಲವೊಮ್ಮೆ ವಿಟ್ನಿ-ರಾಬಿನ್ಸ್ ಸಂಶ್ಲೇಷಣೆ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ. ಪ್ರತ್ಯೇಕಿಸದ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯು ತೆರೆದ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯಾಗಿದೆ, ಅಂದರೆ, ಕೇವಲ ಒಂದು ವಿನಾಯಿತಿಯೊಂದಿಗೆ ಪ್ರತಿ ಶೃಂಗದ v ಗೆ, ಕೊಳೆಯುವಿಕೆಯಲ್ಲಿ ಮೊದಲ ಬಾರಿಗೆ ಕಾಣಿಸಿಕೊಳ್ಳುವ v ನೆರೆಯವರನ್ನು ಹೊಂದಿದೆ, ಇದು ಮೊದಲ ನೋಟಕ್ಕಿಂತ ನಂತರದ ಕಿವಿಯಲ್ಲಿದೆ. ವಿಟ್ನಿಯ ಫಲಿತಾಂಶವನ್ನು ಸಾಮಾನ್ಯೀಕರಿಸಲು ಈ ರೀತಿಯ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯನ್ನು ಬಳಸಬಹುದುಃ G ಪ್ರತ್ಯೇಕಿಸದ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯನ್ನು ಹೊಂದಿದ್ದರೆ ಮತ್ತು ಮಾತ್ರ 3-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕವನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್. ಅಂತಹ ವಿಭಜನೆಯು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ, ಅದನ್ನು ಜಿ ಯ ನಿರ್ದಿಷ್ಟ ಅಂಚಿನ ಯುವಿಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಯು ಮೊದಲ ಕಿವಿಯಲ್ಲಿರುವ ರೀತಿಯಲ್ಲಿ ಆಯ್ಕೆ ಮಾಡಬಹುದು, ವಿ ಎಂಬುದು ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ಅಂಚನ್ನು ಹೊಂದಿರುವ ಕೊನೆಯ ಕಿವಿಯ ಹೊಸ ಶೃಂಗವಾಗಿದೆ ಮತ್ತು ಯುವಿ ಏಕ-ಅಂಚಿನ ಕಿವಿಯಾಗಿದೆ. ಈ ಫಲಿತಾಂಶವನ್ನು ಮೊದಲು ಸ್ಪಷ್ಟವಾಗಿ ಹೇಳಲಾಗಿದೆ, ಆದರೆ ವಿವರಿಸಿದಂತೆ, ಇದು 1971 ರ ಪಿಎಚ್ಡಿ ಫಲಿತಾಂಶಕ್ಕೆ ಸಮಾನವಾಗಿದೆ. ಲೀ ಮೊಂಡ್ಷೀನ್ ಅವರ ಪ್ರಬಂಧ. ಕ್ಯಾನೊನಿಕಲ್ ಆರ್ಡರ್ಗಳು ಎಂದು ಕರೆಯಲ್ಪಡುವ ಗರಿಷ್ಠ ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳ ಬೇರ್ಪಡಿಸದ ಕಿವಿ ವಿಭಜನೆಗಳಿಗೆ ನಿಕಟವಾಗಿ ಸಂಬಂಧಿಸಿದ ರಚನೆಗಳು ಸಹ ಗ್ರಾಫ್ ಡ್ರಾಯಿಂಗ್ನಲ್ಲಿ ಪ್ರಮಾಣಿತ ಸಾಧನವಾಗಿದೆ. ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳ ಬಲವಾದ ಸಂಪರ್ಕ ಮೇಲಿನ ವ್ಯಾಖ್ಯಾನಗಳನ್ನು ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳಿಗೂ ಅನ್ವಯಿಸಬಹುದು. ಒಂದು ಕಿವಿ ನಂತರ ಎಲ್ಲಾ ಆಂತರಿಕ ಶೃಂಗಗಳು 1 ಕ್ಕೆ ಸಮಾನವಾದ ಅಸಮಾನತೆ ಮತ್ತು ಹೊರಭಾಗವನ್ನು ಹೊಂದಿರುವ ನಿರ್ದೇಶಿತ ಮಾರ್ಗವಾಗಿರುತ್ತದೆ. ಪ್ರತಿ ಶೃಂಗದಿಂದ ಪ್ರತಿಯೊಂದು ಶೃಂಗಕ್ಕೆ ನಿರ್ದೇಶಿತ ಮಾರ್ಗವನ್ನು ಹೊಂದಿದ್ದರೆ ನಿರ್ದೇಶಿತ ರೇಖಾಚಿತ್ರವು ಬಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದೆ. ನಂತರ ನಾವು ಈ ಕೆಳಗಿನ ಪ್ರಮೇಯವನ್ನು ಹೊಂದಿದ್ದೇವೆಃ ನಿರ್ದೇಶನದ ರೇಖಾಚಿತ್ರವು ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಬಲವಾಗಿ ಸಂಪರ್ಕಗೊಳ್ಳುತ್ತದೆ. ಅಂಶ-ನಿರ್ಣಾಯಕ ರೇಖಾಚಿತ್ರಗಳು ಅದರ ಪ್ರತಿಯೊಂದು ಕಿವಿಗಳು ಬೆಸ ಸಂಖ್ಯೆಯ ಅಂಚುಗಳನ್ನು ಬಳಸಿದರೆ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯು ವಿಚಿತ್ರವಾಗಿರುತ್ತದೆ. ಫ್ಯಾಕ್ಟರ್-ಕ್ರಿಟಿಕಲ್ ಗ್ರಾಫ್ ಎಂಬುದು ಬೆಸ ಸಂಖ್ಯೆಯ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ ಆಗಿದೆ, ಅಂದರೆ ಪ್ರತಿ ಶೃಂಗ v ಗೆ, ಗ್ರಾಫ್ನಿಂದ v ಅನ್ನು ತೆಗೆದುಹಾಕಿದರೆ ಉಳಿದ ಶೃಂಗಗಳು ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಯನ್ನು ಹೊಂದಿರುತ್ತವೆ. G ಯು ಬೆಸ ಕಿವಿ ವಿಭಜನೆಯನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಗ್ರಾಫ್ G ಅಂಶ-ನಿರ್ಣಾಯಕವಾಗಿದೆ ಎಂದು ಕಂಡುಹಿಡಿದಿದೆ. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ಇದರ ಫಲಿತಾಂಶವು ಯಾವುದೇ ಗ್ರಾಫ್ ಜಿ ಯಲ್ಲಿ ಕಡಿಮೆ ಸಮ ಕಿವಿಗಳೊಂದಿಗೆ ಕಿವಿ ವಿಭಜನೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಾಗಿಸುತ್ತದೆ. ಸರಣಿ-ಸಮಾನಾಂತರ ರೇಖಾಚಿತ್ರಗಳು ಮರದ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯು ಸರಿಯಾದ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯಾಗಿದೆ, ಇದರಲ್ಲಿ ಮೊದಲ ಕಿವಿಯು ಒಂದೇ ತುದಿಯಲ್ಲಿದೆ ಮತ್ತು ನಂತರದ ಪ್ರತಿ ಕಿವಿಗೆ ಒಂದೇ ಕಿವಿ ಇರುತ್ತದೆ, ಅಂದರೆ ಎರಡೂ ಅಂತಿಮ ಬಿಂದುಗಳು ಅದರ ಮೇಲೆ ಇರುತ್ತವೆ. ನೆಸ್ಟೆಡ್ ಕಿವಿ ವಿಭಜನೆಯು ಮರದ ಕಿವಿ ವಿಭಜನೆಯಾಗಿದ್ದು, ಪ್ರತಿ ಕಿವಿಯೊಳಗೆ, ಇತರ ಕಿವಿಗಳ ತುದಿ ಬಿಂದುಗಳ ಜೋಡಿಗಳು ನೆಸ್ಟೆಡ್ ಮಧ್ಯಂತರಗಳ ಗುಂಪನ್ನು ರೂಪಿಸುತ್ತವೆ. ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ ಎನ್ನುವುದು ಎರಡು ಗೊತ್ತುಪಡಿಸಿದ ಟರ್ಮಿನಲ್ಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ ಆಗಿದ್ದು, ಸಣ್ಣ ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ಗಳನ್ನು ಎರಡು ವಿಧಾನಗಳಲ್ಲಿ ಒಂದರಲ್ಲಿ ಸಂಯೋಜಿಸುವ ಮೂಲಕ ಪುನರಾವರ್ತಿತವಾಗಿ ರಚಿಸಬಹುದುಃ ಸರಣಿ ಸಂಯೋಜನೆ (ಒಂದು ಸಣ್ಣ ಗ್ರಾಫ್ನಿಂದ ಒಂದು ಟರ್ಮಿನಲ್ ಅನ್ನು ಇನ್ನೊಂದು ಸಣ್ಣ ಗ್ರಾಫ್ನಿಂದ ಒಂದು ಟರ್ಮಿನಲ್ನೊಂದಿಗೆ ಗುರುತಿಸುವುದು, ಮತ್ತು ಇತರ ಎರಡು ಟರ್ಮಿನಲ್ಗಳನ್ನು ಸಂಯೋಜಿತ ಗ್ರಾಫ್ನ ಟರ್ಮಿನಲ್ಗಳಾಗಿ ಇಟ್ಟುಕೊಳ್ಳುವುದು) ಮತ್ತು ಸಮಾನಾಂತರ ಸಂಯೋಜನೆ (ಎರಡು ಸಣ್ಣ ಗ್ರಾಫ್ಗಳಿಂದ ಎರಡೂ ಜೋಡಿ ಟರ್ಮಿನಲ್ಗಳನ್ನು ಗುರುತಿಸುವುದು). ಈ ಕೆಳಗಿನ ಫಲಿತಾಂಶವು ಈ ಕೆಳಗಿನ ಕಾರಣಗಳಿಂದ ಉಂಟಾಗುತ್ತದೆಃ 2-ಕಶೇರುಕ-ಸಂಪರ್ಕಿತ ರೇಖಾಚಿತ್ರವು ನೆಸ್ಟೆಡ್ ಕಿವಿ ವಿಭಜನೆಯನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಸರಣಿ-ಸಮಾನಾಂತರವಾಗಿರುತ್ತದೆ. ಇದಲ್ಲದೆ, 2-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತ ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ನ ಯಾವುದೇ ತೆರೆದ ಕಿವಿ ವಿಭಜನೆಯನ್ನು ನೆಸ್ಟೆಡ್ ಮಾಡಬೇಕು. ಎರಡು ಟರ್ಮಿನಲ್ಗಳ ನಡುವಿನ ಮಾರ್ಗದಿಂದ ಪ್ರಾರಂಭವಾಗುವ ತೆರೆದ ಕಿವಿ ವಿಭಜನೆಗಳನ್ನು ಬಳಸಿಕೊಂಡು 2-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕವಿಲ್ಲದ ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ಗಳಿಗೆ ಫಲಿತಾಂಶವನ್ನು ವಿಸ್ತರಿಸಬಹುದು. ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳು-ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯ ಪರಿಕಲ್ಪನೆಯನ್ನು ಗ್ರಾಫ್ಗಳಿಂದ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳವರೆಗೆ ವಿಸ್ತರಿಸಬಹುದು. ಮ್ಯಾಟ್ರಾಯಿಡ್ನ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯನ್ನು ಎರಡು ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿರುವ ಮ್ಯಾಟ್ರಾಯಿಡ್ನ ಸರ್ಕ್ಯೂಟ್ಗಳ ಅನುಕ್ರಮವೆಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆಃ ಅನುಕ್ರಮದಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಸರ್ಕ್ಯೂಟ್ ಹಿಂದಿನ ಸರ್ಕ್ಯೂಟ್ಗಳೊಂದಿಗೆ ಖಾಲಿ ಇಲ್ಲದ ಛೇದನವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಅನುಕ್ರಮದಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಸರ್ಕ್ಯೂಟ್ ಹಿಂದಿನ ಎಲ್ಲಾ ಸರ್ಕ್ಯೂಟ್ಗಳನ್ನು ಸಂಕುಚಿತಗೊಳಿಸಿದ್ದರೂ ಸಹ ಸರ್ಕ್ಯೂಟ್ ಆಗಿ ಉಳಿಯುತ್ತದೆ. ಗ್ರಾಫ್ ಜಿ ಯ ಗ್ರಾಫಿಕ್ ಮ್ಯಾಟ್ರಾಯ್ಡ್ಗೆ ಅನ್ವಯಿಸಿದಾಗ, ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯ ಈ ವ್ಯಾಖ್ಯಾನವು ಜಿ ಯ ಸರಿಯಾದ ಕಿವಿ ಕೊಳೆಯುವಿಕೆಯ ವ್ಯಾಖ್ಯಾನದೊಂದಿಗೆ ಹೊಂದಿಕೆಯಾಗುತ್ತದೆಃ ಪ್ರತಿ ಸರ್ಕ್ಯೂಟ್ ಹಿಂದಿನ ಸರ್ಕ್ಯೂಟ್ಗಳಿಗೆ ಸೇರಿದ ಕನಿಷ್ಠ ಒಂದು ಅಂಚನ್ನು ಒಳಗೊಂಡಿರುವ ಅಗತ್ಯತೆಯಿಂದ ಅಸಮರ್ಪಕ ಕೊಳೆಯುವಿಕೆಯನ್ನು ಹೊರಗಿಡಲಾಗುತ್ತದೆ. ಈ ವ್ಯಾಖ್ಯಾನವನ್ನು ಬಳಸಿಕೊಂಡು, ಮ್ಯಾಟ್ರಾಯ್ಡ್ ಅನ್ನು ಕಿವಿ ವಿಭಜನೆಯನ್ನು ಹೊಂದಿರುವಾಗ ಫ್ಯಾಕ್ಟರ್-ಕ್ರಿಟಿಕಲ್ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಇದರಲ್ಲಿ ಅನುಕ್ರಮದಲ್ಲಿ ಪ್ರತಿ ಸರ್ಕ್ಯೂಟ್ ಬೆಸ ಸಂಖ್ಯೆಯ ಹೊಸ ಅಂಶಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಕ್ರಮಾವಳಿಗಳು ಶಾಸ್ತ್ರೀಯ ಕಂಪ್ಯೂಟರ್ಗಳಲ್ಲಿ, 2-ಅಂಚಿನ-ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ಗಳ ಕಿವಿ ವಿಭಜನೆಗಳು ಮತ್ತು 2-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ಗಳ ತೆರೆದ ಕಿವಿ ವಿಭಜನೆಗಳನ್ನು ದುರಾಸೆಯ ಕ್ರಮಾವಳಿಗಳಿಂದ ಕಂಡುಹಿಡಿಯಬಹುದು, ಅದು ಪ್ರತಿ ಕಿವಿಯನ್ನು ಒಂದು ಸಮಯದಲ್ಲಿ ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ಒಂದೇ ಸಮಯದಲ್ಲಿ ಕಿವಿ ವಿಭಜನೆಗಳು, ತೆರೆದ ಕಿವಿ ವಿಭಜನೆಗಳು, ಎಸ್ಟಿ-ಸಂಖ್ಯೆಗಳು ಮತ್ತು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ (ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ)-ದೃಷ್ಟಿಕೋನಗಳನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಸರಳ ದುರಾಸೆಯ ವಿಧಾನವನ್ನು ನೀಡಲಾಗಿದೆ. ಈ ವಿಧಾನವು ಒಂದು ಮಾರ್ಗ-ಉತ್ಪಾದಿಸುವ ನಿಯಮದ ಮೂಲಕ ಸರಪಳಿ ವಿಭಜನೆ ಎಂಬ ವಿಶೇಷ ಕಿವಿ ವಿಭಜನೆಯನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವುದನ್ನು ಆಧರಿಸಿದೆ. ಬೇರ್ಪಡಿಸದ ಕಿವಿ ವಿಭಜನೆಗಳನ್ನು ಸಹ ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ನಿರ್ಮಿಸಬಹುದು ಎಂದು ತೋರಿಸುತ್ತದೆ. , ಮತ್ತು ವಿವಿಧ ರೀತಿಯ ಕಿವಿ ವಿಭಜನೆಗಳನ್ನು ನಿರ್ಮಿಸಲು ಪರಿಣಾಮಕಾರಿ ಸಮಾನಾಂತರ ಕ್ರಮಾವಳಿಗಳನ್ನು ಒದಗಿಸಿದೆ. ಉದಾಹರಣೆಗೆ, 2-ಅಂಚಿನ-ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ನ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು, ಈ ಕೆಳಗಿನ ಹಂತಗಳ ಪ್ರಕಾರ ಆದಾಯದ ಕ್ರಮಾವಳಿಃ ನೀಡಲಾದ ಗ್ರಾಫ್ನ ವಿಸ್ತಾರವಾದ ಮರವನ್ನು ಹುಡುಕಿ ಮತ್ತು ಮರಕ್ಕೆ ಮೂಲವನ್ನು ಆಯ್ಕೆ ಮಾಡಿ. ಮರದ ಭಾಗವಾಗಿರದ ಪ್ರತಿ ಅಂಚಿನ ಯು. ವಿ. ಗೆ, ಯು ಮತ್ತು ವಿ ನ ಮೂಲ ಮತ್ತು ಅತ್ಯಂತ ಕಡಿಮೆ ಸಾಮಾನ್ಯ ಪೂರ್ವಜರ ನಡುವಿನ ಅಂತರವನ್ನು ನಿರ್ಧರಿಸಿ. ಮರದ ಭಾಗವಾಗಿರುವ ಪ್ರತಿ ಅಂಚಿನ ಯು. ವಿ. ಗೆ, ಅನುಗುಣವಾದ "ಮಾಸ್ಟರ್ ಎಡ್ಜ್" ಅನ್ನು ಹುಡುಕಿ, ಮರಕ್ಕೆ ಡಬ್ಲ್ಯೂಎಕ್ಸ್ ಅನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ರೂಪುಗೊಂಡ ಚಕ್ರವು ಯುವಿ ಮೂಲಕ ಹಾದುಹೋಗುತ್ತದೆ ಮತ್ತು ಅಂತಹ ಅಂಚುಗಳ ನಡುವೆ, ಡಬ್ಲ್ಯೂ ಮತ್ತು ಎಕ್ಸ್ ಸಾಧ್ಯವಾದಷ್ಟು ಮೂಲಕ್ಕೆ ಹತ್ತಿರವಿರುವ ಅತ್ಯಂತ ಕಡಿಮೆ ಸಾಮಾನ್ಯ ಪೂರ್ವಜರನ್ನು ಹೊಂದಿರುತ್ತದೆ (ಅಂಚಿನ ಗುರುತಿಸುವಿಕೆಗಳಿಂದ ಮುರಿದ ಸಂಬಂಧಗಳೊಂದಿಗೆ). ಪ್ರತಿ ಮರವಲ್ಲದ ಅಂಚಿಗೆ ಒಂದು ಕಿವಿಯನ್ನು ರಚಿಸಿ, ಅದು ಮತ್ತು ಅದು ಮಾಸ್ಟರ್ ಆಗಿರುವ ಮರದ ಅಂಚುಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಮತ್ತು ಕಿವಿಗಳನ್ನು ಅವುಗಳ ಮಾಸ್ಟರ್ ಅಂಚುಗಳ ಮೂಲದಿಂದ ಇರುವ ಅಂತರದಿಂದ ಆದೇಶಿಸಿ (ಅದೇ ಟೈ-ಬ್ರೇಕಿಂಗ್ ನಿಯಮದೊಂದಿಗೆ). ಈ ಕ್ರಮಾವಳಿಗಳನ್ನು ಪರೀಕ್ಷಾ ಸಂಪರ್ಕ, ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ಗಳನ್ನು ಗುರುತಿಸುವುದು ಮತ್ತು ಗ್ರಾಫ್ಗಳ ಮೊದಲ-ಸಂಖ್ಯೆಗಳನ್ನು ನಿರ್ಮಿಸುವುದು (ಪ್ಲ್ಯಾನಾರಿಟಿ ಪರೀಕ್ಷೆಯಲ್ಲಿ ಪ್ರಮುಖ ಉಪ-ಕ್ರಮಾವಳಿ) ಸೇರಿದಂತೆ ಇತರ ಸಮಸ್ಯೆಗಳಿಗೆ ಉಪ-ಕ್ರಮಾವಳಿಗಳಾಗಿ ಬಳಸಬಹುದು. ಪ್ರತಿ ಕಿವಿಯು ಮ್ಯಾಟ್ರಾಯ್ಡ್ನ ಒಂದೇ ಸ್ಥಿರ ಅಂಶವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಎಂಬ ಹೆಚ್ಚುವರಿ ನಿರ್ಬಂಧದೊಂದಿಗೆ ನಿರ್ದಿಷ್ಟ ಮ್ಯಾಟ್ರಾಯ್ಡ್ನ ಕಿವಿಯ ಕೊಳೆಯುವಿಕೆಯು, ಮ್ಯಾಟ್ರಾಯ್ಡ್ಗಾಗಿ ಸ್ವತಂತ್ರ ಒರಾಕಲ್ಗೆ ಪ್ರವೇಶವನ್ನು ನೀಡಿದ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಕಂಡುಬರುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತವು ಮ್ಯಾಟ್ರಾಯಿಡ್ ಸಿದ್ಧಾಂತವನ್ನು ಆಕ್ಷೇಪಿಸುತ್ತದೆ