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