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