Colin de Verdière graph invariant
ಕಾಲಿನ್ ಡಿ ವರ್ಡಿಯರ್ನ ಅಸ್ಥಿರತೆಯು 1990ರಲ್ಲಿ ವೈವ್ಸ್ ಕಾಲಿನ್ ಡಿ ವರ್ಡಿಯರೆ ಪರಿಚಯಿಸಿದ ಯಾವುದೇ ಗ್ರಾಫ್ ಜಿಗೆ ಗ್ರಾಫ್ ನಿಯತಾಂಕವಾಗಿದೆ. ಕೆಲವು ಶ್ರೋಡಿಂಗರ್ ಆಪರೇಟರ್ಗಳ ಎರಡನೇ ಐಗನ್ ಮೌಲ್ಯದ ಗರಿಷ್ಠ ಬಹುಸಂಖ್ಯೆಯ ಅಧ್ಯಯನದಿಂದ ಇದು ಪ್ರೇರೇಪಿಸಲ್ಪಟ್ಟಿದೆ. ವ್ಯಾಖ್ಯಾನವು ಶೃಂಗದ ಗುಂಪಿನೊಂದಿಗೆ ಲೂಪ್ ರಹಿತ ಸರಳ ಗ್ರಾಫ್ ಆಗಿರಲಿ. ನಂತರ ಯಾವುದೇ ಸಮ್ಮಿತೀಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಅತಿದೊಡ್ಡ ಕೊರಾಂಕ್ ಎಂದರೆಃ (M1) ಎಲ್ಲರಿಗೂಃ ವೇಳೆ, ಮತ್ತು ವೇಳೆ; (M2) ನಿಖರವಾಗಿ ಒಂದು ಋಣಾತ್ಮಕ ಐಗನ್ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದೆ, ಗುಣಾಕಾರ 1 ರ; (M3) ಯಾವುದೇ ಶೂನ್ಯವಲ್ಲದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಇಲ್ಲ ಮತ್ತು ಎರಡೂ ಇದ್ದರೆ ಅಥವಾ ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳುತ್ತದೆ. ತಿಳಿದಿರುವ ಗ್ರಾಫ್ ಕುಟುಂಬಗಳ ಗುಣಲಕ್ಷಣಗಳು ಹಲವಾರು ಪ್ರಸಿದ್ಧ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳನ್ನು ಅವುಗಳ ಕಾಲಿನ್ ಡಿ ವರ್ಡಿಯೆರ್ ಅಸ್ಥಿರಗಳ ಪರಿಭಾಷೆಯಲ್ಲಿ ನಿರೂಪಿಸಬಹುದುಃ G ಗೆ ಯಾವುದೇ ಅಂಚುಗಳಿಲ್ಲದಿದ್ದರೆ ಮತ್ತು ಮಾತ್ರ; G ಒಂದು ರೇಖೀಯ ಅರಣ್ಯವಾಗಿದ್ದರೆ ಮತ್ತು ಮಾತ್ರ (ಮಾರ್ಗಗಳ ಬೇರ್ಪಡಿಸುವ ಒಕ್ಕೂಟ); G ಬಾಹ್ಯ ಸಮತಲವಾಗಿದ್ದರೆ ಮತ್ತು ಮಾತ್ರ; G ಸಮತಲವಾಗಿದ್ದರೆ ಮತ್ತು ಮಾತ್ರ; R3 ನಲ್ಲಿ G ಅನ್ನು ಸಂಪರ್ಕವಿಲ್ಲದೆ ಹುದುಗಿಸಬಹುದಾದರೆ ಮತ್ತು ಮಾತ್ರ. ಇದೇ ರೀತಿಯ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳು ಗ್ರಾಫ್ನ ಕಾಲಿನ್ ಡಿ ವರ್ಡಿಯೆರ್ ಅಸ್ಥಿರ ಮತ್ತು ಅದರ ಪೂರಕ ರಚನೆಯ ನಡುವಿನ ಸಂಪರ್ಕಗಳಲ್ಲಿ ಸಹ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತವೆಃ ಎನ್-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ನ ಪೂರಕವು ರೇಖೀಯ ಅರಣ್ಯವಾಗಿದ್ದರೆ, ನಂತರ; ಎನ್-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ನ ಪೂರಕವು ಬಾಹ್ಯ ಸಮತಲೀಯವಾಗಿದ್ದರೆ, ನಂತರ; ಎನ್-ವೆರ್ಟೆಕ್ಸ್ ಗ್ರಾಫ್ನ ಪೂರಕವು ಸಮತಲೀಯವಾಗಿದ್ದರೆ, ನಂತರ. ಗ್ರಾಫ್ ಮೈನರ್ ಎಂದರೆ ಅಂಚುಗಳನ್ನು ಸಂಕುಚಿತಗೊಳಿಸುವ ಮೂಲಕ ಮತ್ತು ಅಂಚುಗಳು ಮತ್ತು ಶೃಂಗಗಳನ್ನು ಅಳಿಸುವ ಮೂಲಕ ರಚಿಸಲಾದ ಮತ್ತೊಂದು ಗ್ರಾಫ್ ಆಗಿದೆ. ಕಾಲಿನ್ ಡಿ ವರ್ಡಿಯೆರ್ ಇನ್ವೇರಿಯಂಟ್ ಮೈನರ್-ಮೊನೊಟೋನ್ ಆಗಿದೆ, ಅಂದರೆ ಗ್ರಾಫ್ನ ಮೈನರ್ ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುವುದರಿಂದ ಅದರ ಇನ್ವೇರಿಯಂಟ್ ಅನ್ನು ಕಡಿಮೆ ಮಾಡಬಹುದು ಅಥವಾ ಬದಲಾಗದೆ ಬಿಡಬಹುದುಃ H G ಯ ಮೈನರ್ ಆಗಿದ್ದರೆ. ರಾಬರ್ಟ್ಸನ್-ಸೈಮೂರ್ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಪ್ರತಿ k ಗೆ ಒಂದು ಸೀಮಿತವಾದ H ಗ್ರಾಫ್ಗಳ ಸೆಟ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ, ಅಂದರೆ ಗರಿಷ್ಠ k ನಲ್ಲಿ ಅಸ್ಥಿರವಾಗಿರುವ ಗ್ರಾಫ್ಗಳು H ನ ಯಾವುದೇ ಸದಸ್ಯರನ್ನು ಮೈನರ್ ಆಗಿ ಹೊಂದಿರದ ಗ್ರಾಫ್ಗಳಂತೆಯೇ ಇರುತ್ತವೆ. ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಈ ಗುಂಪುಗಳನ್ನು k ≤ 3 ಗೆ ಪಟ್ಟಿ ಮಾಡುತ್ತದೆ; k = 4 ಗೆ ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಗುಂಪು ಪೀಟರ್ಸನ್ ಕುಟುಂಬದಲ್ಲಿ ಏಳು ಗ್ರಾಫ್ಗಳನ್ನು ಒಳಗೊಂಡಿದೆ, ಏಕೆಂದರೆ ಸಂಪರ್ಕವಿಲ್ಲದ ಎಂಬೆಡ್ ಮಾಡಬಹುದಾದ ಗ್ರಾಫ್ಗಳ ಎರಡು ಗುಣಲಕ್ಷಣಗಳು μ ≤ 4 ರೊಂದಿಗಿನ ಗ್ರಾಫ್ಗಳಾಗಿ ಮತ್ತು ಪೀಟರ್ಸನ್ ಕುಟುಂಬ ಮೈನರ್ ಇಲ್ಲದ ಗ್ರಾಫ್ಗಳಾಗಿ. ಕೆ = 5 ಗೆ ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಗುಂಪಿನಲ್ಲಿ ಹೇವುಡ್ ಕುಟುಂಬದ 78 ಗ್ರಾಫ್ಗಳು ಸೇರಿವೆ, ಮತ್ತು ಇನ್ನು ಮುಂದೆ ಇಲ್ಲ ಎಂದು ಊಹಿಸಲಾಗಿದೆ. ಕೋಲಿನ್ ಡಿ ವರ್ಡಿಯೆರ್ ಇನ್ವೇರಿಯಂಟ್ ಮೈಕ್ರೊಂದಿಗಿನ ಯಾವುದೇ ಗ್ರಾಫ್ ಗರಿಷ್ಠ ಮೈಕ್ರೊ + 1 ಬಣ್ಣಗಳಿಂದ ಬಣ್ಣ ಹೊಂದಿರಬಹುದು ಎಂದು ವರ್ಣತಂತು ಸಂಖ್ಯೆಯು ಊಹಿಸುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ರೇಖೀಯ ಕಾಡುಗಳು ಬದಲಾಗದ 1 ಅನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು 2-ಬಣ್ಣದವುಗಳಾಗಿರಬಹುದು; ಬಾಹ್ಯ ಸಮತಲೀಯ ನಕ್ಷೆಗಳು ಬದಲಾಗದ 2 ಅನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು 3-ಬಣ್ಣದವುಗಳಾಗಿರಬಹುದು; ಸಮತಲೀಯ ನಕ್ಷೆಗಳು ಬದಲಾಗದ 3 ಅನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು (ನಾಲ್ಕು ಬಣ್ಣದ ಪ್ರಮೇಯದ ಪ್ರಕಾರ) 4-ಬಣ್ಣದವುಗಳಾಗಿರಬಹುದು. ಕಾಲಿನ್ ಡಿ ವರ್ಡಿಯರ್ನೊಂದಿಗಿನ ಗ್ರಾಫ್ಗಳಿಗೆ ಗರಿಷ್ಠ ನಾಲ್ಕು ಬದಲಾಗದೆ, ಊಹೆಯು ನಿಜವಾಗಿ ಉಳಿದಿದೆ; ಇವು ಸಂಪರ್ಕವಿಲ್ಲದ ಎಂಬೆಡೆಡ್ ಮಾಡಬಹುದಾದ ಗ್ರಾಫ್ಗಳಾಗಿವೆ, ಮತ್ತು ಅವು ಗರಿಷ್ಠ ಐದರಲ್ಲಿ ಕ್ರೋಮಾಟಿಕ್ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿವೆ ಎಂಬ ಅಂಶವು ಕೆ6-ಮೈನರ್-ಫ್ರೀ ಗ್ರಾಫ್ಗಳಿಗಾಗಿ ಹ್ಯಾಡ್ವಿಗರ್ ಊಹೆಯ ಪುರಾವೆಯ ಪರಿಣಾಮವಾಗಿದೆ. ಇತರ ಗುಣಲಕ್ಷಣಗಳು ಒಂದು ರೇಖಾಚಿತ್ರವು ಕ್ರಾಸಿಂಗ್ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದು ಗರಿಷ್ಠ ಕಾಲಿನ್ ಡಿ ವರ್ಡಿಯೆರ್ ಅಸ್ಥಿರತೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಎರಡು ಕುರಾಟೋವ್ಸ್ಕಿ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಎರಡನ್ನೂ ಒಂದೇ ಕ್ರಾಸಿಂಗ್ನೊಂದಿಗೆ ಎಳೆಯಬಹುದು, ಮತ್ತು ಕಾಲಿನ್ ಡಿ ವರ್ಡಿಯೆರ್ ಗರಿಷ್ಠ ನಾಲ್ಕು ಸ್ಥಿರತೆಯನ್ನು ಹೊಂದಿರುತ್ತಾರೆ. ಪ್ರಭಾವ ಕಾಲಿನ್ ಡಿ ವರ್ಡಿಯೆರ್ ಇನ್ವೇರಿಯಂಟ್ ಅನ್ನು ಕೇವಲ ಒಂದೇ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಬದಲಿಗೆ ಗ್ರಾಫ್ಗೆ ಅನುಗುಣವಾದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳ ವರ್ಗದ ಮೂಲಕ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಅದೇ ರೀತಿಯಲ್ಲಿ ಇತರ ಗ್ರಾಫ್ ನಿಯತಾಂಕಗಳನ್ನು ಅದೇ ರೀತಿಯಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು ಮತ್ತು ಅಧ್ಯಯನ ಮಾಡಬಹುದು, ಉದಾಹರಣೆಗೆ ಕನಿಷ್ಠ ಶ್ರೇಣಿ, ಕನಿಷ್ಠ ಅರೆ-ಸೀಮಿತ ಶ್ರೇಣಿ ಮತ್ತು ಕನಿಷ್ಠ ವಕ್ರ ಶ್ರೇಣಿ. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು. ಇದನ್ನು ನೀಲ್ ಜೆ. ಕಾಲ್ಕಿನ್ ಅವರು ಭಾಷಾಂತರಿಸಿದ್ದಾರೆ. .. .. .. ಗ್ರಾಫ್ ಇನ್ವೇರಿಯಂಟ್ಸ್ ಗ್ರಾಫ್ ಸಣ್ಣ ಸಿದ್ಧಾಂತ