Trémaux tree
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ನ ಟ್ರೆಮಾಕ್ಸ್ ಮರವು ಆಳ-ಮೊದಲ ಹುಡುಕಾಟ ಮರಗಳನ್ನು ಸಾಮಾನ್ಯೀಕರಿಸುವ ಒಂದು ರೀತಿಯ ವಿಸ್ತಾರವಾದ ಮರವಾಗಿದೆ. ಮರದ ಪ್ರತಿಯೊಂದು ತುದಿಯು ಮರದಲ್ಲಿನ ಪೂರ್ವಜ-ವಂಶಸ್ಥ ಜೋಡಿಯನ್ನು ಸಂಪರ್ಕಿಸುವ ಗುಣಲಕ್ಷಣದಿಂದ ಅವುಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಟ್ರೆಮಾಕ್ಸ್ ಮರಗಳಿಗೆ 19ನೇ ಶತಮಾನದ ಫ್ರೆಂಚ್ ಲೇಖಕ ಚಾರ್ಲ್ಸ್ ಪಿಯರೆ ಟ್ರೆಮಾಕ್ಸ್ ಅವರ ಹೆಸರನ್ನು ಇಡಲಾಗಿದೆ, ಅವರು ಮ್ಯಾಜ್ಗಳನ್ನು ಪರಿಹರಿಸುವ ತಂತ್ರವಾಗಿ ಡೆಪ್ತ್-ಫಸ್ಟ್ ಸರ್ಚ್ನ ಒಂದು ರೂಪವನ್ನು ಬಳಸಿದರು. ಅವುಗಳನ್ನು ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರಗಳು ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ, ವಿಶೇಷವಾಗಿ ಅನಂತ ರೇಖಾಚಿತ್ರಗಳ ಸಂದರ್ಭದಲ್ಲಿ. ಎಲ್ಲಾ ಆಳ-ಮೊದಲ ಹುಡುಕಾಟ ಮರಗಳು ಮತ್ತು ಎಲ್ಲಾ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಮಾರ್ಗಗಳು ಟ್ರೆಮಾಕ್ಸ್ ಮರಗಳಾಗಿವೆ. ಸೀಮಿತ ಗ್ರಾಫ್ಗಳಲ್ಲಿ, ಪ್ರತಿ ಟ್ರೆಮಾಕ್ಸ್ ಮರವು ಡೆಪ್ತ್-ಫಸ್ಟ್ ಸರ್ಚ್ ಟ್ರೀ ಆಗಿದೆ, ಆದರೆ ಡೆಪ್ತ್-ಫಸ್ಟ್ ಸರ್ಚ್ ಸ್ವತಃ ಅಂತರ್ಗತವಾಗಿ ಅನುಕ್ರಮವಾಗಿದ್ದರೂ, ಟ್ರೆಮಾಕ್ಸ್ ಮರಗಳನ್ನು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗ ಆರ್ಎನ್ಸಿಯಲ್ಲಿ ಯಾದೃಚ್ಛಿಕ ಸಮಾನಾಂತರ ಕ್ರಮಾವಳಿಗಳಿಂದ ನಿರ್ಮಿಸಬಹುದು. ರೇಖಾಚಿತ್ರದ ಮರದ ಆಳವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲು ಅವುಗಳನ್ನು ಬಳಸಬಹುದು ಮತ್ತು ರೇಖಾಚಿತ್ರವು ಸಮತಟ್ಟಾದ ರೇಖಾಚಿತ್ರವೇ ಎಂಬುದನ್ನು ಪರೀಕ್ಷಿಸಲು ಎಡ-ಬಲ ಸಮತೋಲನ ಪರೀಕ್ಷೆಯ ಭಾಗವಾಗಿ ಬಳಸಬಹುದು. ಗ್ರಾಫ್ಗಳ ಮೊನಾಡಿಕ್ ಎರಡನೇ-ಕ್ರಮಾಂಕದ ತರ್ಕದಲ್ಲಿ ಟ್ರೆಮಾಕ್ಸ್ ಮರಗಳ ಗುಣಲಕ್ಷಣವು ಕೊರ್ಸೆಲ್ನ ಪ್ರಮೇಯವನ್ನು ಬಳಸಿಕೊಂಡು ಬೌಂಡೆಡ್ ಟ್ರೈವಿಡ್ತ್ನ ಗ್ರಾಫ್ಗಳಿಗೆ ದೃಷ್ಟಿಕೋನಗಳನ್ನು ಒಳಗೊಂಡ ಗ್ರಾಫ್ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಗುರುತಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಪ್ರತಿ ಅನಂತ ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ ಒಂದು ಟ್ರೆಮಾಕ್ಸ್ ಮರವನ್ನು ಹೊಂದಿಲ್ಲ, ಮತ್ತು ಪ್ರತಿ ಅನಂತ ಟ್ರೆಮಾಕ್ಸ್ ಮರವು ಆಳ-ಮೊದಲ ಹುಡುಕಾಟ ಮರವಲ್ಲ. ಟ್ರೆಮಾಕ್ಸ್ ಮರಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳನ್ನು ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರಿಂದ ನಿರೂಪಿಸಬಹುದು. ಒಂದು ಅನಂತ ಟ್ರೆಮಾಕ್ಸ್ ಮರವು ಗ್ರಾಫ್ನ ಪ್ರತಿ ತುದಿಯಲ್ಲಿ ನಿಖರವಾಗಿ ಒಂದು ಅನಂತ ಮಾರ್ಗವನ್ನು ಹೊಂದಿರಬೇಕು, ಮತ್ತು ಟ್ರೆಮಾಕ್ಸ್ ಮರದ ಅಸ್ತಿತ್ವವು ಪ್ರತಿ ತುದಿಯಲ್ಲಿ ಅನಂತದಲ್ಲಿ ಒಂದು ಬಿಂದುವನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ರೂಪುಗೊಂಡ ಟೋಪೋಲಾಜಿಕಲ್ ಪೂರ್ಣತೆಗಳು ಮೆಟ್ರಿಕ್ ಸ್ಥಳಗಳಾಗಿರುವ ಗ್ರಾಫ್ಗಳನ್ನು ನಿರೂಪಿಸುತ್ತದೆ. ವ್ಯಾಖ್ಯಾನ ಮತ್ತು ಉದಾಹರಣೆಗಳು, ಒಂದು ರೇಖಾಚಿತ್ರಕ್ಕಾಗಿ, ಟ್ರೆಮಾಕ್ಸ್ ಮರವು, ಪ್ರತಿಯೊಂದು ಅಂಚಿನಲ್ಲೂ, ಎರಡು ಅಂತಿಮ ಬಿಂದುಗಳಲ್ಲಿ ಒಂದನ್ನು ಹೊಂದಿರುವ ಮತ್ತು ಇನ್ನೊಂದರ ಪೂರ್ವಜರಾಗಿರುವ ಗುಣಲಕ್ಷಣವನ್ನು ಹೊಂದಿರುವ ವಿಸ್ತಾರವಾದ ಮರವಾಗಿದೆ. ವಿಸ್ತಾರವಾದ ಮರವಾಗಲು, ಇದು ಕೇವಲ ಅಂಚುಗಳನ್ನು ಮಾತ್ರ ಬಳಸಬೇಕು, ಮತ್ತು ಪ್ರತಿ ಶೃಂಗವನ್ನು ಒಳಗೊಂಡಿರಬೇಕು, ಪ್ರತಿ ಜೋಡಿ ಶೃಂಗಗಳ ನಡುವೆ ವಿಶಿಷ್ಟವಾದ ಸೀಮಿತ ಮಾರ್ಗವನ್ನು ಹೊಂದಿರಬೇಕು. ಹೆಚ್ಚುವರಿಯಾಗಿ, ಈ ಮರದಲ್ಲಿನ ಪೂರ್ವಜ-ವಂಶದ ಸಂಬಂಧವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲು, ಅದರ ಒಂದು ಶೃಂಗವನ್ನು ಅದರ ಮೂಲವೆಂದು ಗೊತ್ತುಪಡಿಸಬೇಕು. ಒಂದು ಸೀಮಿತ ನಕ್ಷೆಯು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಮಾರ್ಗವನ್ನು ಹೊಂದಿದ್ದರೆ, ಆ ಮಾರ್ಗವನ್ನು ಅದರ ಎರಡು ಅಂತಿಮ ಬಿಂದುಗಳಲ್ಲಿ ಒಂದರಲ್ಲಿ ಬೇರೂರಿಸುವುದರಿಂದ ಟ್ರೆಮಾಕ್ಸ್ ಮರವನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಅಂತಹ ಮಾರ್ಗಕ್ಕೆ, ಪ್ರತಿ ಜೋಡಿ ಶೃಂಗಗಳು ಪೂರ್ವಜ-ವಂಶಸ್ಥರ ಜೋಡಿಯಾಗಿರುತ್ತವೆ. ಕೆಳಗೆ ತೋರಿಸಿರುವ ರೇಖಾಚಿತ್ರದಲ್ಲಿ, 1-3,2-3, ಮತ್ತು 3-4 ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಮರವು ಶೃಂಗ 1 ಅಥವಾ ಶೃಂಗ 2ರಲ್ಲಿ ಬೇರೂರಿರುವಾಗ ಟ್ರೆಮಾಕ್ಸ್ ಮರವಾಗಿದೆಃ ರೇಖಾಚಿತ್ರದ ಪ್ರತಿಯೊಂದು ತುದಿಯು 1-2ರ ಅಂಚನ್ನು ಹೊರತುಪಡಿಸಿ ಮರಕ್ಕೆ ಸೇರಿದೆ, ಇದು (ಬೇರಿನ ಈ ಆಯ್ಕೆಗಳಿಗಾಗಿ) ಪೂರ್ವಜ-ವಂಶದ ಜೋಡಿಯನ್ನು ಸಂಪರ್ಕಿಸುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಅದೇ ಮರವನ್ನು ಶೃಂಗ 3 ಅಥವಾ ಶೃಂಗ 4 ರಲ್ಲಿ ಬೇರೂರಿಸುವುದರಿಂದ ಬೇರೂರಿರುವ ಮರವು ಟ್ರೆಮಾಕ್ಸ್ ಮರವಲ್ಲ, ಏಕೆಂದರೆ ಈ ಮೂಲ 1 ಮತ್ತು 2 ಇನ್ನು ಮುಂದೆ ಪರಸ್ಪರರ ಪೂರ್ವಜರು ಮತ್ತು ವಂಶಸ್ಥರಲ್ಲ. ಸೀಮಿತ ಗ್ರಾಫ್ಗಳ ಅಸ್ತಿತ್ವದಲ್ಲಿ, ಪ್ರತಿ ಸೀಮಿತ ಸಂಪರ್ಕಿತ ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ ಕನಿಷ್ಠ ಒಂದು ಟ್ರೆಮಾಕ್ಸ್ ಮರವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಆಳವಾದ ಮೊದಲ ಹುಡುಕಾಟವನ್ನು ಮಾಡುವ ಮೂಲಕ ಮತ್ತು ಪ್ರತಿ ಶೃಂಗವನ್ನು (ಹುಡುಕಾಟದ ಆರಂಭಿಕ ಶೃಂಗವನ್ನು ಹೊರತುಪಡಿಸಿ) ಅದನ್ನು ಕಂಡುಹಿಡಿದ ಹಿಂದಿನ ಶೃಂಗಕ್ಕೆ ಸಂಪರ್ಕಿಸುವ ಮೂಲಕ ಅಂತಹ ಮರವನ್ನು ನಿರ್ಮಿಸಬಹುದು. ಈ ರೀತಿಯಲ್ಲಿ ನಿರ್ಮಿಸಲಾದ ಮರವನ್ನು ಡೆಪ್ತ್-ಫಸ್ಟ್ ಸರ್ಚ್ ಟ್ರೀ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಗ್ರಾಫ್ನಲ್ಲಿ ಒಂದು ಅನಿಯಂತ್ರಿತ ಅಂಚು ಇದ್ದರೆ, ಮತ್ತು ಹುಡುಕಾಟದಿಂದ ತಲುಪಬೇಕಾದ ಎರಡು ಶೃಂಗಗಳಲ್ಲಿ ಮೊದಲನೆಯದಾಗಿದ್ದರೆ, ನಂತರ ಆಳವಾದ-ಮೊದಲ ಹುಡುಕಾಟ ಮರದಿಂದ ಇಳಿಯುವ ಉಪವೃಕ್ಷಕ್ಕೆ ಸೇರಿರಬೇಕು, ಏಕೆಂದರೆ ಈ ಉಪವೃಕ್ಷವನ್ನು ಅನ್ವೇಷಿಸುವಾಗ ಹುಡುಕಾಟವು ಅವಶ್ಯವಾಗಿ ಕಂಡುಕೊಳ್ಳುತ್ತದೆ, ಉಪವೃಕ್ಷದ ಇತರ ಶೃಂಗಗಳಲ್ಲಿ ಒಂದರಿಂದ ಅಥವಾ, ಅದು ವಿಫಲವಾದರೆ, ನೇರವಾಗಿ. ಪ್ರತಿಯೊಂದು ಸೀಮಿತ ಟ್ರೆಮಾಕ್ಸ್ ಮರವನ್ನು ಆಳ-ಮೊದಲ ಹುಡುಕಾಟ ಮರವಾಗಿ ಉತ್ಪಾದಿಸಬಹುದುಃ ಒಂದು ಸೀಮಿತ ಗ್ರಾಫ್ನ ಟ್ರೆಮಾಕ್ಸ್ ಮರವಾಗಿದ್ದರೆ, ಮತ್ತು ಯಾವುದೇ ಇತರ ಶೃಂಗಗಳನ್ನು ಅನ್ವೇಷಿಸುವ ಮೊದಲು ಪ್ರತಿ ಶೃಂಗದ ಮಕ್ಕಳನ್ನು ಆಳ-ಮೊದಲ ಹುಡುಕಾಟವು ಅನ್ವೇಷಿಸಿದರೆ, ಅದು ಅದರ ಆಳ-ಮೊದಲ ಹುಡುಕಾಟ ಮರವಾಗಿ ಉತ್ಪತ್ತಿಯಾಗುತ್ತದೆ. ಸಮಾನಾಂತರ ರಚನೆಯು ಅನುಕ್ರಮವಾದ ಡೆಪ್ತ್-ಫಸ್ಟ್ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ನಿಂದ ಕಂಡುಬರುವ ಟ್ರೆಮಾಕ್ಸ್ ಮರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪಿ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ, ಇದರಲ್ಲಿ ಪ್ರತಿ ಶೃಂಗದ ನೆರೆಹೊರೆಯವರನ್ನು ಅವುಗಳ ಗುರುತುಗಳ ಕ್ರಮದಲ್ಲಿ ಹುಡುಕಲಾಗುತ್ತದೆ. ಅದೇನೇ ಇದ್ದರೂ, ಯಾದೃಚ್ಛಿಕ ಸಮಾನಾಂತರ ಅಲ್ಗಾರಿದಮ್ ಮೂಲಕ ವಿಭಿನ್ನ ಟ್ರೆಮಾಕ್ಸ್ ಮರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಿದೆ, ಇದು ಟ್ರೆಮಾಕ್ಸ್ ಮರಗಳ ನಿರ್ಮಾಣವು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗ ಆರ್ಎನ್ಸಿಗೆ ಸೇರಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ. 0-1-ತೂಕದ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಕನಿಷ್ಠ-ತೂಕದ ಪರಿಪೂರ್ಣ ಹೊಂದಾಣಿಕೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಅಲ್ಗಾರಿದಮ್ ಮತ್ತೊಂದು ಯಾದೃಚ್ಛಿಕ ಸಮಾನಾಂತರ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಆಧರಿಸಿದೆ. 1997 ರ ಹೊತ್ತಿಗೆ, ಟ್ರೆಮಾಕ್ಸ್ ಮರದ ನಿರ್ಮಾಣವನ್ನು ಸಂಕೀರ್ಣತೆಯ ವರ್ಗ ಎನ್. ಸಿ. ಯಲ್ಲಿ ನಿರ್ಣಾಯಕ ಸಮಾನಾಂತರ ಕ್ರಮಾವಳಿಯಿಂದ ನಿರ್ವಹಿಸಬಹುದೇ ಎಂಬುದು ತಿಳಿದಿಲ್ಲ. ಎನ್. ಸಿ. ಯಲ್ಲಿ ಹೊಂದಾಣಿಕೆಗಳು ಕಂಡುಬಂದರೆ, ಟ್ರೆಮಾಕ್ಸ್ ಮರಗಳೂ ಸಹ ಕಂಡುಬರುತ್ತವೆ. ತಾರ್ಕಿಕ ಅಭಿವ್ಯಕ್ತಿ ಮೂಲ ಶೃಂಗದ ಆಯ್ಕೆಯೊಂದಿಗಿನ ಅಂಚುಗಳ ಗುಂಪೊಂದು ಟ್ರೆಮಾಕ್ಸ್ ಮರವನ್ನು ರೂಪಿಸುತ್ತದೆ ಎಂಬ ಗುಣವನ್ನು ವ್ಯಕ್ತಪಡಿಸಲು ಸಾಧ್ಯವಿದೆ, ಗ್ರಾಫ್ಗಳ ಮೊನಾಡಿಕ್ ಎರಡನೇ ಕ್ರಮಾಂಕದ ತರ್ಕದಲ್ಲಿ, ಮತ್ತು ಹೆಚ್ಚು ನಿರ್ದಿಷ್ಟವಾಗಿ ಎಂಎಸ್ಒ 2 ಎಂದು ಕರೆಯಲ್ಪಡುವ ಈ ತರ್ಕದ ರೂಪದಲ್ಲಿ, ಇದು ಶೃಂಗ ಮತ್ತು ಅಂಚಿನ ಸೆಟ್ಗಳ ಮೇಲೆ ಪರಿಮಾಣವನ್ನು ಅನುಮತಿಸುತ್ತದೆ. ಈ ಗುಣವನ್ನು ಈ ಕೆಳಗಿನ ಗುಣಲಕ್ಷಣಗಳ ಸಂಯೋಜನೆಯಾಗಿ ವ್ಯಕ್ತಪಡಿಸಬಹುದುಃ ರೇಖಾಚಿತ್ರವು ಅದರ ಅಂಚುಗಳಿಂದ ಸಂಪರ್ಕ ಹೊಂದಿದೆ. ಗ್ರಾಫ್ನ ಶೃಂಗಗಳ ಪ್ರತಿಯೊಂದು ಖಾಲಿ ಇಲ್ಲದ ಸರಿಯಾದ ಉಪವಿಭಾಗಕ್ಕೆ, ನಿರ್ದಿಷ್ಟ ಉಪವಿಭಾಗದಲ್ಲಿ ನಿಖರವಾಗಿ ಒಂದು ಅಂತಿಮ ಬಿಂದುವಿನೊಂದಿಗೆ ಒಂದು ಅಂಚು ಇದೆ ಎಂಬ ಹೇಳಿಕೆಯಂತೆ ಇದನ್ನು ತಾರ್ಕಿಕವಾಗಿ ವ್ಯಕ್ತಪಡಿಸಬಹುದು. ಇದು ಅಸಿಕ್ಲಿಕ್ ಆಗಿದೆ. ಪ್ರತಿ ಶೃಂಗವು ಶೂನ್ಯ ಅಥವಾ ಎರಡು ಅಂಚುಗಳಿಗೆ ಸಂಭವಿಸುವ ಖಾಲಿ ಉಪಗುಂಪು ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ ಎಂಬ ಹೇಳಿಕೆಯಂತೆ ಇದನ್ನು ತಾರ್ಕಿಕವಾಗಿ ವ್ಯಕ್ತಪಡಿಸಬಹುದು. ಒಳಗೆ ಇಲ್ಲದ ಪ್ರತಿಯೊಂದು ಅಂಚು ಪೂರ್ವಜ-ವಂಶಸ್ಥ ಜೋಡಿ ಶೃಂಗಗಳನ್ನು ಸಂಪರ್ಕಿಸುತ್ತದೆ. ಎರಡೂ ಅಂತಿಮ ಬಿಂದುಗಳು ಒಂದು ಮಾರ್ಗಕ್ಕೆ ಸೇರಿದಾಗ ಇದು ನಿಜವಾಗಿದೆ. ಎಲ್ಲಾ ಅಂಚುಗಳಿಗೆ, ನಿಖರವಾಗಿ ಎರಡು ಶೃಂಗಗಳು, ಅವುಗಳಲ್ಲಿ ಒಂದು, ಒಂದೇ ತುದಿಯಲ್ಲಿ ಆಪಾದಿತವಾಗಿರುತ್ತವೆ ಮತ್ತು ಎರಡೂ ಅಂತಿಮ ಬಿಂದುಗಳು ಕನಿಷ್ಠ ಒಂದು ತುದಿಯಲ್ಲಿ ಆಪಾದಿತವಾಗಿರುತ್ತವೆ ಎಂಬ ಹೇಳಿಕೆಯಂತೆ ಇದನ್ನು ತಾರ್ಕಿಕವಾಗಿ ವ್ಯಕ್ತಪಡಿಸಬಹುದು. ಟ್ರೆಮಾಕ್ಸ್ ಮರವನ್ನು ಈ ರೀತಿಯಲ್ಲಿ ಗುರುತಿಸಿದ ನಂತರ, ಪೂರ್ವಜರ ಅಂತಿಮ ಬಿಂದುವಿನಿಂದ ವಂಶಸ್ಥರ ಅಂತಿಮ ಬಿಂದುವಿನವರೆಗಿನ ದೃಷ್ಟಿಕೋನವನ್ನು ಹೊಂದಿರುವ ಅಂಚುಗಳ ಗುಂಪನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸುವ ಮೂಲಕ, ಕೊಟ್ಟಿರುವ ರೇಖಾಚಿತ್ರದ ದೃಷ್ಟಿಕೋನವನ್ನು, ಮೊನಾಡಿಕ್ ಎರಡನೇ ಕ್ರಮಾಂಕದ ತರ್ಕದಲ್ಲಿಯೂ ಸಹ ವಿವರಿಸಬಹುದು. ಈ ಗುಂಪಿನ ಹೊರಗಿನ ಉಳಿದ ಅಂಚುಗಳು ಬೇರೆ ದಿಕ್ಕಿನಲ್ಲಿರಬೇಕು. ಈ ತಂತ್ರವು ಮೊನಾಡಿಕ್ ಸೆಕೆಂಡ್ ಆರ್ಡರ್ ತರ್ಕದಲ್ಲಿ ದೃಷ್ಟಿಕೋನಗಳನ್ನು ಒಳಗೊಂಡ ಗ್ರಾಫ್ ಗುಣಲಕ್ಷಣಗಳನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ, ಇದು ಕೊರ್ಸೆಲ್ನ ಪ್ರಮೇಯವನ್ನು ಬಳಸಿಕೊಂಡು ಬೌಂಡೆಡ್ ಟ್ರೈವಿಡ್ತ್ನ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಈ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪರೀಕ್ಷಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಒಂದು ರೇಖಾಚಿತ್ರವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಮಾರ್ಗವನ್ನು ಹೊಂದಿದ್ದರೆ, ಆ ಮಾರ್ಗವು (ಅದರ ಒಂದು ಅಂತಿಮ ಬಿಂದುವಿನಲ್ಲಿ ಬೇರೂರಿದೆ) ಸಹ ಟ್ರೆಮಾಕ್ಸ್ ಮರವಾಗಿದೆ. ಪ್ರತಿ ಟ್ರೆಮಾಕ್ಸ್ ಮರವು ಈ ರೂಪವನ್ನು ಹೊಂದಿರುವ ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ಗಳು ಸೈಕಲ್ ಗ್ರಾಫ್ಗಳು, ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಸಮತೋಲಿತ ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ಗಳಾಗಿವೆ. ಟ್ರೆಮಾಕ್ಸ್ ಮರಗಳು ಮರದ ಆಳದ ಪರಿಕಲ್ಪನೆಯೊಂದಿಗೆ ನಿಕಟ ಸಂಬಂಧವನ್ನು ಹೊಂದಿವೆ. ರೇಖಾಚಿತ್ರದ ಮರದ ಆಳವನ್ನು ರೇಖಾಚಿತ್ರವಿರುವ ಅತ್ಯಂತ ಚಿಕ್ಕ ಸಂಖ್ಯೆ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಇದರಲ್ಲಿ ಆಳವಾದ ಟ್ರೆಮಾಕ್ಸ್ ಮರವಿದೆ, ಅದು ಅದರ ಉಪ ರೇಖಾಚಿತ್ರವಾಗಿದೆ. ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬದಲ್ಲಿ, ಮರದ ಆಳವು, ಕುಟುಂಬದ ಗ್ರಾಫ್ಗಳ ಸಣ್ಣ ಗ್ರಾಫ್ ಆಗಿ ಸಂಭವಿಸದ ಮಾರ್ಗದ ಅಸ್ತಿತ್ವಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ಗ್ರಾಫ್ಗಳಲ್ಲಿನ ಅನೇಕ ಕಠಿಣ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಗಳು ಕ್ರಮಾವಳಿಗಳನ್ನು ಹೊಂದಿದ್ದು, ಅವುಗಳ ಇನ್ಪುಟ್ಗಳ ಟ್ರೀ-ಡೆಪ್ತ್ನಿಂದ ನಿಯತಾಂಕಗೊಳಿಸಿದಾಗ ಸ್ಥಿರ-ನಿಯತಾಂಕವನ್ನು ಪತ್ತೆಹಚ್ಚಬಹುದು. ಕೊಟ್ಟಿರುವ ರೇಖಾಚಿತ್ರವು ಸಮತಟ್ಟಾಗಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸಲು ಫ್ರೇಸಿಕ್ಸ್-ರೊಸೆನ್ಸ್ಟಿಲ್ ಪ್ಲ್ಯಾನಾರಿಟಿ ಮಾನದಂಡದಲ್ಲಿ ಟ್ರೆಮಾಕ್ಸ್ ಮರಗಳು ಪ್ರಮುಖ ಪಾತ್ರವಹಿಸುತ್ತವೆ. ಈ ಮಾನದಂಡದ ಪ್ರಕಾರ, ಒಂದು ನಿರ್ದಿಷ್ಟ ಟ್ರೆಮಾಕ್ಸ್ ಮರಕ್ಕೆ, ಉಳಿದ ಅಂಚುಗಳನ್ನು ಮರದ ಎಡ ಅಥವಾ ಬಲಕ್ಕೆ ಸ್ಥಿರವಾದ ರೀತಿಯಲ್ಲಿ ಇರಿಸಬಹುದಾದರೆ, ಅದೇ ಸ್ಥಳವನ್ನು ಹೊಂದಿರುವ ಅಂಚುಗಳು ಪರಸ್ಪರ ದಾಟುವುದನ್ನು ತಡೆಯುವ ನಿರ್ಬಂಧಗಳಿಗೆ ಒಳಪಟ್ಟರೆ ರೇಖಾಚಿತ್ರವು ಸಮತಟ್ಟಾಗಿರುತ್ತದೆ. ಅನಂತ ರೇಖಾಚಿತ್ರಗಳಲ್ಲಿ ಅಸ್ತಿತ್ವವು ಪ್ರತಿ ಅನಂತ ರೇಖಾಚಿತ್ರವು ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. ಉದಾಹರಣೆಗೆ, ಲೆಕ್ಕವಿಲ್ಲದಷ್ಟು ಶೃಂಗಗಳ ಗುಂಪಿನ ಮೇಲಿನ ಸಂಪೂರ್ಣ ರೇಖಾಚಿತ್ರವು ಒಂದನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲಃ ಸಂಪೂರ್ಣ ರೇಖಾಚಿತ್ರದಲ್ಲಿರುವ ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರವು ಕೇವಲ ಒಂದು ಮಾರ್ಗವಾಗಿರಬಹುದು, ಆದರೆ ಒಂದು ಮಾರ್ಗವು ಎಣಿಸಬಹುದಾದ ಸಂಖ್ಯೆಯ ಶೃಂಗಗಳನ್ನು ಮಾತ್ರ ಹೊಂದಿರುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಎಣಿಸಬಹುದಾದ ಶೃಂಗಗಳ ಗುಂಪಿನಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಗ್ರಾಫ್ ಸಾಮಾನ್ಯ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಎಣಿಸಬಹುದಾದ ಗ್ರಾಫ್ಗಳಲ್ಲಿಯೂ ಸಹ, ಆಳ-ಮೊದಲ ಹುಡುಕಾಟವು ಅಂತಿಮವಾಗಿ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ ಅನ್ನು ಅನ್ವೇಷಿಸುವಲ್ಲಿ ಯಶಸ್ವಿಯಾಗದಿರಬಹುದು, ಮತ್ತು ಪ್ರತಿ ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರವನ್ನು ಆಳ-ಮೊದಲ ಹುಡುಕಾಟದಿಂದ ಉತ್ಪಾದಿಸಲಾಗುವುದಿಲ್ಲಃ ಆಳ-ಮೊದಲ ಹುಡುಕಾಟ ಮರವಾಗಲು, ಎಣಿಸಬಹುದಾದ ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರವು ಕೇವಲ ಒಂದು ಅನಂತ ಮಾರ್ಗವನ್ನು ಹೊಂದಿರಬೇಕು ಅಥವಾ ಅನಂತವಾದ ಅನೇಕ ಮಕ್ಕಳೊಂದಿಗೆ ಒಂದು ನೋಡ್ ಅನ್ನು ಹೊಂದಿರಬೇಕು (ಮತ್ತು ಎರಡೂ ಅಲ್ಲ). ಅನಂತ ಗ್ರಾಫ್ ಒಂದು ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರವನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದೇ ರೀತಿ ಪ್ರತಿ ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ ಚಿಕ್ಕದಾಗಿದೆ. ಇದರಿಂದ ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳು ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತರ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿವೆ. ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಎರಡು ವರ್ಗಗಳಲ್ಲಿ ಒಂದು ವರ್ಗವು ಉಭಯಪಕ್ಷೀಯ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಇದರಲ್ಲಿ ಉಭಯಪಕ್ಷೀಯತೆಯ ಒಂದು ಭಾಗವನ್ನು ಎಣಿಸಬಹುದು, ಇನ್ನೊಂದು ಭಾಗವನ್ನು ಲೆಕ್ಕ ಹಾಕಲಾಗುವುದಿಲ್ಲ ಮತ್ತು ಪ್ರತಿ ಶೃಂಗವು ಅನಂತ ಮಟ್ಟವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಇತರ ವರ್ಗವು ಅರೋನ್ಸಾಜನ್ ಮರಗಳಿಂದ ಪಡೆದ ಕೆಲವು ಗ್ರಾಫ್ಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಈ ಗುಣಲಕ್ಷಣದ ವಿವರಗಳು ಗಣಿತಶಾಸ್ತ್ರವನ್ನು ಔಪಚಾರಿಕಗೊಳಿಸಲು ಬಳಸುವ ಸೆಟ್-ಥಿಯೋರೆಟಿಕ್ ಆಕ್ಸಿಯೋಮ್ಯಾಟೈಸೇಷನ್ನ ಆಯ್ಕೆಯನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಮಾರ್ಟಿನ್ ಅವರ ಸಿದ್ಧಾಂತವು ನಿಜವಾಗಿರುವ ಮತ್ತು ನಿರಂತರ ಊಹೆಯು ಸುಳ್ಳಾಗಿರುವ ಸೆಟ್ ಸಿದ್ಧಾಂತದ ಮಾದರಿಗಳಲ್ಲಿ, ಈ ಗುಣಲಕ್ಷಣದಲ್ಲಿನ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ಗಳ ವರ್ಗವನ್ನು ಒಂದೇ ನಿಷೇಧಿತ ಮೈನರ್ನಿಂದ ಬದಲಾಯಿಸಬಹುದು. ಆದಾಗ್ಯೂ, ನಿರಂತರ ಊಹೆಯು ನಿಜವಾಗಿರುವ ಮಾದರಿಗಳಿಗೆ, ಈ ವರ್ಗವು ಸಣ್ಣ ಕ್ರಮದಲ್ಲಿ ಪರಸ್ಪರ ಹೋಲಿಸಲಾಗದ ಗ್ರಾಫ್ಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಎಂಡ್ಸ್ ಮತ್ತು ಮೆಟ್ರಿಜಬಿಲಿಟಿ ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರಗಳು ಅನಂತ ಗ್ರಾಫ್ನ ತುದಿಗಳೊಂದಿಗೆ ನಿಕಟ ಸಂಬಂಧವನ್ನು ಹೊಂದಿವೆ, ಅನಂತ ಮಾರ್ಗಗಳ ಸಮಾನತೆಯ ವರ್ಗಗಳು, ಅಂತರ್ಬೋಧೆಯಿಂದ, ಅದೇ ದಿಕ್ಕಿನಲ್ಲಿ ಅನಂತಕ್ಕೆ ಹೋಗುತ್ತವೆ. ಒಂದು ರೇಖಾಚಿತ್ರವು ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರವನ್ನು ಹೊಂದಿದ್ದರೆ, ಈ ಮರವು ರೇಖಾಚಿತ್ರದ ಪ್ರತಿಯೊಂದು ತುದಿಗೂ ನಿಖರವಾಗಿ ಒಂದು ಅನಂತ ಮಾರ್ಗವನ್ನು ಹೊಂದಿರಬೇಕು. ರೇಖಾಚಿತ್ರವನ್ನು ಸರಳ ಸಂಕೀರ್ಣವಾಗಿ ನೋಡುವ ಮೂಲಕ ಮತ್ತು ರೇಖಾಚಿತ್ರದ ಪ್ರತಿ ತುದಿಯಲ್ಲಿ ಅನಂತದಲ್ಲಿ ಒಂದು ಬಿಂದುವನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಅನಂತ ರೇಖಾಚಿತ್ರವನ್ನು ಟೋಪೋಲಾಜಿಕಲ್ ಜಾಗವನ್ನು ರೂಪಿಸಲು ಬಳಸಬಹುದು. ಈ ಟೋಪೋಲಜಿಯೊಂದಿಗೆ, ಅದರ ಶೃಂಗಗಳ ಗುಂಪನ್ನು ಮುಚ್ಚಿದ ಸೆಟ್ಗಳ ಎಣಿಸಬಹುದಾದ ಒಕ್ಕೂಟವಾಗಿ ವಿಭಜಿಸಬಹುದಾದರೆ ಮಾತ್ರ ಗ್ರಾಫ್ ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಹೆಚ್ಚುವರಿಯಾಗಿ, ಗ್ರಾಫ್ ಸಾಮಾನ್ಯ ವಿಸ್ತಾರವಾದ ಮರವನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಈ ಸ್ಥಳವಿಜ್ಞಾನದ ಜಾಗವನ್ನು ಮೆಟ್ರಿಕ್ ಜಾಗದಿಂದ ಪ್ರತಿನಿಧಿಸಬಹುದು. ಉಲ್ಲೇಖಗಳು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ವಸ್ತುಗಳು ಮರವನ್ನು ವ್ಯಾಪಿಸಿರುವ ಗ್ರಾಫ್ ಸಣ್ಣ ಸಿದ್ಧಾಂತ ಅನಂತ ಗ್ರಾಫ್ಗಳು