Euler tour technique
ಲಿಯೊನ್ಹಾರ್ಡ್ ಯೂಲರ್ ಅವರ ಹೆಸರಿನ ಯೂಲರ್ ಪ್ರವಾಸ ತಂತ್ರವು (ಇಟಿಟಿ) ಮರಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಒಂದು ವಿಧಾನವಾಗಿದೆ. ಮರದ ಪ್ರತಿ ಅಂಚಿಗೆ ಎರಡು ನಿರ್ದೇಶನದ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ನಿರ್ದೇಶನದ ರೇಖಾಚಿತ್ರವಾಗಿ ಮರವನ್ನು ನೋಡಲಾಗುತ್ತದೆ. ಮರವನ್ನು ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ನ ಯೂಲೇರಿಯನ್ ಸರ್ಕ್ಯೂಟ್ ಆಗಿ ಪ್ರತಿನಿಧಿಸಬಹುದು, ಇದನ್ನು ಮರದ ಯೂಲರ್ ಪ್ರವಾಸ ಪ್ರಾತಿನಿಧ್ಯ (ಇಟಿಆರ್) ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮಿಕ್ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಸಾಮಾನ್ಯ ಸಮಸ್ಯೆಗಳಿಗೆ ಪರಿಹಾರಗಳನ್ನು ಸಮರ್ಥವಾಗಿ, ಸಮಾನಾಂತರವಾಗಿ ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಇಟಿಟಿ ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಇದನ್ನು 1984ರಲ್ಲಿ ಟಾರ್ಜನ್ ಮತ್ತು ವಿಶ್ಕಿನ್ ಪರಿಚಯಿಸಿದರು. ನಿರ್ದೇಶನವಿಲ್ಲದ ಮರವನ್ನು ಅಂಚುಗಳ ಗುಂಪಾಗಿ ಪ್ರಸ್ತುತಪಡಿಸಿದರೆ, ಯೂಲರ್ ಪ್ರವಾಸ ಪ್ರಾತಿನಿಧ್ಯವನ್ನು (ಇಟಿಆರ್) ಈ ಕೆಳಗಿನಂತೆ ಸಮಾನಾಂತರವಾಗಿ ನಿರ್ಮಿಸಬಹುದುಃ ನಾವು ನಿರ್ದೇಶನದ ಅಂಚುಗಳ ಸಮ್ಮಿತೀಯ ಪಟ್ಟಿಯನ್ನು ನಿರ್ಮಿಸುತ್ತೇವೆಃ ಮರದ ಪ್ರತಿ ನಿರ್ದೇಶನವಿಲ್ಲದ ಅಂಚಿಗೆ (ಯು, ವಿ), ಅಂಚಿನ ಪಟ್ಟಿಯಲ್ಲಿ (ಯು, ವಿ) ಮತ್ತು (ವಿ, ಯು) ಅನ್ನು ಸೇರಿಸಿ. ಅಂಚಿನ ಪಟ್ಟಿಯನ್ನು ನಿಘಂಟಿನ ಪ್ರಕಾರ ವಿಂಗಡಿಸಿ. (ಇಲ್ಲಿ ನಾವು ಮರದ ನೋಡ್ಗಳನ್ನು ಕ್ರಮಬದ್ಧಗೊಳಿಸಲಾಗಿದೆ ಮತ್ತು ಈ ಕ್ರಮದಲ್ಲಿ ಮೂಲವು ಮೊದಲ ಅಂಶವಾಗಿದೆ ಎಂದು ಭಾವಿಸುತ್ತೇವೆ.) ಪ್ರತಿ ನೋಡ್ಗೆ (ಮುಂದಿನ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ) ಹೊಂದಾಣಿಕೆಯ ಪಟ್ಟಿಗಳನ್ನು ರಚಿಸಿ ಮತ್ತು ನೋಡ್ಗಳಿಂದ ಹೊಂದಾಣಿಕೆಯ ಪಟ್ಟಿಗಳ ಮೊದಲ ನಮೂದುಗಳಿಗೆ (ಮೊದಲ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ) ನಕ್ಷೆಯನ್ನು ರಚಿಸಿಃ ಪಟ್ಟಿಯಲ್ಲಿರುವ ಪ್ರತಿ ಅಂಚಿಗೆ (u, v), ಸಮಾನಾಂತರವಾಗಿ ಮಾಡಿಃ ಹಿಂದಿನ ಅಂಚು (x, y) x  ಒತ್ತನ್ನು ಹೊಂದಿದ್ದರೆ, ಅಂದರೆ. ಬೇರೆ ನೋಡ್ನಿಂದ ಪ್ರಾರಂಭಿಸಿ, ಮೊದಲು ಹೊಂದಿಸಿ (ಯು) = (ಯು, ವಿ) ಇಲ್ಲದಿದ್ದರೆ x = ಯು, ಅಂದರೆ. ಅದೇ ನೋಡ್ನಿಂದ ಪ್ರಾರಂಭಿಸಿ, ಮುಂದಿನದನ್ನು ಹೊಂದಿಸಿ (x, y) = (u, v) ಈ ಕೆಳಗಿನ ನಿಯಮದ ಪ್ರಕಾರ ಸಮಾನಾಂತರವಾಗಿ ಎಲ್ಲಾ ಅಂಚುಗಳಿಗೆ (u, v) ಪಾಯಿಂಟರ್ ಸಕ್ (u, v) ಅನ್ನು ಹೊಂದಿಸುವ ಮೂಲಕ ಯೂಲರ್ ಪ್ರವಾಸ ಕ್ರಮದಲ್ಲಿ ಅಂಚಿನ ಪಟ್ಟಿಯನ್ನು (ಸಕ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ) ರಚಿಸಿಃ ಫಲಿತಾಂಶದ ಪಟ್ಟಿ ಸಕ್ ವೃತ್ತಾಕಾರವಾಗಿರುತ್ತದೆ. ಮರವು n ನೋಡ್ಗಳನ್ನು ಹೊಂದಿದ್ದರೆ ಒಟ್ಟಾರೆ ರಚನೆಯು W (n) = O (ವಿಂಗಡಣೆ (n)) (n ವಸ್ತುಗಳನ್ನು ಸಮಾನಾಂತರವಾಗಿ ವಿಂಗಡಿಸಲು ತೆಗೆದುಕೊಳ್ಳುವ ಸಮಯ) ಕೆಲಸವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಮರಗಳಲ್ಲಿ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ನೋಡ್ಗಳ ಸಂಖ್ಯೆಗಿಂತ ಒಂದು ಕಡಿಮೆ ಇರುತ್ತದೆ. ಬೇರುಗಳು, ಮುಂಗಡ ಮತ್ತು ಹಿಮ್ಮೆಟ್ಟುವ ಅಂಚುಗಳು ಮರವು ಮೂಲವನ್ನು ಹೊಂದಿದ್ದರೆ, ನಾವು ಆ ಮೂಲದಲ್ಲಿ ವೃತ್ತಾಕಾರದ ಪಟ್ಟಿಯ ಸಕ್ ಅನ್ನು ವಿಭಜಿಸಬಹುದು. ಅಂತಹ ಸಂದರ್ಭದಲ್ಲಿ, ನಾವು ಮುಂಗಡ ಮತ್ತು ಹಿಮ್ಮೆಟ್ಟುವ ಅಂಚುಗಳ ಬಗ್ಗೆ ಮಾತನಾಡಬಹುದುಃ ಯು, ವಿ ಜೋಡಿ ನೋಡ್ಗಳನ್ನು ನೀಡಿದರೆ, ಇಟಿಆರ್ನಲ್ಲಿ (ಯು, ವಿ) ಅಥವಾ (ವಿ, ಯು) ಮೊದಲ ಸಂಭವವನ್ನು ಮುಂಗಡ ಅಂಚು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಎರಡನೇ ಸಂಭವವನ್ನು ಹಿಮ್ಮೆಟ್ಟುವ ಅಂಚು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಮೊದಲ ಬಾರಿಗೆ ಅಂತಹ ಅಂಚನ್ನು ಹಾದುಹೋಗುವಾಗ ಮೂಲಕ್ಕೆ ದೂರವನ್ನು ಹೆಚ್ಚಿಸಲಾಗುತ್ತದೆ, ಆದರೆ ಎರಡನೇ ಬಾರಿಗೆ ದೂರವು ಕಡಿಮೆಯಾಗುತ್ತದೆ ಎಂಬ ಅಂತಃಪ್ರಜ್ಞೆಯನ್ನು ಇದು ಆಕರ್ಷಿಸುತ್ತದೆ. ಹೊಸ ಮೂಲದಲ್ಲಿ ವೃತ್ತಾಕಾರದ ಪಟ್ಟಿಯ ಸಕ್ ಅನ್ನು ವಿಭಜಿಸುವ ಮೂಲಕ ಮರವನ್ನು ಓ (1) ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ ಮರುಕ್ರಮಗೊಳಿಸಬಹುದು. ಅನ್ವಯಿಕೆಗಳು ಈ ಕೆಳಗಿನ ಎಲ್ಲಾ ಸಮಸ್ಯೆಗಳನ್ನು ಒ (ಪೂರ್ವಪ್ರತ್ಯಯ ಮೊತ್ತ (ಎನ್)) ನಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು (n ಅಂಶಗಳ ಪಟ್ಟಿಗೆ ಸಮಾನಾಂತರವಾಗಿ ಪೂರ್ವಪ್ರತ್ಯಯ ಮೊತ್ತದ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ತೆಗೆದುಕೊಳ್ಳುವ ಸಮಯ): ಮುಂಗಡ ಮತ್ತು ಹಿಮ್ಮೆಟ್ಟುವ ಅಂಚುಗಳನ್ನು ವರ್ಗೀಕರಿಸುವುದುಃ ಇಟಿಆರ್ನಲ್ಲಿ ಶ್ರೇಯಾಂಕವನ್ನು ಪಟ್ಟಿ ಮಾಡಿ ಮತ್ತು ಫಲಿತಾಂಶವನ್ನು ಎರಡು ಆಯಾಮದ ಶ್ರೇಣಿಯಲ್ಲಿ ಉಳಿಸಿ. ನಂತರ (ಯು, ವಿ) ಎ (ಯು, ವಿ) <ಎ (ವಿ, ಯು) ನ ಮುಂಗಡ ಅಂಚು, ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ ಹಿಮ್ಮೆಟ್ಟುವ ಅಂಚು. ಪ್ರತಿ ನೋಡ್ನ ಮಟ್ಟವನ್ನು ನಿರ್ಧರಿಸಿಃ ಇ. ಟಿ. ಆರ್. ನಲ್ಲಿ ಪೂರ್ವಪ್ರತ್ಯಯ ಮೊತ್ತವನ್ನು ಮಾಡಿ, ಅಲ್ಲಿ ಪ್ರತಿ ಮುಂಗಡ ಅಂಚು 1 ಎಂದು ಎಣಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಹಿಮ್ಮೆಟ್ಟುವ ಅಂಚು-1 ಎಂದು ಎಣಿಸಲಾಗುತ್ತದೆ. ನಂತರ ಮುಂಗಡದ ಅಂಚಿನಲ್ಲಿರುವ ಮೌಲ್ಯವು (ಯು, ವಿ) ವಿ ಮಟ್ಟವಾಗಿದೆ. ವಿ ನಲ್ಲಿ ಬೇರೂರಿರುವ ಸಬ್ಟ್ರೀಯಲ್ಲಿನ ನೋಡ್ಗಳ ಸಂಖ್ಯೆಃ ವಿ ಯ ಮೂಲವು ಯು ಎಂದು ಭಾವಿಸಿ, ಮುಂಗಡದ ಅಂಚನ್ನು (ಯು, ವಿ) ಮತ್ತು ಹಿಮ್ಮೆಟ್ಟುವ ಅಂಚನ್ನು (ವಿ, ಯು) ಸಮಾನಾಂತರವಾಗಿ ನಿರ್ಧರಿಸಿ, ನಂತರ ಪೂರ್ವಪ್ರತ್ಯಯ ಮೊತ್ತವನ್ನು ಬಳಸಿಕೊಂಡು (ಯು, ವಿ) ಮತ್ತು (ವಿ, ಯು) ನಡುವಿನ ಮುಂಗಡ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಿ. ನೋಡ್ ವಿ ನ ಆಳ-ಮೊದಲ ಹುಡುಕಾಟ ಸೂಚ್ಯಂಕಃ (ಯು, ವಿ) ಸೇರಿದಂತೆ ಮುಂಗಡ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಿ. ಎರಡು ನೋಡ್ಗಳ ಅತ್ಯಂತ ಕಡಿಮೆ ಸಾಮಾನ್ಯ ಪೂರ್ವಜರನ್ನು ನಿರ್ಧರಿಸಿ. ಯೂಲರ್ ಪ್ರವಾಸದ ಮರಗಳಾದ ಹೆನ್ಜಿಂಗರ್ ಮತ್ತು ಕಿಂಗ್ ತನ್ನ ಯೂಲರ್ ಪ್ರವಾಸವನ್ನು ಸಮತೋಲಿತ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀನಲ್ಲಿ ಇರಿಸಿಕೊಳ್ಳುವ ಮೂಲಕ ನಿರ್ದಿಷ್ಟ ಮರವನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಸೂಚಿಸುತ್ತಾರೆ, ಇದು ಪ್ರವಾಸದಲ್ಲಿನ ಸೂಚ್ಯಂಕದಿಂದ ಪ್ರಮುಖವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ಮೇಲಿನ ಉದಾಹರಣೆಯಲ್ಲಿರುವ 7 ನೋಡ್ಗಳನ್ನು ಹೊಂದಿರುವ ಅಸಮತೋಲಿತ ಮರವನ್ನು 14 ನೋಡ್ಗಳನ್ನು ಹೊಂದಿರುವ ಸಮತೋಲಿತ ಬೈನರಿ ಮರದಿಂದ ಪ್ರತಿನಿಧಿಸಲಾಗುತ್ತದೆ, ಪ್ರತಿ ಬಾರಿ ಪ್ರತಿ ನೋಡ್ ಪ್ರವಾಸದಲ್ಲಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತದೆ. ನಾವು ಇ. ಟಿ ಮರಗಳ ಸಂಗ್ರಹವನ್ನು ಬಳಸಿಕೊಂಡು ಅರಣ್ಯವನ್ನು (ಅಸೈಕ್ಲಿಕ್ ಗ್ರಾಫ್) ಪ್ರತಿನಿಧಿಸಬಹುದು-ಒಂದು ಅರಣ್ಯ ಮರಕ್ಕೆ ಒಂದು ಇ. ಟಿ ಮರ. ಈ ಪ್ರಾತಿನಿಧ್ಯವು "ನೋಡ್ v ನ ಮೂಲ ಯಾವುದು?" ಎಂಬ ಪ್ರಶ್ನೆಗೆ ತ್ವರಿತವಾಗಿ ಉತ್ತರಿಸಲು ನಮಗೆ ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಇ. ಟಿ. ಮರದ ಮೊದಲ ನೋಡ್ಗೆ ಚಲಿಸುವ ಮೂಲಕ (ಇ. ಟಿ. ಮರದಲ್ಲಿನ ನೋಡ್ಗಳನ್ನು ಯೂಲರ್ ಪ್ರವಾಸದಲ್ಲಿ ಅವುಗಳ ಸ್ಥಳದಿಂದ ಕೀಯ್ಡ್ ಮಾಡಲಾಗುತ್ತದೆ, ಮತ್ತು ಮೂಲವು ಪ್ರವಾಸದ ಮೊದಲ ಮತ್ತು ಕೊನೆಯ ನೋಡ್ ಆಗಿರುತ್ತದೆ). ಪ್ರತಿನಿಧಿಸಲಾದ ಅರಣ್ಯವನ್ನು ನವೀಕರಿಸಿದಾಗ (ಉದಾ. ಎರಡು ಮರಗಳನ್ನು ಒಂದೇ ಮರಕ್ಕೆ ಜೋಡಿಸುವ ಮೂಲಕ ಅಥವಾ ಒಂದು ಮರವನ್ನು ಎರಡು ಮರಗಳಾಗಿ ವಿಭಜಿಸುವ ಮೂಲಕ), ಅನುಗುಣವಾದ ಯೂಲರ್-ಪ್ರವಾಸ ರಚನೆಯನ್ನು ಸಮಯ ಒ (ಲಾಗ್ (ಎನ್)) ನಲ್ಲಿ ನವೀಕರಿಸಬಹುದು. ಲಿಂಕ್/ಕಟ್ ಮರಗಳು ಇದೇ ರೀತಿಯ ಕಾರ್ಯಕ್ಷಮತೆಯ ಖಾತರಿಗಳನ್ನು ಹೊಂದಿವೆ. ಎಲ್ಸಿ ಮರಗಳು ಮರದ ಹಾದಿಗಳಲ್ಲಿ ಒಟ್ಟುಗೂಡಿಸುವಿಕೆಯನ್ನು ನಿರ್ವಹಿಸಲು ಉತ್ತಮವಾಗಿದ್ದರೆ (ಇದು ಜಾಲಬಂಧ ಹರಿವಿನ ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಉತ್ತಮ ಆಯ್ಕೆಯ ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದೆ), ಇಟಿ ಮರಗಳು ಸಬ್ಟ್ರೀಗಳ ಮೇಲೆ ಒಟ್ಟು ಮಾಹಿತಿಯನ್ನು ಇಟ್ಟುಕೊಳ್ಳುವಲ್ಲಿ ಉತ್ತಮವಾಗಿವೆ. ಉಲ್ಲೇಖಗಳು ಗ್ರಾಫ್ ಕ್ರಮಾವಳಿಗಳು ಸಮಾನಾಂತರ ಕಂಪ್ಯೂಟಿಂಗ್