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