Treewidth
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ನ ಮೂರು ಅಗಲವು ಒಂದು ಪೂರ್ಣಾಂಕ ಸಂಖ್ಯೆಯಾಗಿದ್ದು, ಇದು ಅನೌಪಚಾರಿಕವಾಗಿ, ಗ್ರಾಫ್ ಮರದಿಂದ ಎಷ್ಟು ದೂರದಲ್ಲಿದೆ ಎಂಬುದನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸುತ್ತದೆ. ಅತ್ಯಂತ ಚಿಕ್ಕ ಟ್ರೆವಿಡ್ತ್ 1 ಆಗಿದೆ; ಟ್ರೆವಿಡ್ತ್ 1 ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳು ನಿಖರವಾಗಿ ಮರಗಳು ಮತ್ತು ಕಾಡುಗಳಾಗಿವೆ. ಗರಿಷ್ಠ 2 ತ್ರಿ ಅಗಲವನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳು ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ಗಳಾಗಿವೆ. ನಿಖರವಾಗಿ ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿರುವ ಗರಿಷ್ಠ ಗ್ರಾಫ್ಗಳನ್ನು-ಮರಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಗರಿಷ್ಠ ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳನ್ನು ಭಾಗಶಃ-ಮರಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಇತರ ಅನೇಕ ಚೆನ್ನಾಗಿ ಅಧ್ಯಯನ ಮಾಡಲಾದ ಗ್ರಾಫ್ ಕುಟುಂಬಗಳು ಸಹ ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿವೆ. ಮೂರು ಅಗಲವನ್ನು ಔಪಚಾರಿಕವಾಗಿ ಹಲವಾರು ಸಮಾನ ರೀತಿಯಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದುಃ ಗ್ರಾಫ್ನ ಮರದ ವಿಭಜನೆಯಲ್ಲಿ ಹೊಂದಿಸಲಾದ ಅತಿದೊಡ್ಡ ಶೃಂಗದ ಗಾತ್ರದ ದೃಷ್ಟಿಯಿಂದ, ಗ್ರಾಫ್ನ ಸ್ವರಮೇಳದ ಪೂರ್ಣಗೊಳಿಸುವಿಕೆಯಲ್ಲಿ ಅತಿದೊಡ್ಡ ಗುಂಪಿನ ಗಾತ್ರದ ದೃಷ್ಟಿಯಿಂದ, ಗ್ರಾಫ್ನಲ್ಲಿ ಅನ್ವೇಷಣೆ-ತಪ್ಪಿಸಿಕೊಳ್ಳುವ ಆಟದ ಕಾರ್ಯತಂತ್ರವನ್ನು ವಿವರಿಸುವ ಆಶ್ರಯದ ಗರಿಷ್ಠ ಕ್ರಮದ ದೃಷ್ಟಿಯಿಂದ, ಅಥವಾ ಬ್ರ್ಯಾಂಬಲ್ನ ಗರಿಷ್ಠ ಕ್ರಮದ ದೃಷ್ಟಿಯಿಂದ, ಪರಸ್ಪರ ಸ್ಪರ್ಶಿಸುವ ಸಂಪರ್ಕಿತ ಉಪಗ್ರಾಫ್ಗಳ ಸಂಗ್ರಹ. ಮೂರು ಅಗಲವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಗ್ರಾಫ್ ಕ್ರಮಾವಳಿಗಳ ನಿಯತಾಂಕ ಸಂಕೀರ್ಣತೆಯ ವಿಶ್ಲೇಷಣೆಯಲ್ಲಿ ನಿಯತಾಂಕವಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ. ಸಾಮಾನ್ಯ ಗ್ರಾಫ್ಗಳಿಗೆ ಎನ್ಪಿ-ಕಠಿಣವಾಗಿರುವ ಅನೇಕ ಕ್ರಮಾವಳಿಗಳು, ಮೂರು ಅಗಲವು ಸ್ಥಿರಾಂಕದಿಂದ ಸುತ್ತುವರಿದಾಗ ಸುಲಭವಾಗುತ್ತದೆ. ತ್ರಿ ಅಗಲದ ಪರಿಕಲ್ಪನೆಯನ್ನು ಮೂಲತಃ ಆಯಾಮದ ಹೆಸರಿನಲ್ಲಿ ಪರಿಚಯಿಸಲಾಯಿತು. ಇದು ಬೇರೆ ಗ್ರಾಫ್ ನಿಯತಾಂಕವಾದ ಹ್ಯಾಡ್ವಿಗರ್ ಸಂಖ್ಯೆಯೊಂದಿಗೆ ಹಂಚಿಕೊಳ್ಳುವ ಗುಣಲಕ್ಷಣಗಳ ಆಧಾರದ ಮೇಲೆ ಇದನ್ನು ನಂತರ ಮರುಶೋಧಿಸಲಾಯಿತು. ನಂತರ ಇದನ್ನು ಮತ್ತೆ ಕಂಡುಹಿಡಿಯಲಾಯಿತು ಮತ್ತು ನಂತರ ಅನೇಕ ಇತರ ಲೇಖಕರು ಇದನ್ನು ಅಧ್ಯಯನ ಮಾಡಿದ್ದಾರೆ. ವ್ಯಾಖ್ಯಾನ ಗ್ರಾಫ್ನ ಮರದ ವಿಭಜನೆಯು ನೋಡ್ಗಳನ್ನು ಹೊಂದಿರುವ ಮರವಾಗಿದೆ, ಅಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ ಈ ಕೆಳಗಿನ ಗುಣಲಕ್ಷಣಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ (ನೋಡ್ ಎಂಬ ಪದವನ್ನು ಶೃಂಗಗಳೊಂದಿಗೆ ಗೊಂದಲವನ್ನು ತಪ್ಪಿಸಲು ಶೀರ್ಷವನ್ನು ಉಲ್ಲೇಖಿಸಲು ಬಳಸಲಾಗುತ್ತದೆ): ಎಲ್ಲಾ ಸೆಟ್ಗಳ ಒಕ್ಕೂಟವು ಸಮಾನವಾಗಿರುತ್ತದೆ. ಅಂದರೆ, ಪ್ರತಿ ಗ್ರಾಫ್ ಶೃಂಗವು ಕನಿಷ್ಠ ಒಂದು ಮರದ ನೋಡ್ನಲ್ಲಿ ಇರುತ್ತದೆ. ಒಂದು ವೇಳೆ ಮತ್ತು ಎರಡೂ ಶೃಂಗವನ್ನು ಹೊಂದಿದ್ದರೆ, ಮತ್ತು ನಡುವಿನ (ಅನನ್ಯ) ಮಾರ್ಗದಲ್ಲಿರುವ ಎಲ್ಲಾ ನೋಡ್ಗಳು ಸಹ ಹೊಂದಿರುತ್ತವೆ. ಸಮಾನವಾಗಿ, ಶೃಂಗವನ್ನು ಹೊಂದಿರುವ ಮರದ ಗ್ರಂಥಿಗಳು ಅದರ ಸಂಪರ್ಕಿತ ಉಪವೃಕ್ಷವನ್ನು ರೂಪಿಸುತ್ತವೆ. ಗ್ರಾಫ್ನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಅಂಚಿಗೆ, ಮತ್ತು ಎರಡನ್ನೂ ಒಳಗೊಂಡಿರುವ ಉಪವಿಭಾಗವಿದೆ. ಅಂದರೆ, ಅನುಗುಣವಾದ ಸಬ್ಟ್ರೀಗಳು ಸಾಮಾನ್ಯವಾದ ನೋಡ್ ಅನ್ನು ಹೊಂದಿರುವಾಗ ಮಾತ್ರ ಗ್ರಾಫ್ನಲ್ಲಿ ಶೃಂಗಗಳು ಪಕ್ಕದಲ್ಲಿರುತ್ತವೆ. ಮರದ ಕೊಳೆಯುವಿಕೆಯ ಅಗಲವು ಅದರ ಅತಿದೊಡ್ಡ ಗುಂಪಿನ ಮೈನಸ್ ಒಂದರ ಗಾತ್ರವಾಗಿದೆ. ಗ್ರಾಫ್ನ ಮೂರು ಅಗಲವು ಎಲ್ಲಾ ಸಂಭವನೀಯ ಮರದ ವಿಭಜನೆಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಅಗಲವಾಗಿದೆ. ಈ ವ್ಯಾಖ್ಯಾನದಲ್ಲಿ, ಮರದ ಮೂರು ಅಗಲವನ್ನು ಒಂದಕ್ಕೆ ಸಮಾನವಾಗಿಸುವ ಸಲುವಾಗಿ ಅತಿದೊಡ್ಡ ಗುಂಪಿನ ಗಾತ್ರವನ್ನು ಒಂದರಿಂದ ಕಡಿಮೆ ಮಾಡಲಾಗುತ್ತದೆ. ಸಮಾನವಾಗಿ, ತ್ರಿ ಅಗಲವು ಚಿಕ್ಕ ಗುಂಪಿನ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುವ ಸ್ವರಮೇಳದ ಗ್ರಾಫ್ನಲ್ಲಿರುವ ಅತಿದೊಡ್ಡ ಗುಂಪಿನ ಗಾತ್ರಕ್ಕಿಂತ ಒಂದು ಕಡಿಮೆಯಾಗಿದೆ. ಈ ಗುಂಪಿನ ಗಾತ್ರವನ್ನು ಹೊಂದಿರುವ ಸ್ವರಮೇಳದ ರೇಖಾಚಿತ್ರವನ್ನು ಪ್ರತಿ ಎರಡು ಶೃಂಗಗಳ ನಡುವಿನ ಅಂಚಿಗೆ ಸೇರಿಸುವ ಮೂಲಕ ಪಡೆಯಬಹುದು, ಎರಡೂ ಕನಿಷ್ಠ ಒಂದು ಸೆಟ್ಗೆ ಸೇರಿವೆ. ಟ್ರೆವಿಡ್ತ್ ಅನ್ನು ಸ್ವರ್ಗಗಳ ದೃಷ್ಟಿಯಿಂದಲೂ ನಿರೂಪಿಸಬಹುದು, ಗ್ರಾಫ್ನಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ನಿರ್ದಿಷ್ಟ ಅನ್ವೇಷಣೆ-ತಪ್ಪಿಸಿಕೊಳ್ಳುವ ಆಟಕ್ಕೆ ತಪ್ಪಿಸಿಕೊಳ್ಳುವ ಕಾರ್ಯತಂತ್ರವನ್ನು ವಿವರಿಸುವ ಕಾರ್ಯಗಳು. ಒಂದು ರೇಖಾಚಿತ್ರವು ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿದ್ದರೆ ಮತ್ತು ಅದು ಕ್ರಮದ ಧಾಮವನ್ನು ಹೊಂದಿದ್ದರೆ ಆದರೆ ಹೆಚ್ಚಿನ ಕ್ರಮವನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ ಮಾತ್ರ, ಅಲ್ಲಿ ಕ್ರಮದ ಧಾಮವು ಪ್ರತಿಯೊಂದು ಶೃಂಗಗಳನ್ನು ಸಂಪರ್ಕಿತ ಘಟಕಗಳಲ್ಲಿ ಒಂದಾಗಿ ನಕ್ಷೆ ಮಾಡುವ ಮತ್ತು ಏಕತಾನತೆಯ ಗುಣಲಕ್ಷಣವನ್ನು ಪಾಲಿಸುವ ಕಾರ್ಯವಾಗಿದೆ. ಇದೇ ರೀತಿಯ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಬ್ರ್ಯಾಂಬಲ್ಗಳನ್ನು ಬಳಸಿ ಮಾಡಬಹುದು, ಸಂಪರ್ಕಿತ ಉಪಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳು ಎಲ್ಲರೂ ಪರಸ್ಪರ ಸ್ಪರ್ಶಿಸುತ್ತವೆ (ಅಂದರೆ ಅವು ಶೃಂಗವನ್ನು ಹಂಚಿಕೊಳ್ಳುತ್ತವೆ ಅಥವಾ ಅಂಚಿನಿಂದ ಸಂಪರ್ಕ ಹೊಂದಿವೆ). ಬ್ರ್ಯಾಂಬಲ್ನ ಕ್ರಮವು ಸಬ್ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಕ್ಕೆ ಚಿಕ್ಕ ಹೊಡೆತದ ಸೆಟ್ ಆಗಿದೆ, ಮತ್ತು ಗ್ರಾಫ್ನ ಮೂರು ಅಗಲವು ಬ್ರ್ಯಾಂಬಲ್ನ ಗರಿಷ್ಠ ಕ್ರಮಕ್ಕಿಂತ ಒಂದು ಕಡಿಮೆ. ಉದಾಹರಣೆಗಳು ಪ್ರತಿ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಸ್ವರಮೇಳದ ರೇಖಾಚಿತ್ರಗಳ ಪರಿಭಾಷೆಯಲ್ಲಿ ತ್ರಿ ಅಗಲದ ವ್ಯಾಖ್ಯಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಇದನ್ನು ಸುಲಭವಾಗಿ ಕಾಣಬಹುದುಃ ಸಂಪೂರ್ಣ ರೇಖಾಚಿತ್ರವು ಈಗಾಗಲೇ ಸ್ವರಮೇಳವಾಗಿದೆ, ಮತ್ತು ಹೆಚ್ಚಿನ ಅಂಚುಗಳನ್ನು ಸೇರಿಸುವುದರಿಂದ ಅದರ ಅತಿದೊಡ್ಡ ಗುಂಪಿನ ಗಾತ್ರವನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಸಾಧ್ಯವಿಲ್ಲ. ಕನಿಷ್ಠ ಎರಡು ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಸಂಪರ್ಕಿತ ರೇಖಾಚಿತ್ರವು ಮರವಾಗಿದ್ದರೆ ಮಾತ್ರ ಮೂರು ಅಗಲ 1 ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಂದು ಮರವು ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ಗಳಂತೆಯೇ ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿರುತ್ತದೆ (ಅಂದರೆ, ಇದು ಸ್ವರಮೇಳವಾಗಿದೆ ಮತ್ತು ಗರಿಷ್ಠ ಗುಂಪಿನ ಗಾತ್ರ ಎರಡನ್ನು ಹೊಂದಿರುತ್ತದೆ). ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ರೇಖಾಚಿತ್ರವು ಒಂದು ಚಕ್ರವನ್ನು ಹೊಂದಿದ್ದರೆ, ರೇಖಾಚಿತ್ರದ ಪ್ರತಿ ಸ್ವರಮೇಳದ ಪೂರ್ಣಗೊಳಿಸುವಿಕೆಯು ಚಕ್ರದ ಮೂರು ಸತತ ಶೃಂಗಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಕನಿಷ್ಠ ಒಂದು ತ್ರಿಕೋನವನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಅದರಿಂದ ಅದರ ಮೂರು ಅಗಲವು ಕನಿಷ್ಠ ಎರಡು ಆಗಿರುತ್ತದೆ. ಯಾವುದೇ ಸ್ಥಿರ ಸ್ಥಿರಾಂಕಕ್ಕೆ, ತ್ರಿ ಅಗಲದ ಗ್ರಾಫ್ಗಳನ್ನು ಗರಿಷ್ಠವಾಗಿ ಭಾಗಶಃ-ಮರಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಸೀಮಿತವಾದ ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳ ಇತರ ಕುಟುಂಬಗಳಲ್ಲಿ ಕ್ಯಾಕ್ಟಸ್ ಗ್ರಾಫ್ಗಳು, ಸೂಡೋಫಾರೆಸ್ಟ್ಗಳು, ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ಗಳು, ಹೊರ ಸಮತಲ ಗ್ರಾಫ್ಗಳು, ಹ್ಯಾಲಿನ್ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಅಪೋಲೋನಿಯನ್ ಜಾಲಗಳು ಸೇರಿವೆ. ರಚನಾತ್ಮಕ ಕಾರ್ಯಕ್ರಮಗಳ ಸಂಕಲನದಲ್ಲಿ ಉದ್ಭವಿಸುವ ನಿಯಂತ್ರಣ-ಹರಿವಿನ ಗ್ರಾಫ್ಗಳು ಮೂರು ಅಗಲವನ್ನು ಸಹ ಹೊಂದಿವೆ, ಇದು ರಿಜಿಸ್ಟರ್ ಹಂಚಿಕೆಯಂತಹ ಕೆಲವು ಕಾರ್ಯಗಳನ್ನು ಅವುಗಳ ಮೇಲೆ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ನಿರ್ವಹಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಸಮತಟ್ಟಾದ ನಕ್ಷೆಗಳು ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ, ಏಕೆಂದರೆ ಗ್ರಿಡ್ ನಕ್ಷೆಯು ನಿಖರವಾಗಿ ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿರುವ ಸಮತಟ್ಟಾದ ನಕ್ಷೆಯಾಗಿದೆ. ಆದ್ದರಿಂದ, ಸೀಮಿತ ತ್ರಿ ಅಗಲವನ್ನು ಹೊಂದಿರುವ ಸಣ್ಣ-ಮುಚ್ಚಿದ ಗ್ರಾಫ್ ಕುಟುಂಬವಾಗಿದ್ದರೆ, ಅದು ಎಲ್ಲಾ ಸಮತಟ್ಟಾದ ಗ್ರಾಫ್ಗಳನ್ನು ಒಳಗೊಂಡಿರುವುದಿಲ್ಲ. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ಕೆಲವು ಸಮತಟ್ಟಾದ ಗ್ರಾಫ್ಗಳು ಕುಟುಂಬದಲ್ಲಿನ ಗ್ರಾಫ್ಗಳಿಗೆ ಚಿಕ್ಕದಾಗಿ ಸಂಭವಿಸಲು ಸಾಧ್ಯವಾಗದಿದ್ದರೆ, ಎಲ್ಲಾ ಗ್ರಾಫ್ಗಳು ಗರಿಷ್ಠ ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿರುವಂತಹ ಸ್ಥಿರಾಂಕವಿರುತ್ತದೆ. ಅಂದರೆ, ಈ ಕೆಳಗಿನ ಮೂರು ಷರತ್ತುಗಳು ಒಂದಕ್ಕೊಂದು ಸಮಾನವಾಗಿವೆಃ ಇದು ಸೀಮಿತ-ತ್ರಿ-ಅಗಲದ ರೇಖಾಚಿತ್ರಗಳ ಸಣ್ಣ-ಮುಚ್ಚಿದ ಕುಟುಂಬವಾಗಿದೆ; ಸಮತಟ್ಟಾಗಿ ನಿರೂಪಿಸಲಾಗಿರುವ ಅನೇಕ ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರಲ್ಲಿ ಒಂದು ಸಮತಟ್ಟಾಗಿದೆ; ಇದು ಎಲ್ಲಾ ಸಮತಟ್ಟಾದ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಒಳಗೊಂಡಿರದ ಸಣ್ಣ-ಮುಚ್ಚಿದ ರೇಖಾಚಿತ್ರ ಕುಟುಂಬವಾಗಿದೆ. ಪ್ರತಿ ಸೀಮಿತ ಮೌಲ್ಯಕ್ಕೆ, ಗರಿಷ್ಠ ಮೂರು ಅಗಲದ ಗ್ರಾಫ್ಗಳನ್ನು ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಸೀಮಿತ ಗುಂಪಿನಿಂದ ನಿರೂಪಿಸಬಹುದು. (ಅಂದರೆ, ಮೂರು ಅಗಲದ ಯಾವುದೇ ಗ್ರಾಫ್ ಸಣ್ಣದಾಗಿರುವ ಗುಂಪಿನಲ್ಲಿನ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಒಂದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ.) ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಈ ಪ್ರತಿಯೊಂದು ಗುಂಪುಗಳು ಕನಿಷ್ಠ ಒಂದು ಸಮತಟ್ಟಾದ ನಕ್ಷೆಯನ್ನು ಒಳಗೊಂಡಿರುತ್ತವೆ. ಏಕೆಂದರೆ, ಅನನ್ಯ ನಿಷೇಧಿತ ಮೈನರ್ 3-ವೆರ್ಟೆಕ್ಸ್ ಸೈಕಲ್ ಗ್ರಾಫ್ ಆಗಿದೆ. ಏಕೆಂದರೆ, ಅನನ್ಯ ನಿಷೇಧಿತ ಮೈನರ್ 4-ವೆರ್ಟೆಕ್ಸ್ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ ಆಗಿದೆ. ಏಕೆಂದರೆ, ನಾಲ್ಕು ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತರು ಇದ್ದಾರೆಃ ಅಷ್ಟಭುಜಾಕೃತಿಯ ರೇಖಾಚಿತ್ರ, ಪಂಚಭುಜಾಕೃತಿಯ ಪ್ರಿಸ್ಮ್ ರೇಖಾಚಿತ್ರ ಮತ್ತು ವ್ಯಾಗ್ನರ್ ರೇಖಾಚಿತ್ರ. ಇವುಗಳಲ್ಲಿ, ಎರಡು ಪಾಲಿಹೆಡ್ರಲ್ ಗ್ರಾಫ್ಗಳು ಸಮತಟ್ಟಾಗಿವೆ. ದೊಡ್ಡ ಮೌಲ್ಯಗಳಿಗೆ, ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಸಂಖ್ಯೆಯು ಕನಿಷ್ಠ ವರ್ಗಮೂಲದ ಘಾತಾಂಕದಷ್ಟು ವೇಗವಾಗಿ ಬೆಳೆಯುತ್ತದೆ. ಆದಾಗ್ಯೂ, ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಗಾತ್ರ ಮತ್ತು ಸಂಖ್ಯೆಯ ಮೇಲೆ ತಿಳಿದಿರುವ ಮೇಲಿನ ಮಿತಿಗಳು ಈ ಕೆಳಗಿನ ಮಿತಿಗಿಂತ ತುಂಬಾ ಹೆಚ್ಚಾಗಿದೆ. ಕ್ರಮಾವಳಿಗಳು ಮೂರು ಅಗಲವನ್ನು ಗಣಿಸುವುದು ಒಂದು ನಿರ್ದಿಷ್ಟ ಗ್ರಾಫ್ ಒಂದು ನಿರ್ದಿಷ್ಟ ವೇರಿಯೇಬಲ್ನಲ್ಲಿ ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸಲು ಇದು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿದೆ. ಆದಾಗ್ಯೂ, ಯಾವುದೇ ಸ್ಥಿರ ಸ್ಥಿರಾಂಕವು ಯಾವಾಗ, ತ್ರಿ ಅಗಲವನ್ನು ಹೊಂದಿರುವ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಗುರುತಿಸಬಹುದು, ಮತ್ತು ಅವುಗಳಿಗಾಗಿ ಒಂದು ಅಗಲದ ಮರದ ವಿಭಜನೆಯನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ನಿರ್ಮಿಸಬಹುದು. ಈ ಅಲ್ಗಾರಿದಮ್ನ ಸಮಯ ಅವಲಂಬನೆಯು ಘಾತೀಯವಾಗಿದೆ. ಅಗಾಧ ಸಂಖ್ಯೆಯ ಕ್ಷೇತ್ರಗಳಲ್ಲಿ ತ್ರಿ ಅಗಲವು ವಹಿಸುವ ಪಾತ್ರಗಳಿಂದಾಗಿ, ಗ್ರಾಫ್ನ ತ್ರಿ ಅಗಲವನ್ನು ಗಣಿಸುವ ವಿಭಿನ್ನ ಪ್ರಾಯೋಗಿಕ ಮತ್ತು ಸೈದ್ಧಾಂತಿಕ ಕ್ರಮಾವಳಿಗಳನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಲಾಯಿತು. ಕೈಯಲ್ಲಿರುವ ಅಪ್ಲಿಕೇಶನ್ ಅನ್ನು ಅವಲಂಬಿಸಿ, ಒಬ್ಬರು ಉತ್ತಮ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಅಥವಾ ಇನ್ಪುಟ್ನ ಗಾತ್ರ ಅಥವಾ ಮೂರು ಅಗಲದಿಂದ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯದಲ್ಲಿ ಉತ್ತಮ ಅವಲಂಬನೆಯನ್ನು ಆದ್ಯತೆ ನೀಡಬಹುದು. ಕೆಳಗಿನ ಕೋಷ್ಟಕವು ಕೆಲವು ತ್ರಿ-ಅಗಲ ಕ್ರಮಾವಳಿಗಳ ಅವಲೋಕನವನ್ನು ಒದಗಿಸುತ್ತದೆ. ಇಲ್ಲಿ ಮೂರು ಅಗಲವಿದೆ ಮತ್ತು ಇದು ಇನ್ಪುಟ್ ಗ್ರಾಫ್ನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಪ್ರತಿಯೊಂದು ಕ್ರಮಾವಳಿಗಳು ಅಪ್ರಾಕ್ಸಿಮೇಷನ್ ಕಾಲಮ್ನಲ್ಲಿ ನೀಡಲಾದ ಅಗಲದ ವಿಭಜನೆಯನ್ನು ಸಮಯಕ್ಕೆ ಔಟ್ಪುಟ್ ಮಾಡುತ್ತವೆ. ಉದಾಹರಣೆಗೆ, ಇನ್ ಟೈಮ್ ಅಲ್ಗಾರಿದಮ್ ಗರಿಷ್ಠ ಅಗಲದ ಇನ್ಪುಟ್ ಗ್ರಾಫ್ನ ಮರದ ವಿಭಜನೆಯನ್ನು ನಿರ್ಮಿಸುತ್ತದೆ ಅಥವಾ ತ್ರಿ ಅಗಲವು ಇದಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿದೆ ಎಂದು ವರದಿ ಮಾಡುತ್ತದೆ. ಅಂತೆಯೇ, ಇನ್ ಟೈಮ್ ಅಲ್ಗಾರಿದಮ್ ಗರಿಷ್ಠ ಅಗಲದ ಇನ್ಪುಟ್ ಗ್ರಾಫ್ನ ಮರದ ವಿಭಜನೆಯನ್ನು ನಿರ್ಮಿಸುತ್ತದೆ ಅಥವಾ ತ್ರಿ ಅಗಲವು ಇದಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿದೆ ಎಂದು ವರದಿ ಮಾಡುತ್ತದೆ. ಇದನ್ನು ಅದೇ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯಕ್ಕೆ ಸುಧಾರಿಸಲಾಗಿದೆ. ಸಮತಟ್ಟಾದ ನಕ್ಷೆಗಳ ತ್ರಿ-ಅಗಲವನ್ನು ನಿರ್ಧರಿಸುವುದು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿದೆಯೇ ಅಥವಾ ಅವುಗಳ ತ್ರಿ-ಅಗಲವನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದೇ ಎಂಬುದು ತಿಳಿದಿಲ್ಲ. ಪ್ರಾಯೋಗಿಕವಾಗಿ, ಒಂದು ಅಲ್ಗಾರಿದಮ್ 100 ಶೃಂಗಗಳವರೆಗಿನ ಗ್ರಾಫ್ಗಳ ಮೂರು ಅಗಲವನ್ನು ಮತ್ತು 11ರವರೆಗಿನ ಮೂರು ಅಗಲವನ್ನು ನಿರ್ಧರಿಸುತ್ತದೆ, ಈ ಗ್ರಾಫ್ಗಳ ಸ್ವರಮೇಳದ ಪೂರ್ಣಗೊಳಿಸುವಿಕೆಯನ್ನು ಅತ್ಯುತ್ತಮ ಮೂರು ಅಗಲದೊಂದಿಗೆ ಕಂಡುಹಿಡಿಯುತ್ತದೆ. ದೊಡ್ಡ ಗ್ರಾಫ್ಗಳಿಗಾಗಿ, ಮೂರು ಅಗಲವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಶಾಖೆ ಮತ್ತು ಬೌಂಡ್ ಸರ್ಚ್ (ಬಿಎನ್ಬಿ) ಮತ್ತು ಅತ್ಯುತ್ತಮ-ಮೊದಲ ಹುಡುಕಾಟದಂತಹ ಹುಡುಕಾಟ-ಆಧಾರಿತ ತಂತ್ರಗಳನ್ನು ಬಳಸಬಹುದು. ಈ ಕ್ರಮಾವಳಿಗಳು ಯಾವ ಸಮಯದಲ್ಲಾದರೂ ಇರುತ್ತವೆ, ಮುಂಚಿತವಾಗಿ ನಿಲ್ಲಿಸಿದಾಗ, ಅವು ಮೂರು ಅಗಲದ ಮೇಲೆ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಉತ್ಪಾದಿಸುತ್ತವೆ. ಕ್ವಿಕ್ಬಿಬಿ ಅಲ್ಗಾರಿದಮ್ ಎಂದು ಕರೆಯಲಾಗುವ ಮೂರು ಅಗಲದ ಗಣನೆಯ ಮೊದಲ ಬಿಎನ್ಬಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಗೊಗೇಟ್ ಮತ್ತು ಡೆಚ್ಟರ್ ಪ್ರಸ್ತಾಪಿಸಿದರು. ಯಾವುದೇ ಬಿಎನ್ಬಿ ಅಲ್ಗಾರಿದಮ್ನ ಗುಣಮಟ್ಟವು ಬಳಸಿದ ಲೋವರ್ ಬೌಂಡ್ನ ಗುಣಮಟ್ಟದ ಮೇಲೆ ಹೆಚ್ಚು ಅವಲಂಬಿತವಾಗಿರುವುದರಿಂದ, ಗೊಗೇಟ್ ಮತ್ತು ಡೆಚ್ಟರ್ ಅವರು ಮೈನರ್-ಮಿನ್-ವಿಡ್ತ್ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಮೂರು-ಅಗಲದ ಮೇಲೆ ಲೋವರ್-ಬೌಂಡ್ ಅನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಹೊಸ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತಾಪಿಸಿದರು. ಉನ್ನತ ಮಟ್ಟದಲ್ಲಿ, ಮೈನರ್-ಮಿನ್-ವಿಡ್ತ್ ಅಲ್ಗಾರಿದಮ್ ಒಂದು ಗ್ರಾಫ್ನ ಮೂರು ಅಗಲವು ಅದರ ಕನಿಷ್ಠ ಡಿಗ್ರಿಗಿಂತ ಎಂದಿಗೂ ದೊಡ್ಡದಾಗಿರುವುದಿಲ್ಲ ಅಥವಾ ಮೂರು ಅಗಲದ ಮೇಲೆ ಕಡಿಮೆ ಮಿತಿಯನ್ನು ನೀಡಲು ಚಿಕ್ಕದಾಗಿರುವುದಿಲ್ಲ ಎಂಬ ಸಂಗತಿಗಳನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ. ಮೈನರ್-ಮಿನ್-ವಿಡ್ತ್ ಅಲ್ಗಾರಿದಮ್ ಕನಿಷ್ಠ ಡಿಗ್ರಿ ಶೃಂಗ ಮತ್ತು ಅದರ ನೆರೆಹೊರೆಯವರ ನಡುವಿನ ಅಂಚನ್ನು ಸಂಕುಚಿತಗೊಳಿಸುವ ಮೂಲಕ ಕೇವಲ ಒಂದು ಶೃಂಗವು ಉಳಿದಿರುವವರೆಗೆ ಗ್ರಾಫ್ ಮೈನರ್ ಅನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ನಿರ್ಮಿಸುತ್ತದೆ. ಈ ನಿರ್ಮಿಸಲಾದ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಮೇಲೆ ಗರಿಷ್ಠ ಕನಿಷ್ಠ ಮಟ್ಟವು ಗ್ರಾಫ್ನ ಮೂರು ಅಗಲದ ಮೇಲೆ ಕಡಿಮೆ ಮಿತಿಯಾಗಿರುತ್ತದೆ ಎಂದು ಖಾತರಿಪಡಿಸಲಾಗಿದೆ. ಡೌ ಮತ್ತು ಕಾರ್ಫ್ ಬೆಸ್ಟ್-ಫಸ್ಟ್ ಸರ್ಚ್ ಅನ್ನು ಬಳಸಿಕೊಂಡು ಕ್ವಿಕ್ಬಿಬಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸುಧಾರಿಸಿದರು. ಕೆಲವು ಗ್ರಾಫ್ಗಳಲ್ಲಿ, ಈ ಅತ್ಯುತ್ತಮ-ಮೊದಲ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಕ್ವಿಕ್ಬಿಬಿಗಿಂತ ವೇಗವಾಗಿ ಪರಿಮಾಣದ ಕ್ರಮವಾಗಿದೆ. ಸಣ್ಣ ಮೂರು ಅಗಲದ ಗ್ರಾಫ್ಗಳ ಮೇಲೆ ಇತರ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸುವುದು 1970 ರ ದಶಕದ ಆರಂಭದಲ್ಲಿ, ಗ್ರಾಫ್ಗಳಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ದೊಡ್ಡ ವರ್ಗದ ಸಂಯೋಜಿತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳನ್ನು ನಾನ್ ಸೀರಿಯಲ್ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಮೂಲಕ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪರಿಹರಿಸಬಹುದು ಎಂದು ಗಮನಿಸಲಾಯಿತು. ನಂತರ, 1980 ರ ದಶಕದ ಕೊನೆಯಲ್ಲಿ ಹಲವಾರು ಲೇಖಕರು ಸ್ವತಂತ್ರವಾಗಿ ಗಮನಿಸಿದರು, ಅನಿಯಂತ್ರಿತ ಗ್ರಾಫ್ಗಳಿಗೆ ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿರುವ ಅನೇಕ ಅಲ್ಗಾರಿದಮಿಕ್ ಸಮಸ್ಯೆಗಳನ್ನು ಈ ಗ್ರಾಫ್ಗಳ ಟ್ರೀ-ಡೀಕಂಪೊಸಿಷನ್ಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಬೌಂಡೆಡ್ ಟ್ರೈವಿಡ್ತ್ನ ಗ್ರಾಫ್ಗಳಿಗೆ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಮೂಲಕ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪರಿಹರಿಸಬಹುದು. ಉದಾಹರಣೆಗೆ, ತ್ರಿ ಅಗಲದ ಗ್ರಾಫ್ಗೆ ಬಣ್ಣ ಹಾಕುವ ಸಮಸ್ಯೆಯನ್ನು ಗ್ರಾಫ್ನ ಮರದ ವಿಭಜನೆಯ ಮೇಲೆ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸುವ ಮೂಲಕ ಪರಿಹರಿಸಬಹುದು. ಮರದ ಕೊಳೆಯುವಿಕೆಯ ಪ್ರತಿಯೊಂದು ಗುಂಪಿಗೆ, ಮತ್ತು ಬಣ್ಣದ ವರ್ಗಗಳಾಗಿ ಅದರ ಶೃಂಗಗಳ ಪ್ರತಿಯೊಂದು ವಿಭಜನೆಗೆ, ಆ ಬಣ್ಣವು ಮಾನ್ಯವಾಗಿದೆಯೇ ಎಂಬುದನ್ನು ಅಲ್ಗಾರಿದಮ್ ನಿರ್ಧರಿಸುತ್ತದೆ ಮತ್ತು ಮರದ ಕೊಳೆಯುವಿಕೆಯಲ್ಲಿನ ಎಲ್ಲಾ ವಂಶಸ್ಥ ನೋಡ್ಗಳಿಗೆ ವಿಸ್ತರಿಸಬಹುದು, ಅದೇ ರೀತಿಯ ಮಾಹಿತಿಯನ್ನು ಒಟ್ಟುಗೂಡಿಸಿ ಆ ನೋಡ್ಗಳಲ್ಲಿ ಸಂಗ್ರಹಿಸಲಾಗುತ್ತದೆ. ಪರಿಣಾಮವಾಗಿ ಬರುವ ಅಲ್ಗಾರಿದಮ್ ಸಮಯದೊಳಗೆ-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ನ ಅತ್ಯುತ್ತಮ ಬಣ್ಣವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ, ಇದು ಈ ಸಮಸ್ಯೆಯನ್ನು ಸ್ಥಿರ-ನಿಯತಾಂಕದ ಮೂಲಕ ಪರಿಹರಿಸಬಹುದಾದ ಸಮಯದ ಮಿತಿಯಾಗಿದೆ. ಒಂದು ದೊಡ್ಡ ವರ್ಗದ ಸಮಸ್ಯೆಗಳಿಗೆ, ಸ್ಥಿರವಾದ ತ್ರಿ-ಅಗಲವನ್ನು ಹೊಂದಿರುವ ಮರದ-ವಿಭಜನೆಯನ್ನು ಒದಗಿಸಿದರೆ ವರ್ಗದಿಂದ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ರೇಖೀಯ ಸಮಯದ ಕ್ರಮಾವಳಿ ಇರುತ್ತದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಮೊನಾಡಿಕ್ ಸೆಕೆಂಡ್ ಆರ್ಡರ್ ತರ್ಕವನ್ನು ಬಳಸಿಕೊಂಡು ಗ್ರಾಫ್ಗಳ ತರ್ಕದಲ್ಲಿ ಗ್ರಾಫ್ ಸಮಸ್ಯೆಯನ್ನು ವ್ಯಕ್ತಪಡಿಸಬಹುದಾದರೆ, ಅದನ್ನು ರೇಖಾತ್ಮಕ ಸಮಯದಲ್ಲಿ ರೇಖಾಗಣಿತದ ಮೂರು ಅಗಲದೊಂದಿಗೆ ಪರಿಹರಿಸಬಹುದು ಎಂದು ಕೊರ್ಸೆಲ್ನ ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ. ಮೊನಾಡಿಕ್ ಸೆಕೆಂಡ್ ಆರ್ಡರ್ ಲಾಜಿಕ್ ಈ ಕೆಳಗಿನ ರಚನೆಗಳನ್ನು ಬಳಸುವ ಗ್ರಾಫ್ ಗುಣಲಕ್ಷಣಗಳನ್ನು ವಿವರಿಸುವ ಭಾಷೆಯಾಗಿದೆಃ ಸದಸ್ಯತ್ವ ಪರೀಕ್ಷೆಗಳಂತಹ ಲಾಜಿಕ್ ಕಾರ್ಯಾಚರಣೆಗಳು, ಉದಾಹರಣೆಗೆ, ಶೃಂಗಗಳು, ಅಂಚುಗಳು, ಶೃಂಗಗಳ ಸೆಟ್ಗಳು, ಮತ್ತು/ಅಥವಾ ಅಂಚುಗಳ ಸೆಟ್ಗಳು, ಉದಾಹರಣೆಗೆ,,, ಅಡ್ಜಸೆನ್ಸಿ ಪರೀಕ್ಷೆಗಳು (ಒಂದು ಅಂತಿಮ ಬಿಂದುವಾಗಿದೆ), ಮತ್ತು ಆಪ್ಟಿಮೈಸೇಶನ್ನಂತಹ ವಿಷಯಗಳನ್ನು ಅನುಮತಿಸುವ ಕೆಲವು ವಿಸ್ತರಣೆಗಳು. ಉದಾಹರಣೆಗೆ ರೇಖಾಚಿತ್ರಗಳ 3-ಬಣ್ಣದ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಗಣಿಸಿ. ಗ್ರಾಫ್ಗಾಗಿ, ಈ ಸಮಸ್ಯೆಯು ಪ್ರತಿ ಶೃಂಗವನ್ನು 3 ಬಣ್ಣಗಳಲ್ಲಿ ಒಂದನ್ನು ನಿಯೋಜಿಸಲು ಸಾಧ್ಯವೇ ಎಂದು ಕೇಳುತ್ತದೆ, ಅಂದರೆ ಯಾವುದೇ ಎರಡು ಪಕ್ಕದ ಶೃಂಗಗಳಿಗೆ ಒಂದೇ ಬಣ್ಣವನ್ನು ನಿಗದಿಪಡಿಸಲಾಗುವುದಿಲ್ಲ. ಈ ಸಮಸ್ಯೆಯನ್ನು ಮೊನಾಡಿಕ್ ಸೆಕೆಂಡ್ ಆರ್ಡರ್ ತರ್ಕದಲ್ಲಿ ಈ ಕೆಳಗಿನಂತೆ ವ್ಯಕ್ತಪಡಿಸಬಹುದುಃ, ಅಲ್ಲಿ, 3 ಬಣ್ಣಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದನ್ನು ಹೊಂದಿರುವ ಶೃಂಗಗಳ ಉಪಗುಂಪುಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, ಕೊರ್ಸೆಲ್ನ ಫಲಿತಾಂಶಗಳಿಂದ, 3-ಬಣ್ಣದ ಸಮಸ್ಯೆಯನ್ನು ರೇಖಾಗಣಿತಕ್ಕೆ ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು, ಇದು ನಿರ್ಬಂಧಿತ ಸ್ಥಿರವಾದ ಮೂರು ಅಗಲದ ಮರ-ವಿಭಜನೆಯನ್ನು ನೀಡುತ್ತದೆ. ಸಂಬಂಧಿತ ನಿಯತಾಂಕಗಳು ಪಥದ ಅಗಲ ಗ್ರಾಫ್ನ ಪಥದ ಅಗಲವು ಮರದ ವಿಭಜನೆಗಳ ಮೂಲಕ ಮೂರು ಅಗಲಕ್ಕೆ ಹೋಲುವ ವ್ಯಾಖ್ಯಾನವನ್ನು ಹೊಂದಿದೆ, ಆದರೆ ಇದು ಮರದ ವಿಭಜನೆಗಳಿಗೆ ಸೀಮಿತವಾಗಿದೆ, ಇದರಲ್ಲಿ ವಿಭಜನೆಯ ಆಧಾರವಾಗಿರುವ ಮರವು ಪಥದ ಗ್ರಾಫ್ ಆಗಿದೆ. ಪರ್ಯಾಯವಾಗಿ, ಪಥದ ಅಗಲವನ್ನು ಮಧ್ಯಂತರದ ರೇಖಾಚಿತ್ರಗಳಿಂದ ಸ್ವರಮೇಳದ ರೇಖಾಚಿತ್ರಗಳಿಂದ ಮೂರು ಅಗಲದ ವ್ಯಾಖ್ಯಾನಕ್ಕೆ ಹೋಲುವಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. ಇದರ ಪರಿಣಾಮವಾಗಿ, ರೇಖಾಚಿತ್ರದ ಪಥದ ಅಗಲವು ಯಾವಾಗಲೂ ಅದರ ಮೂರು ಅಗಲದಷ್ಟು ದೊಡ್ಡದಾಗಿರುತ್ತದೆ, ಆದರೆ ಅದು ಲಾಗರಿದಮಿಕ್ ಅಂಶದಿಂದ ಮಾತ್ರ ದೊಡ್ಡದಾಗಿರಬಹುದು. ಗ್ರಾಫ್ ಬ್ಯಾಂಡ್ವಿಡ್ತ್ ಎಂಬ ಮತ್ತೊಂದು ನಿಯತಾಂಕವು ಸರಿಯಾದ ಮಧ್ಯಂತರ ಗ್ರಾಫ್ಗಳಿಂದ ಹೋಲುವ ವ್ಯಾಖ್ಯಾನವನ್ನು ಹೊಂದಿದೆ ಮತ್ತು ಕನಿಷ್ಠ ಪಥದ ಅಗಲದಷ್ಟು ದೊಡ್ಡದಾಗಿದೆ. ಇತರ ಸಂಬಂಧಿತ ನಿಯತಾಂಕಗಳಲ್ಲಿ ಟ್ರೀ-ಡೆಪ್ತ್, ಕುಟುಂಬವು ಒಂದು ಮಾರ್ಗವನ್ನು ಹೊರತುಪಡಿಸಿದರೆ ಮಾತ್ರ ಸಣ್ಣ-ಮುಚ್ಚಿದ ಗ್ರಾಫ್ ಕುಟುಂಬಕ್ಕೆ ಸೀಮಿತವಾಗಿರುವ ಸಂಖ್ಯೆ, ಮತ್ತು ಅವನತಿಯು, ಅದರ ಮೂರು ಅಗಲಕ್ಕೆ ಸಮಾನವಾದ ಗ್ರಾಫ್ನ ವಿರಾಮದ ಅಳತೆಯಾಗಿದೆ. ಗ್ರಿಡ್ ಸಣ್ಣ ಗಾತ್ರ ಗ್ರಿಡ್ ಗ್ರಾಫ್ನ ಮೂರು ಅಗಲವಾಗಿರುವುದರಿಂದ, ಗ್ರಾಫ್ನ ಮೂರು ಅಗಲವು ಯಾವಾಗಲೂ ಚಿಕ್ಕದಾದ ಅತಿದೊಡ್ಡ ಚದರ ಗ್ರಿಡ್ನ ಗಾತ್ರಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ ಅಥವಾ ಸಮನಾಗಿರುತ್ತದೆ. ಇನ್ನೊಂದು ದಿಕ್ಕಿನಲ್ಲಿ, ರಾಬರ್ಟ್ಸನ್ ಮತ್ತು ಸೆಮೌರ್ ಅವರ ಗ್ರಿಡ್ ಮೈನರ್ ಪ್ರಮೇಯವು ಅತಿದೊಡ್ಡ ಚೌಕಾಕಾರದ ಗ್ರಿಡ್ ಮೈನರ್ ಕನಿಷ್ಠ ಮೂರು ಅಗಲವಿರುವ ಸ್ಥಳದ ಗಾತ್ರವನ್ನು ಹೊಂದಿರುವಂತಹ ಮಿತಿಯಿಲ್ಲದ ಕಾರ್ಯವಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ. ತಿಳಿದಿರುವ ಅತ್ಯುತ್ತಮ ಮಿತಿಗಳು ಕನಿಷ್ಠ ಕೆಲವು ಸ್ಥಿರ ಸ್ಥಿರಾಂಕಗಳಾಗಿರಬೇಕು, ಮತ್ತು ಗರಿಷ್ಠವಾಗಿ ಕೆಳಗಿನ ಮಿತಿಯಲ್ಲಿನ ಸಂಕೇತಕ್ಕಾಗಿ, ದೊಡ್ಡ O ಸಂಕೇತವನ್ನು ನೋಡಿ. ಬಿಗಿಯಾದ ಮಿತಿಗಳು ನಿರ್ಬಂಧಿತ ಗ್ರಾಫ್ ಕುಟುಂಬಗಳಿಗೆ ಹೆಸರುವಾಸಿಯಾಗಿವೆ, ಇದು ದ್ವಿ-ಆಯಾಮದ ಸಿದ್ಧಾಂತದ ಮೂಲಕ ಆ ಕುಟುಂಬಗಳ ಮೇಲೆ ಅನೇಕ ಗ್ರಾಫ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳಿಗೆ ಪರಿಣಾಮಕಾರಿ ಕ್ರಮಾವಳಿಗಳಿಗೆ ಕಾರಣವಾಗುತ್ತದೆ. ಹ್ಯಾಲಿನ್ರ ಗ್ರಿಡ್ ಪ್ರಮೇಯವು ಅನಂತ ಗ್ರಾಫ್ಗಳಿಗೆ ತ್ರಿ ಅಗಲ ಮತ್ತು ಗ್ರಿಡ್ ಸಣ್ಣ ಗಾತ್ರದ ನಡುವಿನ ಸಂಬಂಧದ ಸಾದೃಶ್ಯವನ್ನು ಒದಗಿಸುತ್ತದೆ. ವ್ಯಾಸ ಮತ್ತು ಸ್ಥಳೀಯ ಮೂರು ಅಗಲ ಉಪ ರೇಖಾಚಿತ್ರಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಅಡಿಯಲ್ಲಿ ಮುಚ್ಚಿದ ರೇಖಾಚಿತ್ರಗಳ ಒಂದು ಕುಟುಂಬವು ಸ್ಥಳೀಯ ಮೂರು ಅಗಲ ಅಥವಾ ವ್ಯಾಸ-ಮೂರು ಅಗಲದ ಗುಣಲಕ್ಷಣವನ್ನು ಸುತ್ತುವರೆದಿದೆ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ, ಕುಟುಂಬದಲ್ಲಿನ ರೇಖಾಚಿತ್ರಗಳ ಮೂರು ಅಗಲವು ಅವುಗಳ ವ್ಯಾಸದ ಕಾರ್ಯದಿಂದ ಸುತ್ತುವರೆದಿದ್ದರೆ. ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ ವರ್ಗವನ್ನು ಮುಚ್ಚಲಾಗಿದೆ ಎಂದು ಭಾವಿಸಿದರೆ, ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರಲ್ಲಿ ಒಬ್ಬರು ಅಪೆಕ್ಸ್ ಗ್ರಾಫ್ ಆಗಿದ್ದರೆ ಮಾತ್ರ ಸ್ಥಳೀಯ ಮೂರು ಅಗಲವನ್ನು ನಿರ್ಬಂಧಿಸಲಾಗಿದೆ. ಈ ಫಲಿತಾಂಶದ ಮೂಲ ಪುರಾವೆಗಳು ಎಪೆಕ್ಸ್-ಮೈನರ್-ಫ್ರೀ ಗ್ರಾಫ್ ಕುಟುಂಬದಲ್ಲಿ ತ್ರಿ ಅಗಲವು ವ್ಯಾಸದ ಕಾರ್ಯವಾಗಿ ಗರಿಷ್ಠ ದ್ವಿಗುಣವಾಗಿ ಘಾತೀಯವಾಗಿ ಬೆಳೆಯುತ್ತದೆ ಎಂದು ತೋರಿಸಿದೆ; ನಂತರ ಇದನ್ನು ಏಕ ಘಾತೀಯ ಮತ್ತು ಅಂತಿಮವಾಗಿ ರೇಖೀಯ ಬಂಧಕ್ಕೆ ಇಳಿಸಲಾಯಿತು. ಬೌಂಡೆಡ್ ಲೋಕಲ್ ಟ್ರೈವಿಡ್ತ್ ದ್ವಿ-ಆಯಾಮದ ಅಲ್ಗಾರಿದಮಿಕ್ ಸಿದ್ಧಾಂತಕ್ಕೆ ನಿಕಟ ಸಂಬಂಧವನ್ನು ಹೊಂದಿದೆ, ಮತ್ತು ಮೊದಲ ಕ್ರಮಾಂಕದ ತರ್ಕದಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದಾದ ಪ್ರತಿ ಗ್ರಾಫ್ ಗುಣಲಕ್ಷಣವನ್ನು ತುದಿ-ಚಿಕ್ಕ-ಮುಕ್ತ ಗ್ರಾಫ್ ಕುಟುಂಬಕ್ಕೆ ಸ್ವಲ್ಪವೇ ಸೂಪರ್ಲೀನಿಯರ್ ಆಗಿರುವ ಸಮಯದಲ್ಲಿ ನಿರ್ಧರಿಸಬಹುದು. ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಅಡಿಯಲ್ಲಿ ಮುಚ್ಚಿರದ ಗ್ರಾಫ್ಗಳ ಒಂದು ವರ್ಗವು ಸ್ಥಳೀಯ ಮೂರು ಅಗಲವನ್ನು ಹೊಂದಲು ಸಹ ಸಾಧ್ಯವಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಇದು ಮಿತಿಯಿರುವ ಡಿಗ್ರಿ ಗ್ರಾಫ್ಗಳ ವರ್ಗಕ್ಕೆ ಕ್ಷುಲ್ಲಕವಾಗಿ ನಿಜವಾಗಿದೆ, ಏಕೆಂದರೆ ಸೀಮಿತ ವ್ಯಾಸದ ಉಪಗ್ರಾಫ್ಗಳು ಸೀಮಿತ ಗಾತ್ರವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಮತ್ತೊಂದು ಉದಾಹರಣೆಯನ್ನು 1-ಸಮತಲೀಯ ರೇಖಾಚಿತ್ರಗಳಿಂದ ನೀಡಲಾಗುತ್ತದೆ, ಪ್ರತಿ ಅಂಚಿಗೆ ಒಂದು ದಾಟುವಿಕೆಯೊಂದಿಗೆ ಸಮತಲದಲ್ಲಿ ಚಿತ್ರಿಸಬಹುದಾದ ರೇಖಾಚಿತ್ರಗಳು, ಮತ್ತು ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ ಪ್ರತಿ ಅಂಚಿಗೆ ಸೀಮಿತ ಸಂಖ್ಯೆಯ ದಾಟುವಿಕೆಯೊಂದಿಗೆ ಸುತ್ತುವರಿದ ಕುಲದ ಮೇಲ್ಮೈಯಲ್ಲಿ ಚಿತ್ರಿಸಬಹುದಾದ ರೇಖಾಚಿತ್ರಗಳಿಗೆ. ಸೀಮಿತ ಸ್ಥಳೀಯ ಮೂರು ಅಗಲದ ಸಣ್ಣ-ಮುಚ್ಚಿದ ಗ್ರಾಫ್ ಕುಟುಂಬಗಳಂತೆ, ಈ ಗುಣಲಕ್ಷಣವು ಈ ಗ್ರಾಫ್ಗಳಿಗೆ ಪರಿಣಾಮಕಾರಿ ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳಿಗೆ ದಾರಿ ತೋರಿಸಿದೆ. ಹ್ಯಾಡ್ವಿಗರ್ ಸಂಖ್ಯೆ ಮತ್ತು ಎಸ್-ಕಾರ್ಯಗಳು ಅವರು ಕರೆಯುವ ಗ್ರಾಫ್ ನಿಯತಾಂಕಗಳ ವರ್ಗವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತವೆ-ಕಾರ್ಯಗಳು, ಇದರಲ್ಲಿ ತ್ರಿ ಅಗಲವೂ ಸೇರಿದೆ. ಗ್ರಾಫ್ಗಳಿಂದ ಪೂರ್ಣಾಂಕಗಳವರೆಗಿನ ಈ ಕಾರ್ಯಗಳು ಯಾವುದೇ ಅಂಚುಗಳಿಲ್ಲದ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಶೂನ್ಯವಾಗಿರಬೇಕು, ಮೈನರ್-ಮೊನೊಟೋನ್ ಆಗಿರಬೇಕು (ಒಂದು ಕಾರ್ಯವನ್ನು "ಮೈನರ್-ಮೊನೊಟೋನ್" ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಅದು ಚಿಕ್ಕದಾದಾಗಲೆಲ್ಲಾ, ಒಂದನ್ನು ಹೊಂದಿರುತ್ತದೆ), ಹೊಸ ಶೃಂಗವನ್ನು ಸೇರಿಸಿದಾಗ ಒಂದನ್ನು ಹೆಚ್ಚಿಸುವುದು ಹಿಂದಿನ ಎಲ್ಲಾ ಶೃಂಗಗಳ ಪಕ್ಕದಲ್ಲಿದೆ, ಮತ್ತು ಎರಡು ಉಪಗ್ರಾಫ್ಗಳಿಂದ ದೊಡ್ಡ ಮೌಲ್ಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳಲು ಒಂದು ಗುಂಪು ವಿಭಜಕದ ಎರಡೂ ಬದಿಗಳು. ಅಂತಹ ಎಲ್ಲಾ ಕಾರ್ಯಗಳ ಸಮೂಹವು ಅಂಶವಾರು ಕನಿಷ್ಠೀಕರಣ ಮತ್ತು ಗರಿಷ್ಠೀಕರಣದ ಕಾರ್ಯಾಚರಣೆಗಳ ಅಡಿಯಲ್ಲಿ ಸಂಪೂರ್ಣ ಜಾಲರಿಯನ್ನು ರೂಪಿಸುತ್ತದೆ. ಈ ಜಾಲರಿಯಲ್ಲಿನ ಮೇಲಿನ ಅಂಶವು ಮೂರು ಅಗಲವಾಗಿದೆ, ಮತ್ತು ಕೆಳಗಿನ ಅಂಶವು ಹ್ಯಾಡ್ವಿಗರ್ ಸಂಖ್ಯೆಯಾಗಿದೆ, ಇದು ನೀಡಲಾದ ಗ್ರಾಫ್ನಲ್ಲಿನ ಅತಿದೊಡ್ಡ ಸಂಪೂರ್ಣ ಮೈನರ್ನ ಗಾತ್ರವಾಗಿದೆ. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ಗ್ರಾಫ್ ಇನ್ವೇರಿಯಂಟ್ಸ್ ಗ್ರಾಫ್ ಸಣ್ಣ ಸಿದ್ಧಾಂತ