Recursive largest first algorithm
ರಿಕರ್ಸಿವ್ ಲಾರ್ಜೆಸ್ಟ್ ಫಸ್ಟ್ (ಆರ್ಎಲ್ಎಫ್) ಅಲ್ಗಾರಿದಮ್ ಎನ್ಪಿ-ಹಾರ್ಡ್ ಗ್ರಾಫ್ ಬಣ್ಣದ ಸಮಸ್ಯೆಗೆ ಒಂದು ಶೋಧಕವಾಗಿದೆ. ಇದನ್ನು ಮೂಲತಃ ಫ್ರಾಂಕ್ ಲೈಟನ್ ಅವರು 1979 ರಲ್ಲಿ ಪ್ರಸ್ತಾಪಿಸಿದರು. ಆರ್ಎಲ್ಎಫ್ ಅಲ್ಗಾರಿದಮ್ ಪ್ರತಿ ಬಣ್ಣದ ವರ್ಗವನ್ನು ಒಂದು ಸಮಯದಲ್ಲಿ ನಿರ್ಮಿಸುವ ಮೂಲಕ ಗ್ರಾಫ್ನ ಶೃಂಗಗಳಿಗೆ ಬಣ್ಣಗಳನ್ನು ನಿಯೋಜಿಸುತ್ತದೆ. ಇದು ರೇಖಾಚಿತ್ರದಲ್ಲಿನ ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಶೃಂಗಗಳನ್ನು ಗುರುತಿಸುವ ಮೂಲಕ, ಅವುಗಳನ್ನು ಒಂದೇ ಬಣ್ಣಕ್ಕೆ ನಿಯೋಜಿಸುವ ಮೂಲಕ ಮತ್ತು ನಂತರ ರೇಖಾಚಿತ್ರದಿಂದ ಈ ಶೃಂಗಗಳನ್ನು ತೆಗೆದುಹಾಕುವ ಮೂಲಕ ಇದನ್ನು ಮಾಡುತ್ತದೆ. ಯಾವುದೇ ಶೃಂಗಗಳು ಉಳಿದಿರದವರೆಗೂ ಈ ಕ್ರಿಯೆಗಳನ್ನು ಉಳಿದ ಉಪಗ್ರಫ್ನಲ್ಲಿ ಪುನರಾವರ್ತಿಸಲಾಗುತ್ತದೆ. ಉತ್ತಮ-ಗುಣಮಟ್ಟದ ಪರಿಹಾರಗಳನ್ನು (ಕೆಲವು ಬಣ್ಣಗಳನ್ನು ಬಳಸುವ ಪರಿಹಾರಗಳು) ರೂಪಿಸಲು, ಆರ್ಎಲ್ಎಫ್ ಅಲ್ಗಾರಿದಮ್ "ಉತ್ತಮ ಗುಣಮಟ್ಟದ" ಸ್ವತಂತ್ರ ಸೆಟ್ಗಳನ್ನು ಗುರುತಿಸಲು ವಿಶೇಷ ಹ್ಯೂರಿಸ್ಟಿಕ್ ನಿಯಮಗಳನ್ನು ಬಳಸುತ್ತದೆ. ಈ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ ಆರ್ಎಲ್ಎಫ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬೈಪಾರ್ಟೈಟ್, ಸೈಕಲ್ ಮತ್ತು ವೀಲ್ ಗ್ರಾಫ್ಗಳಿಗೆ ನಿಖರವಾಗಿಸುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಸಾಮಾನ್ಯವಾಗಿ, ಅಲ್ಗಾರಿದಮ್ ಅಂದಾಜು ಮತ್ತು ಗ್ರಾಫ್ನ ಕ್ರೋಮಾಟಿಕ್ ಸಂಖ್ಯೆಗಿಂತ ಹೆಚ್ಚಿನ ಬಣ್ಣಗಳನ್ನು ಬಳಸುವ ಪರಿಹಾರಗಳನ್ನು ಚೆನ್ನಾಗಿ ಹಿಂದಿರುಗಿಸಬಹುದು. ವಿವರಣೆ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಈ ಕೆಳಗಿನ ಮೂರು ಹಂತಗಳಿಂದ ವಿವರಿಸಬಹುದು. ಈ ಪ್ರಕ್ರಿಯೆಯ ಕೊನೆಯಲ್ಲಿ, ಗ್ರಾಫ್ನ ಕಾರ್ಯಸಾಧ್ಯವಾದ-ಬಣ್ಣವನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಶೃಂಗಗಳ ವಿಭಾಗವನ್ನು ನೀಡುತ್ತದೆ. ಖಾಲಿ ಪರಿಹಾರವಾಗಿರಲಿ. ಅಲ್ಲದೆ, ಶೃಂಗದ ಸೆಟ್ ಮತ್ತು ಅಂಚಿನ ಸೆಟ್ ಅನ್ನು ಒಳಗೊಂಡಿರುವ ನಾವು ಬಣ್ಣ ಮಾಡಲು ಬಯಸುವ ಗ್ರಾಫ್ ಆಗಿರಲಿ. ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಗುಂಪನ್ನು ಗುರುತಿಸಿ. ಇದನ್ನು ಮಾಡಲುಃ ಮೊದಲ ಶೃಂಗವು ಅತಿ ಹೆಚ್ಚು ನೆರೆಹೊರೆಯವರನ್ನು ಹೊಂದಿರುವ ಶೃಂಗವಾಗಿರಬೇಕು. ಸೇರಿಸಲಾದ ನಂತರದ ಶೃಂಗಗಳನ್ನು (ಎ) ಪ್ರಸ್ತುತ ಯಾವುದೇ ಶೃಂಗದ ಪಕ್ಕದಲ್ಲಿಲ್ಲ ಮತ್ತು (ಬಿ) ಶೃಂಗಗಳ ಪಕ್ಕದಲ್ಲಿರುವ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ನೆರೆಹೊರೆಗಳನ್ನು ಹೊಂದಿರುವಂತೆ ಆಯ್ಕೆ ಮಾಡಬೇಕು. ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ನೆರೆಹೊರೆಯವರಿಲ್ಲದ ಶೃಂಗವನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ (ಬಿ) ಸ್ಥಿತಿಯಲ್ಲಿರುವ ಸಂಬಂಧಗಳನ್ನು ಮುರಿಯಬಹುದು. ಮತ್ತಷ್ಟು ಶೃಂಗಗಳನ್ನು ಸೇರಿಸುವುದು ಅಸಾಧ್ಯವಾಗುವವರೆಗೆ ಶೃಂಗಗಳನ್ನು ಈ ರೀತಿಯಲ್ಲಿ ಸೇರಿಸಲಾಗುತ್ತದೆ. ಈಗ ಅದರ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿಸಿ ಮತ್ತು ತೆಗೆದುಹಾಕಿ. ಇನ್ನೂ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಹಂತ 2ಕ್ಕೆ ಹಿಂತಿರುಗಿ; ಇಲ್ಲದಿದ್ದರೆ ಕೊನೆಗೊಳ್ಳುತ್ತದೆ. ಉದಾಹರಣೆ ಬಲಭಾಗದಲ್ಲಿ ತೋರಿಸಿರುವ ರೇಖಾಚಿತ್ರವನ್ನು ಪರಿಗಣಿಸಿ. ಇದು ಚಕ್ರದ ರೇಖಾಚಿತ್ರವಾಗಿದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಆರ್ಎಲ್ಎಫ್ನಿಂದ ಅತ್ಯುತ್ತಮವಾಗಿ ಬಣ್ಣವನ್ನು ಪಡೆಯುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸುವುದರಿಂದ ಶೃಂಗಗಳನ್ನು ಈ ಕೆಳಗಿನ ಕ್ರಮದಲ್ಲಿ ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ ಮತ್ತು ಬಣ್ಣ ಮಾಡಲಾಗುತ್ತದೆಃ ವೆರ್ಟೆಕ್ಸ್ (ಬಣ್ಣ 1) ವೆರ್ಟೆಕ್ಸ್, ಮತ್ತು ನಂತರ (ಬಣ್ಣ 2) ವೆರ್ಟೆಕ್ಸ್, ಮತ್ತು ನಂತರ (ಬಣ್ಣ 3) ಇದು ಅಂತಿಮ ಮೂರು ಬಣ್ಣದ ಪರಿಹಾರವನ್ನು ನೀಡುತ್ತದೆ. ಕಾರ್ಯಕ್ಷಮತೆ ಗ್ರಾಫ್ನಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯಾಗಿರಲಿ ಮತ್ತು ಅಂಚುಗಳ ಸಂಖ್ಯೆಯಾಗಿರಲಿ. ಬಿಗ್ ಓ ಸಂಕೇತವನ್ನು ಬಳಸಿಕೊಂಡು, ಲೈಟನ್ ತನ್ನ ಮೂಲ ಪ್ರಕಟಣೆಯಲ್ಲಿ ಆರ್ಎಲ್ಎಫ್ನ ಸಂಕೀರ್ಣತೆಯನ್ನು ವಿವರಿಸುತ್ತಾನೆ; ಆದಾಗ್ಯೂ, ಇದನ್ನು ಸುಧಾರಿಸಬಹುದು. ಈ ಅಲ್ಗಾರಿದಮ್ನ ಹೆಚ್ಚಿನ ವೆಚ್ಚವು ಹಂತ 2 ರ ಕಾರಣದಿಂದಾಗಿರುತ್ತದೆ, ಅಲ್ಲಿ ಮೇಲೆ ತಿಳಿಸಲಾದ ಹ್ಯೂರಿಸ್ಟಿಕ್ ನಿಯಮಗಳ ಪ್ರಕಾರ ಶೃಂಗವನ್ನು ಆಯ್ಕೆ ಮಾಡಲಾಗುತ್ತದೆ. ವಾಸ್ತವವಾಗಿ, ಪ್ರತಿ ಬಾರಿ ಸ್ವತಂತ್ರ ಗುಂಪಿಗೆ ಹೆಚ್ಚುವರಿಯಾಗಿ ಒಂದು ಶೃಂಗವನ್ನು ಆಯ್ಕೆ ಮಾಡಿದಾಗ, ನೆರೆಯವರಿಗೆ ಸಂಬಂಧಿಸಿದ ಮಾಹಿತಿಯನ್ನು ಪ್ರತಿ ಬಣ್ಣರಹಿತ ಶೃಂಗಕ್ಕೆ ಮರು ಲೆಕ್ಕಾಚಾರ ಮಾಡಬೇಕಾಗುತ್ತದೆ. ಈ ಲೆಕ್ಕಾಚಾರಗಳನ್ನು ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಮಾಡಬಹುದು, ಅಂದರೆ ಆರ್ಎಲ್ಎಫ್ನ ಒಟ್ಟಾರೆ ಸಂಕೀರ್ಣತೆ. ಹಂತ 2 ರ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ ಅನ್ನು ಯಾದೃಚ್ಛಿಕ ಆಯ್ಕೆಯಿಂದ ಬದಲಾಯಿಸಿದರೆ, ಈ ಅಲ್ಗಾರಿದಮ್ನ ಸಂಕೀರ್ಣತೆಯು ಕಡಿಮೆಯಾಗುತ್ತದೆ; ಆದಾಗ್ಯೂ, ಫಲಿತಾಂಶದ ಅಲ್ಗಾರಿದಮ್ ಸಾಮಾನ್ಯವಾಗಿ ಆರ್ಎಲ್ಎಫ್ಗೆ ಹೋಲಿಸಿದರೆ ಕಡಿಮೆ ಗುಣಮಟ್ಟದ ಪರಿಹಾರಗಳನ್ನು ನೀಡುತ್ತದೆ. ಇದು ಈಗ ಬೈಪಾರ್ಟೈಟ್, ಸೈಕಲ್ ಮತ್ತು ವೀಲ್ ಗ್ರಾಫ್ಗಳಿಗೆ ನಿಖರವಾಗಿಲ್ಲ. 2021 ರಲ್ಲಿ ಲೆವಿಸ್ ನಡೆಸಿದ ಪ್ರಾಯೋಗಿಕ ಹೋಲಿಕೆಯಲ್ಲಿ, ಆರ್ಎಲ್ಎಫ್ ಯಾದೃಚ್ಛಿಕ ಗ್ರಾಫ್ಗಳಲ್ಲಿನ ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಮತ್ತು ಡಿಶಾಟೂರ್ ಅಲ್ಗಾರಿದಮ್ನಂತಹ ಪರ್ಯಾಯ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ಗಿಂತ ಗಮನಾರ್ಹವಾಗಿ ಉತ್ತಮ ಶೃಂಗ ಬಣ್ಣಗಳನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಆದಾಗ್ಯೂ, ಆರ್ಎಲ್ಎಫ್ನೊಂದಿಗಿನ ರನ್ಟೈಮ್ಗಳು ಅದರ ಹೆಚ್ಚಿನ ಒಟ್ಟಾರೆ ಸಂಕೀರ್ಣತೆಯಿಂದಾಗಿ ಈ ಪರ್ಯಾಯಗಳಿಗಿಂತ ಹೆಚ್ಚಾಗಿರುವುದು ಕಂಡುಬಂದಿದೆ. ಎ ಗೈಡ್ ಟು ಗ್ರಾಫ್ ಕಲರಿಂಗ್ಃ ಅಲ್ಗಾರಿದಮ್ಸ್ ಅಂಡ್ ಅಪ್ಲಿಕೇಷನ್ಸ್ (ಸ್ಪ್ರಿಂಗರ್ ಇಂಟರ್ನ್ಯಾಷನಲ್ ಪಬ್ಲಿಷರ್ಸ್, 2021) ಪುಸ್ತಕದಲ್ಲಿ ಬಳಸಲಾದ ಹೈ-ಪರ್ಫಾರ್ಮೆನ್ಸ್ ಗ್ರಾಫ್ ಕಲರಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ಸ್ ಸೂಟ್ ಆಫ್ ಗ್ರಾಫ್ ಕಲರಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ಸ್ (ಸಿ + + ನಲ್ಲಿ ಅಳವಡಿಸಲಾಗಿದೆ). 1979 ಗಣನೆಯಲ್ಲಿ ಗ್ರಾಫ್ ಕ್ರಮಾವಳಿಗಳು ಗ್ರಾಫ್ ಬಣ್ಣ