Colour refinement algorithm
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಮತ್ತು ಸೈದ್ಧಾಂತಿಕ ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ನೈವ್ ವರ್ಟೆಕ್ಸ್ ವರ್ಗೀಕರಣ ಎಂದೂ ಕರೆಯಲ್ಪಡುವ ಬಣ್ಣ ಪರಿಷ್ಕರಣೆ ಅಲ್ಗಾರಿದಮ್, ಅಥವಾ ವೈಸ್ಫೀಲರ್-ಲೆಮನ್ ಅಲ್ಗಾರಿದಮ್ನ 1-ಆಯಾಮದ ಆವೃತ್ತಿಯು, ಎರಡು ಗ್ರಾಫ್ಗಳು ಐಸೊಮಾರ್ಫಿಕ್ ಆಗಿವೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಪರೀಕ್ಷಿಸಲು ಬಳಸುವ ವಾಡಿಕೆಯಾಗಿದೆ. ಇತಿಹಾಸದ ವಿವರಣೆ ನಾವು ಶೃಂಗದ ಬಣ್ಣಗಳ ಅನುಕ್ರಮವನ್ನು ಈ ಕೆಳಗಿನಂತೆ ವ್ಯಾಖ್ಯಾನಿಸುತ್ತೇವೆಃ ಇದು ಆರಂಭಿಕ ಬಣ್ಣವಾಗಿದೆ. ಗ್ರಾಫ್ ಅನ್ನು ಲೇಬಲ್ ಮಾಡದಿದ್ದರೆ, ಆರಂಭಿಕ ಬಣ್ಣವು ಪ್ರತಿ ಶೃಂಗಕ್ಕೂ ಕ್ಷುಲ್ಲಕ ಬಣ್ಣವನ್ನು ನಿಗದಿಪಡಿಸುತ್ತದೆ. ಗ್ರಾಫ್ ಅನ್ನು ಲೇಬಲ್ ಮಾಡಿದರೆ, ಅದು ಶೃಂಗದ ಲೇಬಲ್ ಆಗಿರುತ್ತದೆ. ಎಲ್ಲಾ ಶೃಂಗಗಳಿಗೆ, ನಾವು ಹೊಂದಿಸುತ್ತೇವೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಶೃಂಗದ ಹೊಸ ಬಣ್ಣವು ಹಿಂದಿನ ಬಣ್ಣದಿಂದ ರೂಪುಗೊಂಡ ಜೋಡಿ ಮತ್ತು ಅದರ ನೆರೆಹೊರೆಯವರ ಬಣ್ಣಗಳ ಸಮೂಹವಾಗಿದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ ಪ್ರಸ್ತುತ ಬಣ್ಣವನ್ನು ಪರಿಷ್ಕರಿಸುತ್ತಲೇ ಇರುತ್ತದೆ. ಕೆಲವು ಹಂತದಲ್ಲಿ, n ಹಂತಗಳ ಮೊದಲು, ಇಲ್ಲಿ n ಎಂಬುದು ಶೃಂಗಗಳ ಸಂಖ್ಯೆ, ಇದು ಸ್ಥಿರಗೊಳ್ಳುತ್ತದೆಃ t ಹೆಚ್ಚಾದಾಗ ಇನ್ನು ಮುಂದೆ ಬದಲಾಗುವುದಿಲ್ಲ. ಈ ಅಂತಿಮ ಬಣ್ಣವನ್ನು ಸ್ಥಿರ ಬಣ್ಣ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಅಭಿವ್ಯಕ್ತಿಶೀಲತೆ ಈ ಕ್ರಮಾವಳಿಯು 6ರ ಉದ್ದದ ಚಕ್ರವನ್ನು ಒಂದು ಜೋಡಿ ತ್ರಿಕೋನಗಳಿಂದ ಪ್ರತ್ಯೇಕಿಸುವುದಿಲ್ಲ (ಉದಾಹರಣೆಗೆ ವಿ. 1 ಇಂಚು). ಸಂಕೀರ್ಣತೆ ಸ್ಥಿರ ಬಣ್ಣವನ್ನು O ((n + m) ಲಾಗ್ n) ನಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು, ಅಲ್ಲಿ n ಎಂದರೆ ಶೃಂಗಗಳ ಸಂಖ್ಯೆ ಮತ್ತು m ಎಂದರೆ ಅಂಚುಗಳ ಸಂಖ್ಯೆ. ಈ ಸಂಕೀರ್ಣತೆಯು ಕೆಲವು ವರ್ಗದ ಗ್ರಾಫ್ಗಳಿಗೆ ಸೂಕ್ತವೆಂದು ಸಾಬೀತಾಗಿದೆ. ಉಲ್ಲೇಖಗಳು ಗ್ರಾಫ್ ಕ್ರಮಾವಳಿಗಳು ಐಸೊಮಾರ್ಫಿಸಮ್ ಪ್ರಮೇಯಗಳು