Algebraic graph theory
ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತವು ಗಣಿತಶಾಸ್ತ್ರದ ಒಂದು ಶಾಖೆಯಾಗಿದ್ದು, ಇದರಲ್ಲಿ ಗ್ರಾಫ್ಗಳ ಬಗೆಗಿನ ಸಮಸ್ಯೆಗಳಿಗೆ ಬೀಜಗಣಿತದ ವಿಧಾನಗಳನ್ನು ಅನ್ವಯಿಸಲಾಗುತ್ತದೆ. ಇದು ಜ್ಯಾಮಿತೀಯ, ಸಂಯೋಜಿತ ಅಥವಾ ಕ್ರಮಾವಳಿ ವಿಧಾನಗಳಿಗೆ ವ್ಯತಿರಿಕ್ತವಾಗಿದೆ. ರೇಖೀಯ ಬೀಜಗಣಿತದ ಬಳಕೆ, ಗುಂಪು ಸಿದ್ಧಾಂತದ ಬಳಕೆ ಮತ್ತು ಗ್ರಾಫ್ ಅಸ್ಥಿರಗಳ ಅಧ್ಯಯನವನ್ನು ಒಳಗೊಂಡಿರುವ ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಮೂರು ಪ್ರಮುಖ ಶಾಖೆಗಳಿವೆ. ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಶಾಖೆಗಳು ರೇಖೀಯ ಬೀಜಗಣಿತವನ್ನು ಬಳಸುವುದು ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಮೊದಲ ಶಾಖೆಯು ರೇಖೀಯ ಬೀಜಗಣಿತಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ಗ್ರಾಫ್ಗಳ ಅಧ್ಯಯನವನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ವಿಶೇಷವಾಗಿ, ಇದು ಪಕ್ಕದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ವರ್ಣಪಟಲವನ್ನು ಅಥವಾ ಗ್ರಾಫ್ನ ಲ್ಯಾಪ್ಲೇಸಿಯನ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತದೆ (ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಈ ಭಾಗವನ್ನು ಸ್ಪೆಕ್ಟ್ರಲ್ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ). ಉದಾಹರಣೆಗೆ, ಪೀಟರ್ಸನ್ ಗ್ರಾಫ್ಗೆ, ಸಮೀಪದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ವರ್ಣಪಟಲವು (−2, −2, −2, −2,1,1,1,1,3) ಆಗಿದೆ. ಹಲವಾರು ಪ್ರಮೇಯಗಳು ವರ್ಣಪಟಲದ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಇತರ ಗ್ರಾಫ್ ಗುಣಲಕ್ಷಣಗಳಿಗೆ ಸಂಬಂಧಿಸಿವೆ. ಒಂದು ಸರಳ ಉದಾಹರಣೆಯಾಗಿ, ಡಿ ವ್ಯಾಸವನ್ನು ಹೊಂದಿರುವ ಸಂಪರ್ಕಿತ ರೇಖಾಚಿತ್ರವು ಅದರ ವರ್ಣಪಟಲದಲ್ಲಿ ಕನಿಷ್ಠ ಡಿ + 1 ವಿಭಿನ್ನ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಜಾಲಗಳ ಸಮನ್ವಯತೆಯನ್ನು ವಿಶ್ಲೇಷಿಸಲು ಗ್ರಾಫ್ ಸ್ಪೆಕ್ಟ್ರಾದ ಅಂಶಗಳನ್ನು ಬಳಸಲಾಗಿದೆ. ಗುಂಪು ಸಿದ್ಧಾಂತವನ್ನು ಬಳಸುವುದು ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಎರಡನೇ ಶಾಖೆಯು ಗುಂಪು ಸಿದ್ಧಾಂತಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ಗ್ರಾಫ್ಗಳ ಅಧ್ಯಯನವನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ವಿಶೇಷವಾಗಿ ಆಟೋಮಾರ್ಫಿಸಂ ಗುಂಪುಗಳು ಮತ್ತು ಜ್ಯಾಮಿತೀಯ ಗುಂಪು ಸಿದ್ಧಾಂತ. ಸಮ್ಮಿತಿಯ ಆಧಾರದ ಮೇಲೆ ಗ್ರಾಫ್ಗಳ ವಿವಿಧ ಕುಟುಂಬಗಳ ಮೇಲೆ ಗಮನವನ್ನು ಕೇಂದ್ರೀಕರಿಸಲಾಗಿದೆ (ಉದಾಹರಣೆಗೆ ಸಮ್ಮಿತೀಯ ಗ್ರಾಫ್ಗಳು, ಶೃಂಗ-ಸಂಕ್ರಮಣ ಗ್ರಾಫ್ಗಳು, ಅಂಚು-ಸಂಕ್ರಮಣ ಗ್ರಾಫ್ಗಳು, ದೂರ-ಸಂಕ್ರಮಣ ಗ್ರಾಫ್ಗಳು, ದೂರ-ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಬಲವಾಗಿ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳು) ಮತ್ತು ಈ ಕುಟುಂಬಗಳ ನಡುವಿನ ಸೇರ್ಪಡೆ ಸಂಬಂಧಗಳ ಮೇಲೆ. ಅಂತಹ ಕೆಲವು ವರ್ಗಗಳ ರೇಖಾಚಿತ್ರಗಳು ವಿರಳವಾಗಿದ್ದು, ರೇಖಾಚಿತ್ರಗಳ ಪಟ್ಟಿಗಳನ್ನು ರಚಿಸಬಹುದು. ಫ್ರುಕ್ಟ್ನ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಎಲ್ಲಾ ಗುಂಪುಗಳನ್ನು ಸಂಪರ್ಕಿತ ರೇಖಾಚಿತ್ರದ ಸ್ವಯಂಚಾಲಿತ ಗುಂಪು ಎಂದು ಪ್ರತಿನಿಧಿಸಬಹುದು (ವಾಸ್ತವವಾಗಿ, ಘನ ರೇಖಾಚಿತ್ರದ). ಗುಂಪು ಸಿದ್ಧಾಂತದೊಂದಿಗಿನ ಮತ್ತೊಂದು ಸಂಬಂಧವೆಂದರೆ, ಯಾವುದೇ ಗುಂಪನ್ನು ನೀಡಿದರೆ, ಕೇಲೆ ಗ್ರಾಫ್ಗಳು ಎಂದು ಕರೆಯಲ್ಪಡುವ ಸಮ್ಮಿತೀಯ ಗ್ರಾಫ್ಗಳನ್ನು ರಚಿಸಬಹುದು ಮತ್ತು ಇವು ಗುಂಪಿನ ರಚನೆಗೆ ಸಂಬಂಧಿಸಿದ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿವೆ. ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಈ ಎರಡನೇ ಶಾಖೆಯು ಮೊದಲನೆಯದಕ್ಕೆ ಸಂಬಂಧಿಸಿದೆ, ಏಕೆಂದರೆ ಗ್ರಾಫ್ನ ಸಮ್ಮಿತಿಯ ಗುಣಲಕ್ಷಣಗಳು ಅದರ ವರ್ಣಪಟಲದಲ್ಲಿ ಪ್ರತಿಫಲಿಸುತ್ತವೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಪೀಟರ್ಸನ್ ರೇಖಾಚಿತ್ರದಂತಹ ಹೆಚ್ಚು ಸಮ್ಮಿತೀಯ ರೇಖಾಚಿತ್ರದ ವರ್ಣಪಟಲವು ಕೆಲವು ವಿಭಿನ್ನ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿದೆ (ಪೀಟರ್ಸನ್ ರೇಖಾಚಿತ್ರವು 3 ಅನ್ನು ಹೊಂದಿದೆ, ಇದು ಅದರ ವ್ಯಾಸವನ್ನು ಗಮನಿಸಿದರೆ ಸಾಧ್ಯವಾದಷ್ಟು ಕನಿಷ್ಠವಾಗಿದೆ). ಕೇಲೆಯ ರೇಖಾಚಿತ್ರಗಳಿಗೆ, ವರ್ಣಪಟಲವು ನೇರವಾಗಿ ಗುಂಪಿನ ರಚನೆಗೆ, ವಿಶೇಷವಾಗಿ ಅದರ ಇರ್ರೆಡ್ಯೂಸಿಬಲ್ ಅಕ್ಷರಗಳಿಗೆ ಸಂಬಂಧಿಸಿರಬಹುದು. ಗ್ರಾಫ್ ಇನ್ವೇರಿಯಂಟ್ಗಳನ್ನು ಅಧ್ಯಯನ ಮಾಡುವುದು ಅಂತಿಮವಾಗಿ, ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಮೂರನೇ ಶಾಖೆಯು ಗ್ರಾಫ್ಗಳ ಇನ್ವೇರಿಯಂಟ್ಗಳ ಬೀಜಗಣಿತದ ಗುಣಲಕ್ಷಣಗಳಿಗೆ ಸಂಬಂಧಿಸಿದೆ, ಮತ್ತು ವಿಶೇಷವಾಗಿ ವರ್ಣದ ಬಹುಪದ, ಟುಟ್ಟೆ ಬಹುಪದ ಮತ್ತು ಗಂಟು ಇನ್ವೇರಿಯಂಟ್ಗಳಿಗೆ ಸಂಬಂಧಿಸಿದೆ. ಉದಾಹರಣೆಗೆ, ರೇಖಾಚಿತ್ರದ ವರ್ಣದ ಬಹುಪದವು ಅದರ ಸರಿಯಾದ ಶೃಂಗದ ಬಣ್ಣಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುತ್ತದೆ. ಪೀಟರ್ಸನ್ ಗ್ರಾಫ್ಗೆ, ಈ ಬಹುಪದವು. ನಿರ್ದಿಷ್ಟವಾಗಿ, ಇದರರ್ಥ ಪೀಟರ್ಸನ್ ರೇಖಾಚಿತ್ರವನ್ನು ಒಂದು ಅಥವಾ ಎರಡು ಬಣ್ಣಗಳಿಂದ ಸರಿಯಾಗಿ ಬಣ್ಣ ಮಾಡಲಾಗುವುದಿಲ್ಲ, ಆದರೆ 3 ಬಣ್ಣಗಳೊಂದಿಗೆ 120 ವಿಭಿನ್ನ ರೀತಿಯಲ್ಲಿ ಬಣ್ಣ ಮಾಡಬಹುದು. ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಈ ಕ್ಷೇತ್ರದಲ್ಲಿ ಹೆಚ್ಚಿನ ಕೆಲಸವು ನಾಲ್ಕು ಬಣ್ಣದ ಪ್ರಮೇಯವನ್ನು ಸಾಬೀತುಪಡಿಸುವ ಪ್ರಯತ್ನಗಳಿಂದ ಪ್ರೇರೇಪಿಸಲ್ಪಟ್ಟಿದೆ. ಆದಾಗ್ಯೂ, ಒಂದೇ ವರ್ಣದ ಬಹುಪದವನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳನ್ನು ನಿರೂಪಿಸುವುದು ಮತ್ತು ಯಾವ ಬಹುಪದಗಳು ವರ್ಣದವಾಗಿವೆ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವಂತಹ ಅನೇಕ ಮುಕ್ತ ಸಮಸ್ಯೆಗಳಿವೆ. ಸ್ಪೆಕ್ಟ್ರಲ್ ಗ್ರಾಫ್ ಥಿಯರಿ ಆಲ್ಜಿಬ್ರಾಯಿಕ್ ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ಆಲ್ಜಿಬ್ರಾಯಿಕ್ ಕನೆಕ್ಟಿವಿಟಿ ಡಲ್ಮೇಜ್-ಮೆಂಡೆಲ್ಸೋನ್ ಡಿಕಂಪೊಸಿಷನ್ ಗ್ರಾಫ್ ಪ್ರಾಪರ್ಟಿ ಅಡ್ಜಸೆನ್ಸಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಉಲ್ಲೇಖಗಳನ್ನು ಸಹ ನೋಡಿ. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು