Circle graph
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ವೃತ್ತದ ರೇಖಾಚಿತ್ರವು ಸ್ವರಮೇಳದ ರೇಖಾಚಿತ್ರದ ಛೇದಕ ರೇಖಾಚಿತ್ರವಾಗಿದೆ. ಅಂದರೆ, ಇದು ನಿರ್ದೇಶಿಸದ ರೇಖಾಚಿತ್ರವಾಗಿದ್ದು, ಅದರ ಶೃಂಗಗಳನ್ನು ವೃತ್ತದ ಸ್ವರಮೇಳಗಳ ಸೀಮಿತ ವ್ಯವಸ್ಥೆಯೊಂದಿಗೆ ಸಂಯೋಜಿಸಬಹುದು, ಅಂದರೆ ಅನುಗುಣವಾದ ಸ್ವರಮೇಳಗಳು ಪರಸ್ಪರ ದಾಟಿದರೆ ಮಾತ್ರ ಎರಡು ಶೃಂಗಗಳು ಪಕ್ಕದಲ್ಲಿರುತ್ತವೆ. ಅಲ್ಗಾರಿದಮಿಕ್ ಸಂಕೀರ್ಣತೆಯು O (n2)-ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡುತ್ತದೆ, ಇದು ನೀಡಲಾದ n-ವೆರ್ಟೆಕ್ಸ್ ಅನಿರ್ದಿಷ್ಟ ಗ್ರಾಫ್ ವೃತ್ತದ ಗ್ರಾಫ್ ಆಗಿದೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸುತ್ತದೆ ಮತ್ತು ಅದು ಇದ್ದರೆ, ಅದನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಸ್ವರಮೇಳಗಳ ಗುಂಪನ್ನು ನಿರ್ಮಿಸುತ್ತದೆ. ಸಾಮಾನ್ಯ ರೇಖಾಚಿತ್ರಗಳಲ್ಲಿ ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿರುವ ಹಲವಾರು ಇತರ ಸಮಸ್ಯೆಗಳು ವೃತ್ತ ನಕ್ಷೆಗಳಿಗೆ ಸೀಮಿತವಾದಾಗ ಬಹುಪದ ಸಮಯದ ಕ್ರಮಾವಳಿಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಉದಾಹರಣೆಗೆ, ವೃತ್ತದ ರೇಖಾಚಿತ್ರದ ಮೂರು ಅಗಲವನ್ನು ನಿರ್ಧರಿಸಬಹುದು ಮತ್ತು O (n3) ಸಮಯದಲ್ಲಿ ಸೂಕ್ತವಾದ ಮರದ ವಿಭಜನೆಯನ್ನು ನಿರ್ಮಿಸಬಹುದು ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಹೆಚ್ಚುವರಿಯಾಗಿ, O (n3) ಸಮಯದಲ್ಲಿ ಕನಿಷ್ಠ ಫಿಲ್-ಇನ್ (ಅಂದರೆ, ನೀಡಲಾದ ವೃತ್ತದ ಗ್ರಾಫ್ ಅನ್ನು ಉಪವಿಭಾಗವಾಗಿ ಒಳಗೊಂಡಿರುವ ಸಾಧ್ಯವಾದಷ್ಟು ಕಡಿಮೆ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಸ್ವರಮೇಳದ ಗ್ರಾಫ್) ಅನ್ನು ಕಾಣಬಹುದು. ವೃತ್ತ ಗ್ರಾಫ್ನ ಗರಿಷ್ಠ ಗುಂಪನ್ನು O (n log2n) ಸಮಯದಲ್ಲಿ ಕಾಣಬಹುದು ಎಂದು ತೋರಿಸಿದೆ, ಆದರೆ ತೂಕವಿಲ್ಲದ ವೃತ್ತ ಗ್ರಾಫ್ನ ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಗುಂಪನ್ನು O (n ನಿಮಿಷ {d, α}) ಸಮಯದಲ್ಲಿ ಕಾಣಬಹುದು ಎಂದು ತೋರಿಸಿದೆ, ಅಲ್ಲಿ d ಅದರ ಸಾಂದ್ರತೆ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಗ್ರಾಫ್ನ ನಿಯತಾಂಕವಾಗಿದೆ ಮತ್ತು α ವೃತ್ತ ಗ್ರಾಫ್ನ ಸ್ವತಂತ್ರ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಆದಾಗ್ಯೂ, ವೃತ್ತ ನಕ್ಷೆಗಳಿಗೆ ಸೀಮಿತವಾದಾಗ NP-ಪೂರ್ಣವಾಗಿ ಉಳಿಯುವ ಸಮಸ್ಯೆಗಳೂ ಇವೆ. ಇವುಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಪ್ರಾಬಲ್ಯದ ಸೆಟ್, ಕನಿಷ್ಠ ಸಂಪರ್ಕಿತ ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ ಮತ್ತು ಕನಿಷ್ಠ ಒಟ್ಟು ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ ಸಮಸ್ಯೆಗಳು ಸೇರಿವೆ. ಕ್ರೋಮಾಟಿಕ್ ಸಂಖ್ಯೆ ವೃತ್ತದ ಗ್ರಾಫ್ನ ಕ್ರೋಮಾಟಿಕ್ ಸಂಖ್ಯೆಯು ಅದರ ಸ್ವರಮೇಳಗಳಿಗೆ ಬಣ್ಣ ಹಾಕಲು ಬಳಸಬಹುದಾದ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಬಣ್ಣಗಳಾಗಿದ್ದು, ಯಾವುದೇ ಎರಡು ದಾಟುವ ಸ್ವರಮೇಳಗಳು ಒಂದೇ ಬಣ್ಣವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. ವೃತ್ತದ ರೇಖಾಚಿತ್ರಗಳನ್ನು ರಚಿಸಲು ಸಾಧ್ಯವಿರುವುದರಿಂದ, ಇದರಲ್ಲಿ ಅನಿಯಂತ್ರಿತವಾಗಿ ದೊಡ್ಡ ಸ್ವರಮೇಳಗಳು ಪರಸ್ಪರ ದಾಟುತ್ತವೆ, ವೃತ್ತದ ರೇಖಾಚಿತ್ರದ ವರ್ಣದ ಸಂಖ್ಯೆಯು ಅನಿಯಂತ್ರಿತವಾಗಿ ದೊಡ್ಡದಾಗಿರಬಹುದು ಮತ್ತು ವೃತ್ತದ ರೇಖಾಚಿತ್ರದ ವರ್ಣದ ಸಂಖ್ಯೆಯನ್ನು ನಿರ್ಧರಿಸುವುದು ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿರುತ್ತದೆ. ವೃತ್ತದ ರೇಖಾಚಿತ್ರವನ್ನು ನಾಲ್ಕು ಬಣ್ಣಗಳಿಂದ ಬಣ್ಣ ಮಾಡಬಹುದೇ ಎಂದು ಪರೀಕ್ಷಿಸಲು ಇದು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿ ಉಳಿದಿದೆ. ಮೂರು ಬಣ್ಣಗಳ ಬಣ್ಣವನ್ನು ಕಂಡುಹಿಡಿಯುವುದನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಮಾಡಬಹುದು ಆದರೆ ಈ ಫಲಿತಾಂಶದ ಅವರ ಬರವಣಿಗೆಯು ಅನೇಕ ವಿವರಗಳನ್ನು ಬಿಟ್ಟುಬಿಡುತ್ತದೆ ಎಂದು ಪ್ರತಿಪಾದಿಸಿದರು. ಹಲವಾರು ಲೇಖಕರು ವೃತ್ತ ನಕ್ಷೆಗಳ ನಿರ್ಬಂಧಿತ ಉಪವರ್ಗಗಳನ್ನು ಕೆಲವು ಬಣ್ಣಗಳೊಂದಿಗೆ ಬಣ್ಣ ಮಾಡುವ ಸಮಸ್ಯೆಗಳನ್ನು ತನಿಖೆ ಮಾಡಿದ್ದಾರೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಯಾವುದೇ ಕೆ ಅಥವಾ ಹೆಚ್ಚಿನ ಸ್ವರಮೇಳಗಳು ಪರಸ್ಪರ ದಾಟದ ವೃತ್ತ ನಕ್ಷೆಗಳಿಗೆ, ರೇಖಾಚಿತ್ರವನ್ನು ಕಡಿಮೆ ಬಣ್ಣಗಳಿಂದ ಬಣ್ಣ ಮಾಡಲು ಸಾಧ್ಯವಿದೆ. ಇದನ್ನು ಹೇಳುವ ಒಂದು ವಿಧಾನವೆಂದರೆ ವೃತ್ತದ ರೇಖಾಚಿತ್ರಗಳು-ಸೀಮಿತವಾಗಿವೆ. ನಿರ್ದಿಷ್ಟ ಸಂದರ್ಭದಲ್ಲಿ k = 3 (ಅಂದರೆ, ತ್ರಿಕೋನ-ಮುಕ್ತ ವೃತ್ತ ನಕ್ಷೆಗಳಿಗೆ) ವರ್ಣದ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ ಐದು ಆಗಿರುತ್ತದೆ ಮತ್ತು ಇದು ಬಿಗಿಯಾಗಿರುತ್ತದೆಃ ಎಲ್ಲಾ ತ್ರಿಕೋನ-ಮುಕ್ತ ವೃತ್ತ ನಕ್ಷೆಗಳು ಐದು ಬಣ್ಣಗಳಿಂದ ಬಣ್ಣ ಹೊಂದಿರಬಹುದು ಮತ್ತು ಐದು ಬಣ್ಣಗಳ ಅಗತ್ಯವಿರುವ ತ್ರಿಕೋನ-ಮುಕ್ತ ವೃತ್ತ ನಕ್ಷೆಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿರುತ್ತವೆ. ವೃತ್ತದ ನಕ್ಷೆಯು ಕನಿಷ್ಠ ಐದು ಸುತ್ತಳತೆಗಳನ್ನು ಹೊಂದಿದ್ದರೆ (ಅಂದರೆ, ಅದು ತ್ರಿಕೋನ-ಮುಕ್ತವಾಗಿದೆ ಮತ್ತು ನಾಲ್ಕು-ಅಕ್ಷತಂತು ಚಕ್ರಗಳನ್ನು ಹೊಂದಿಲ್ಲ) ಅದನ್ನು ಗರಿಷ್ಠ ಮೂರು ಬಣ್ಣಗಳಿಂದ ಬಣ್ಣ ಮಾಡಬಹುದು. ತ್ರಿಕೋನ-ಮುಕ್ತ ಚೌಕ ನಕ್ಷೆಗಳಿಗೆ ಬಣ್ಣ ಹಾಕುವ ಸಮಸ್ಯೆಯು ಚೌಕ ನಕ್ಷೆಗಳನ್ನು ಮರಗಳ ಕಾರ್ಟೇಶಿಯನ್ ಉತ್ಪನ್ನಗಳ ಐಸೊಮೆಟ್ರಿಕ್ ಉಪ ನಕ್ಷೆಗಳಾಗಿ ಪ್ರತಿನಿಧಿಸುವ ಸಮಸ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ; ಈ ಪತ್ರವ್ಯವಹಾರದಲ್ಲಿ, ಬಣ್ಣದಲ್ಲಿನ ಬಣ್ಣಗಳ ಸಂಖ್ಯೆಯು ಉತ್ಪನ್ನದ ಪ್ರಾತಿನಿಧ್ಯದಲ್ಲಿನ ಮರಗಳ ಸಂಖ್ಯೆಗೆ ಅನುರೂಪವಾಗಿದೆ. "ಎರಡು-ಟರ್ಮಿನಲ್ ಸ್ವಿಚ್ಬಾಕ್ಸ್ ರೂಟಿಂಗ್" ಎಂದು ಕರೆಯಲ್ಪಡುವ ತಂತಿ ರೂಟಿಂಗ್ಗಾಗಿ ವಿಶೇಷ ಪ್ರಕರಣಕ್ಕೆ ಅಮೂರ್ತ ಪ್ರಾತಿನಿಧ್ಯವಾಗಿ ವಿಎಲ್ಎಸ್ಐ ಭೌತಿಕ ವಿನ್ಯಾಸದಲ್ಲಿ ಸರ್ಕಲ್ ಗ್ರಾಫ್ಗಳು ಉದ್ಭವಿಸುತ್ತವೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ ರೂಟಿಂಗ್ ಪ್ರದೇಶವು ಆಯತವಾಗಿದೆ, ಎಲ್ಲಾ ಬಲೆಗಳು ಎರಡು-ಟರ್ಮಿನಲ್ ಆಗಿರುತ್ತವೆ ಮತ್ತು ಟರ್ಮಿನಲ್ಗಳನ್ನು ಆಯತದ ಪರಿಧಿಯ ಮೇಲೆ ಇರಿಸಲಾಗುತ್ತದೆ. ಈ ಬಲೆಗಳ ಛೇದಕ ರೇಖಾಚಿತ್ರವು ವೃತ್ತಾಕಾರದ ರೇಖಾಚಿತ್ರವಾಗಿದೆ ಎಂದು ಸುಲಭವಾಗಿ ಕಾಣಬಹುದು. ತಂತಿ ರೂಟಿಂಗ್ ಹಂತದ ಗುರಿಗಳಲ್ಲಿ ವಿವಿಧ ಬಲೆಗಳು ವಿದ್ಯುತ್ ಸಂಪರ್ಕವನ್ನು ಕಡಿತಗೊಳಿಸುವುದನ್ನು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳುವುದು ಮತ್ತು ಅವುಗಳ ಸಂಭಾವ್ಯ ಛೇದಕ ಭಾಗಗಳನ್ನು ವಿವಿಧ ವಾಹಕ ಪದರಗಳಲ್ಲಿ ಹಾಕಬೇಕು. ಆದ್ದರಿಂದ ವೃತ್ತ ನಕ್ಷೆಗಳು ಈ ರೂಟಿಂಗ್ ಸಮಸ್ಯೆಯ ವಿವಿಧ ಅಂಶಗಳನ್ನು ಸೆರೆಹಿಡಿಯುತ್ತವೆ. ಸರ್ಕಲ್ ಗ್ರಾಫ್ಗಳ ಬಣ್ಣಗಳನ್ನು ಅನಿಯಂತ್ರಿತ ಗ್ರಾಫ್ಗಳ ಪುಸ್ತಕ ಎಂಬೆಡಿಂಗ್ಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಹ ಬಳಸಬಹುದುಃ ನಿರ್ದಿಷ್ಟ ಗ್ರಾಫ್ G ಯ ಶೃಂಗಗಳನ್ನು ವೃತ್ತದ ಮೇಲೆ ಜೋಡಿಸಿ, G ಯ ಅಂಚುಗಳು ವೃತ್ತದ ಸ್ವರಮೇಳಗಳನ್ನು ರೂಪಿಸಿದರೆ, ಈ ಸ್ವರಮೇಳಗಳ ಛೇದಕ ಗ್ರಾಫ್ ವೃತ್ತದ ಗ್ರಾಫ್ ಆಗಿರುತ್ತದೆ ಮತ್ತು ಈ ವೃತ್ತ ಗ್ರಾಫ್ನ ಬಣ್ಣಗಳು ನೀಡಲಾದ ವೃತ್ತಾಕಾರದ ವಿನ್ಯಾಸವನ್ನು ಗೌರವಿಸುವ ಪುಸ್ತಕ ಎಂಬೆಡಿಂಗ್ಗಳಿಗೆ ಸಮನಾಗಿರುತ್ತದೆ. ಈ ಸಮಾನತೆಯಲ್ಲಿ, ಬಣ್ಣದಲ್ಲಿನ ಬಣ್ಣಗಳ ಸಂಖ್ಯೆಯು ಪುಸ್ತಕದ ಎಂಬೆಡಿಂಗ್ನಲ್ಲಿರುವ ಪುಟಗಳ ಸಂಖ್ಯೆಗೆ ಅನುಗುಣವಾಗಿರುತ್ತದೆ. ಸಂಬಂಧಿತ ಗ್ರಾಫ್ ವರ್ಗಗಳು ಒಂದು ರೇಖೆಯ ಮೇಲಿನ ಮಧ್ಯಂತರಗಳ ಗುಂಪಿನ ಅತಿವ್ಯಾಪ್ತಿ ಗ್ರಾಫ್ ಆಗಿದ್ದರೆ ಮಾತ್ರ ಗ್ರಾಫ್ ವೃತ್ತಾಕಾರದ ಗ್ರಾಫ್ ಆಗಿರುತ್ತದೆ. ಇದು ಒಂದು ರೇಖಾಚಿತ್ರವಾಗಿದ್ದು, ಇದರಲ್ಲಿ ಶೃಂಗಗಳು ಮಧ್ಯಂತರಗಳಿಗೆ ಅನುಗುಣವಾಗಿರುತ್ತವೆ, ಮತ್ತು ಎರಡು ಮಧ್ಯಂತರಗಳು ಅತಿಕ್ರಮಿಸಿದರೆ ಎರಡು ಶೃಂಗಗಳು ಒಂದು ಅಂಚಿನಿಂದ ಸಂಪರ್ಕಗೊಳ್ಳುತ್ತವೆ, ಯಾವುದೂ ಇನ್ನೊಂದನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. ಒಂದು ರೇಖೆಯ ಮೇಲಿನ ಮಧ್ಯಂತರಗಳ ಗುಂಪಿನ ಛೇದಕ ರೇಖಾಚಿತ್ರವನ್ನು ಮಧ್ಯಂತರ ರೇಖಾಚಿತ್ರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಸ್ಟ್ರಿಂಗ್ ಗ್ರಾಫ್ಗಳು, ಸಮತಲದಲ್ಲಿನ ವಕ್ರಾಕೃತಿಗಳ ಛೇದಕ ಗ್ರಾಫ್ಗಳು, ವೃತ್ತದ ಗ್ರಾಫ್ಗಳನ್ನು ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿ ಒಳಗೊಂಡಿರುತ್ತವೆ. ಪ್ರತಿ ಕ್ರಮಪಲ್ಲಟನೆ ರೇಖಾಚಿತ್ರ ಮತ್ತು ಪ್ರತಿ ಉದಾಸೀನತೆಯ ರೇಖಾಚಿತ್ರದಂತೆ, ಪ್ರತಿ ದೂರ-ಆನುವಂಶಿಕ ರೇಖಾಚಿತ್ರವು ವೃತ್ತದ ರೇಖಾಚಿತ್ರವಾಗಿದೆ. ಪ್ರತಿಯೊಂದು ಬಾಹ್ಯ ಸಮತಲೀಯ ರೇಖಾಚಿತ್ರವೂ ಸಹ ವೃತ್ತಾಕಾರದ ರೇಖಾಚಿತ್ರವಾಗಿದೆ. ವೃತ್ತದ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಬಹುಭುಜಾಕೃತಿ-ವೃತ್ತದ ರೇಖಾಚಿತ್ರಗಳಿಂದ ಸಾಮಾನ್ಯೀಕರಿಸಲಾಗುತ್ತದೆ, ಬಹುಭುಜಾಕೃತಿಗಳ ಛೇದಕ ರೇಖಾಚಿತ್ರಗಳು ಒಂದೇ ವೃತ್ತದಲ್ಲಿ ಕೆತ್ತಲಾಗಿದೆ. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು. .. .. .. .. .. .. ಉಲ್ಲೇಖಿಸಿದಂತೆ. .. ಉಲ್ಲೇಖಿಸಿದಂತೆ. .. ಉಲ್ಲೇಖಿಸಿದಂತೆ. .. .. .. .. ಉಲ್ಲೇಖಿಸಿದಂತೆ. .. .. .. .. .. .. .. ಉಲ್ಲೇಖಿಸಿದಂತೆ. ರೇಖಾಕೃತಿಗಳ ವಲಯಗಳ ಛೇದನ ವರ್ಗಗಳು ಜ್ಯಾಮಿತೀಯ ರೇಖಾಚಿತ್ರಗಳು