Strongly regular graph
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ (ಎಸ್ಆರ್ಜಿ) ಶೃಂಗಗಳು ಮತ್ತು ಡಿಗ್ರಿಗಳನ್ನು ಹೊಂದಿರುವ ನಿಯಮಿತ ಗ್ರಾಫ್ ಆಗಿದ್ದು, ಕೆಲವು ಪೂರ್ಣಾಂಕಗಳಿಗೆ ಪ್ರತಿ ಎರಡು ಪಕ್ಕದ ಶೃಂಗಗಳು ಸಾಮಾನ್ಯ ನೆರೆಹೊರೆಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು ಪ್ರತಿ ಎರಡು ಪಕ್ಕದ ಶೃಂಗಗಳು ಸಾಮಾನ್ಯ ನೆರೆಹೊರೆಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಅಂತಹ ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ ಅನ್ನು ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಇದರ ಪೂರಕವೂ ಸಹ ಬಲವಾಗಿ ನಿಯಮಿತವಾಗಿದೆಃ ಬಲವಾದ ನಿಯಮಿತ ರೇಖಾಚಿತ್ರವು ಶೂನ್ಯವಲ್ಲದಿದ್ದಾಗಲೆಲ್ಲಾ 2 ವ್ಯಾಸವನ್ನು ಹೊಂದಿರುವ ದೂರ-ನಿಯಮಿತ ರೇಖಾಚಿತ್ರವಾಗಿದೆ. ಇದು ಯಾವಾಗ ಬೇಕಾದರೂ ಸ್ಥಳೀಯವಾಗಿ ರೇಖೀಯ ಗ್ರಾಫ್ ಆಗಿರುತ್ತದೆ. ಒಂದು ಬಲವಾದ ನಿಯಮಿತ ರೇಖಾಚಿತ್ರವನ್ನು ಸಾಹಿತ್ಯದಲ್ಲಿ srg (v, k, λ, μ) ಎಂದು ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಸಂಪ್ರದಾಯದ ಪ್ರಕಾರ, ವ್ಯಾಖ್ಯಾನವನ್ನು ಕ್ಷುಲ್ಲಕವಾಗಿ ತೃಪ್ತಿಪಡಿಸುವ ಗ್ರಾಫ್ಗಳನ್ನು ವಿವರವಾದ ಅಧ್ಯಯನಗಳು ಮತ್ತು ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳ ಪಟ್ಟಿಗಳಿಂದ ಹೊರಗಿಡಲಾಗುತ್ತದೆ. ಇವುಗಳಲ್ಲಿ ಒಂದು ಅಥವಾ ಹೆಚ್ಚು ಸಮಾನ-ಗಾತ್ರದ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ಗಳ ಬೇರ್ಪಡುವ ಒಕ್ಕೂಟ ಮತ್ತು ಅವುಗಳ ಪೂರಕಗಳು, ಸಮಾನ-ಗಾತ್ರದ ಸ್ವತಂತ್ರ ಸೆಟ್ಗಳೊಂದಿಗೆ ಸಂಪೂರ್ಣ ಮಲ್ಟಿಪಾರ್ಟೈಟ್ ಗ್ರಾಫ್ಗಳು ಸೇರಿವೆ. ಆಂಡ್ರೀಸ್ ಬ್ರೌವರ್ ಮತ್ತು ಹೆಂಡ್ರಿಕ್ ವಾನ್ ಮಾಲ್ಡೆಘೆಮ್ (ನೋಡಿ #References) ಸ್ಪೆಕ್ಟ್ರಲ್ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಆಧಾರದ ಮೇಲೆ ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ನ ಪರ್ಯಾಯ ಆದರೆ ಸಂಪೂರ್ಣವಾಗಿ ಸಮಾನವಾದ ವ್ಯಾಖ್ಯಾನವನ್ನು ಬಳಸುತ್ತಾರೆಃ ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ ನಿಖರವಾಗಿ ಮೂರು ಐಗನ್ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುವ ಸೀಮಿತ ನಿಯಮಿತ ಗ್ರಾಫ್ ಆಗಿದೆ, ಅವುಗಳಲ್ಲಿ ಒಂದು ಮಾತ್ರ ಗುಣಾಕಾರ 1 ರ ಡಿಗ್ರಿ k ಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ಇದು ಸ್ವಯಂಚಾಲಿತವಾಗಿ ಸಂಪೂರ್ಣವಾಗಿ ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ಗಳನ್ನು (ಮೂರು ಅಲ್ಲ, ಕೇವಲ ಎರಡು ವಿಭಿನ್ನ ಐಗನ್ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುವ) ಮತ್ತು ಸಂಪರ್ಕ ಕಡಿತಗೊಂಡ ಗ್ರಾಫ್ಗಳನ್ನು (ಕೆ ಪದವಿಯ ಗುಣಾಕಾರವು ವಿವಿಧ ಸಂಪರ್ಕಿತ ಘಟಕಗಳ ಸಂಖ್ಯೆಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಅದು ಒಂದನ್ನು ಮೀರುತ್ತದೆ) ತಳ್ಳಿಹಾಕುತ್ತದೆ. ಬ್ರೌವರ್ ಸೇರಿದಂತೆ ಹೆಚ್ಚಿನ ಸಾಹಿತ್ಯವು ದೊಡ್ಡ ಐಗನ್ ಮೌಲ್ಯವನ್ನು r (ಮಲ್ಟಿಪ್ಲಿಸಿಟಿ f ನೊಂದಿಗೆ) ಮತ್ತು ಚಿಕ್ಕದನ್ನು s (ಮಲ್ಟಿಪ್ಲಿಸಿಟಿ g ನೊಂದಿಗೆ) ಎಂದು ಉಲ್ಲೇಖಿಸುತ್ತದೆ. ಇತಿಹಾಸದ ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳನ್ನು ಆರ್. ಸಿ. ಪರಿಚಯಿಸಿದರು. 1963ರಲ್ಲಿ ಬೋಸ್. ಅವರು 1950 ರ ದಶಕದಲ್ಲಿ ಸ್ಪೆಕ್ಟ್ರಲ್ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಆಗಿನ ಹೊಸ ಕ್ಷೇತ್ರದಲ್ಲಿ ಹಿಂದಿನ ಕೆಲಸವನ್ನು ನಿರ್ಮಿಸಿದರು. ಉದಾಹರಣೆಗಳು 5 ನೇ ಉದ್ದದ ಚಕ್ರವು ಎಸ್ಆರ್ಜಿ (5,2,0,1) ಆಗಿದೆ. ಪೀಟರ್ಸನ್ ಗ್ರಾಫ್ ಒಂದು ಎಸ್ಆರ್ಜಿ (10,3,0,1) ಆಗಿದೆ. ಕ್ಲೆಬ್ಷ್ ಗ್ರಾಫ್ ಒಂದು ಎಸ್ಆರ್ಜಿ (16,5,0,2) ಆಗಿದೆ. ಶ್ರೀಖಂಡೆ ರೇಖಾಚಿತ್ರವು ಒಂದು ಎಸ್. ಆರ್. ಜಿ. (16,6,2,2) ಆಗಿದ್ದು, ಇದು ದೂರ-ಪರಿವರ್ತನೆಯ ರೇಖಾಚಿತ್ರವಲ್ಲ. n × n ಸ್ಕ್ವೇರ್ ರೂಕ್ನ ಗ್ರಾಫ್, ಅಂದರೆ, ಸಮತೋಲಿತ ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ Kn, n ನ ರೇಖೆಯ ಗ್ರಾಫ್, ಒಂದು srg (n2,2n−2, n−2) ಆಗಿದೆ. ಇದರ ನಿಯತಾಂಕಗಳು ಶ್ರೀಖಂಡೆ ರೇಖಾಚಿತ್ರದೊಂದಿಗೆ ಹೊಂದಿಕೆಯಾಗುತ್ತವೆ, ಆದರೆ ಎರಡು ರೇಖಾಚಿತ್ರಗಳು ಐಸೊಮಾರ್ಫಿಕ್ ಆಗಿರುವುದಿಲ್ಲ. ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ Kn ನ ರೇಖೆಯ ರೇಖಾಚಿತ್ರವು ಒಂದು. ಚಾಂಗ್ ರೇಖಾಚಿತ್ರಗಳು ಎಸ್ಆರ್ಜಿ (28,12,6,4) ಆಗಿದ್ದು, ಕೆ8ನ ರೇಖೆಯ ರೇಖಾಚಿತ್ರದಂತೆಯೇ ಇರುತ್ತವೆ, ಆದರೆ ಈ ನಾಲ್ಕು ರೇಖಾಚಿತ್ರಗಳು ಐಸೊಮಾರ್ಫಿಕ್ ಆಗಿರುವುದಿಲ್ಲ. ಕ್ರಮದ (s, t) ಪ್ರತಿಯೊಂದು ಸಾಮಾನ್ಯೀಕೃತ ಚತುಷ್ಕೋಣವು ಒಂದು srg ((s + 1) (st + 1), s (t + 1), s-1, t + 1) ಅನ್ನು ಅದರ ರೇಖಾಕೃತಿ ಎಂದು ನೀಡುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, GQ (2,4) srg (27,10,1,5) ಅನ್ನು ಅದರ ರೇಖಾಕೃತಿ ಎಂದು ನೀಡುತ್ತದೆ. ಸ್ಕ್ಲಾಫ್ಲಿ ಗ್ರಾಫ್ ಒಂದು ಎಸ್ಆರ್ಜಿ (27,16,10,8) ಆಗಿದೆ. ಹಾಫ್ಮನ್-ಸಿಂಗ್ಲೆಟನ್ ಗ್ರಾಫ್ ಒಂದು ಎಸ್ಆರ್ಜಿ (50,7,0,1) ಆಗಿದೆ. ಸಿಮ್ಸ್-ಗ್ವಿರ್ಟ್ಜ್ ರೇಖಾಚಿತ್ರವು (56,10,0,2) ಆಗಿದೆ. M22 ಗ್ರಾಫ್ ಅಥವಾ ಮೆಸ್ನರ್ ಗ್ರಾಫ್ ಒಂದು srg (77,16,0,4) ಆಗಿದೆ. ಬ್ರೌವರ್-ಹೇಮರ್ಸ್ ಗ್ರಾಫ್ ಒಂದು ಎಸ್ಆರ್ಜಿ (81,20,1,6) ಆಗಿದೆ. ಹಿಗ್ಮನ್-ಸಿಮ್ಸ್ ಗ್ರಾಫ್ ಒಂದು ಎಸ್ಆರ್ಜಿ (100,22,0,6) ಆಗಿದೆ. ಸ್ಥಳೀಯ ಮೆಕ್ಲಾಫ್ಲಿನ್ ಗ್ರಾಫ್ ಒಂದು ಎಸ್ಆರ್ಜಿ (162,56,10,24) ಆಗಿದೆ. ಕ್ಯಾಮೆರಾನ್ ಗ್ರಾಫ್ ಒಂದು ಎಸ್. ಆರ್. ಜಿ. (239,30,9,3) ಆಗಿದೆ. ಬರ್ಲೆಕಾಂಪ್-ವ್ಯಾನ್ ಲಿಂಟ್-ಸೀಡೆಲ್ ಗ್ರಾಫ್ ಒಂದು ಎಸ್ಆರ್ಜಿ (243,22,1,2) ಆಗಿದೆ. ಮೆಕ್ಲಾಫ್ಲಿನ್ ಗ್ರಾಫ್ ಒಂದು ಎಸ್ಆರ್ಜಿ (275,112,30,56) ಆಗಿದೆ. q ಕ್ರಮದ ಪಾಲೆ ಗ್ರಾಫ್ ಒಂದು srg (q, (q−1)/2, (q−5)/4, (q−1)/4) ಆಗಿದೆ. ಅತ್ಯಂತ ಚಿಕ್ಕ ಪಾಲೆ ರೇಖಾಚಿತ್ರವು 5-ಚಕ್ರವಾಗಿದೆ (ಮೇಲಿನದು). ಸ್ವಯಂ-ಪೂರಕ ಆರ್ಕ್-ಟ್ರಾನ್ಸಿಟಿವ್ ಗ್ರಾಫ್ಗಳು ಬಲವಾಗಿ ನಿಯಮಿತವಾಗಿವೆ. ಗ್ರಾಫ್ ಮತ್ತು ಅದರ ಪೂರಕಗಳೆರಡೂ ಸಂಪರ್ಕಗೊಂಡಿದ್ದರೆ ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ ಅನ್ನು ಪ್ರಿಮಿಟಿವ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಮೇಲಿನ ಎಲ್ಲಾ ಗ್ರಾಫ್ಗಳು ಪ್ರಾಚೀನವಾಗಿವೆ, ಇಲ್ಲದಿದ್ದರೆ ಅಥವಾ. ಕಾನ್ವೇ ಅವರ 99-ಗ್ರಾಫ್ ಸಮಸ್ಯೆಯು ಒಂದು ಎಸ್. ಆರ್. ಜಿ. (99,14,1,2) ಅನ್ನು ನಿರ್ಮಿಸಲು ಕೇಳುತ್ತದೆ. ಈ ನಿಯತಾಂಕಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆಯೇ ಎಂಬುದು ತಿಳಿದಿಲ್ಲ, ಮತ್ತು ಜಾನ್ ಹಾರ್ಟನ್ ಕಾನ್ವೇ ಈ ಸಮಸ್ಯೆಯ ಪರಿಹಾರಕ್ಕಾಗಿ $1000 ಬಹುಮಾನವನ್ನು ನೀಡಿದರು. ತ್ರಿಕೋನ-ಮುಕ್ತ ರೇಖಾಚಿತ್ರಗಳು λ = 0 ಹೊಂದಿರುವ ಬಲವಾದ ನಿಯಮಿತ ರೇಖಾಚಿತ್ರಗಳು ತ್ರಿಕೋನ-ಮುಕ್ತವಾಗಿವೆ. 3ಕ್ಕಿಂತ ಕಡಿಮೆ ಶೃಂಗಗಳಲ್ಲಿರುವ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಎಲ್ಲಾ ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ಗಳನ್ನು ಹೊರತುಪಡಿಸಿ, ಮೊದಲು ಪಟ್ಟಿ ಮಾಡಲಾದ ಏಳು (ಪೆಂಟಗನ್, ಪೀಟರ್ಸನ್, ಕ್ಲೆಬ್ಷ್, ಹಾಫ್ಮನ್-ಸಿಂಗ್ಲೆಟನ್, ಗೆವರ್ಟ್ಜ್, ಮೆಸ್ನರ್-ಎಂ22, ಮತ್ತು ಹಿಗ್ಮನ್-ಸಿಮ್ಸ್) ಮಾತ್ರ ಪರಿಚಿತವಾಗಿವೆ. ಜಿಯೋಡೆಟಿಕ್ ಗ್ರಾಫ್ಗಳು ಪ್ರತಿ ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ ಜಿಯೋಡೆಟಿಕ್ ಗ್ರಾಫ್ ಆಗಿದೆ, ಇದರಲ್ಲಿ ಪ್ರತಿ ಎರಡು ಶೃಂಗಗಳು ವಿಶಿಷ್ಟವಾದ ತೂಕವಿಲ್ಲದ ಚಿಕ್ಕ ಮಾರ್ಗವನ್ನು ಹೊಂದಿವೆ. ತಿಳಿದಿರುವ ಏಕೈಕ ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳು 0 ಆಗಿವೆ, ಆದ್ದರಿಂದ ತ್ರಿಕೋನ-ಮುಕ್ತವಾಗಿವೆ. ಇವುಗಳನ್ನು ಮೂರ್ ಗ್ರಾಫ್ಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಕೆಳಗೆ ಹೆಚ್ಚು ವಿವರವಾಗಿ ಅನ್ವೇಷಿಸಲಾಗಿದೆ. (400,21,2,1) ನಂತಹ ಇತರ ನಿಯತಾಂಕಗಳ ಸಂಯೋಜನೆಯನ್ನು ಇನ್ನೂ ತಳ್ಳಿಹಾಕಲಾಗಿಲ್ಲ. ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ ಹೊಂದಿರುವ ಗುಣಲಕ್ಷಣಗಳ ಬಗ್ಗೆ ನಡೆಯುತ್ತಿರುವ ಸಂಶೋಧನೆಯ ಹೊರತಾಗಿಯೂ, ಯಾವುದಾದರೂ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆಯೇ ಅಥವಾ ಅವುಗಳ ಸಂಖ್ಯೆಯು ಸೀಮಿತವಾಗಿದೆಯೇ ಎಂಬುದು ತಿಳಿದಿಲ್ಲ. ಪ್ರಾಥಮಿಕ ಫಲಿತಾಂಶ ಮಾತ್ರ ತಿಳಿದಿದೆ, ಅದು ಅಂತಹ ಗ್ರಾಫ್ಗೆ 1 ಆಗಿರಬಾರದು. ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳ ಬೀಜಗಣಿತದ ಗುಣಲಕ್ಷಣಗಳು ನಿಯತಾಂಕಗಳ ನಡುವಿನ ಮೂಲಭೂತ ಸಂಬಂಧ ಎಸ್ಆರ್ಜಿ (v, k, λ, μ) ನಲ್ಲಿರುವ ನಾಲ್ಕು ನಿಯತಾಂಕಗಳು ಸ್ವತಂತ್ರವಾಗಿಲ್ಲ. ಅವರು ಈ ಕೆಳಗಿನ ಸಂಬಂಧವನ್ನು ಪಾಲಿಸಬೇಕುಃ ಮೇಲಿನ ಸಂಬಂಧವನ್ನು ಎಣಿಕೆಯ ವಾದದ ಮೂಲಕ ಈ ಕೆಳಗಿನಂತೆ ಪಡೆಯಲಾಗಿದೆಃ ಗ್ರಾಫ್ನ ಶೃಂಗಗಳು ಮೂರು ಹಂತಗಳಲ್ಲಿವೆ ಎಂದು ಊಹಿಸಿಕೊಳ್ಳಿ. ಮಟ್ಟ 0 ರಲ್ಲಿ ಯಾವುದೇ ಶೃಂಗವನ್ನು ಮೂಲವಾಗಿ ಆಯ್ಕೆ ಮಾಡಿ. ನಂತರ ಅದರ ಕೆ ನೆರೆಹೊರೆಯವರು ಹಂತ 1 ರಲ್ಲಿ ಇರುತ್ತಾರೆ, ಮತ್ತು ಎಲ್ಲಾ ಇತರ ಶೃಂಗಗಳು ಹಂತ 2 ರಲ್ಲಿರುತ್ತವೆ. ಹಂತ 1ರಲ್ಲಿರುವ ಶೃಂಗಗಳು ಮೂಲಕ್ಕೆ ನೇರವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿವೆ, ಆದ್ದರಿಂದ ಅವು ಮೂಲಕ್ಕೆ ಸಮಾನವಾದ ಇತರ ನೆರೆಹೊರೆಗಳನ್ನು ಹೊಂದಿರಬೇಕು, ಮತ್ತು ಈ ಸಾಮಾನ್ಯ ನೆರೆಹೊರೆಗಳು ಸಹ ಹಂತ 1ರಲ್ಲಿರಬೇಕು. ಪ್ರತಿ ಶೃಂಗವು ಡಿಗ್ರಿ k ಅನ್ನು ಹೊಂದಿರುವುದರಿಂದ, ಹಂತ 2 ರಲ್ಲಿ ಶೃಂಗಗಳಿಗೆ ಸಂಪರ್ಕಿಸಲು ಪ್ರತಿ ಹಂತ 1 ನೋಡ್ಗೆ ಅಂಚುಗಳು ಉಳಿದಿವೆ. ಆದ್ದರಿಂದ, ಹಂತ 1 ಮತ್ತು ಹಂತ 2ರ ನಡುವೆ ಅಂಚುಗಳಿವೆ. ಹಂತ 2ರಲ್ಲಿರುವ ಶೃಂಗಗಳು ಮೂಲಕ್ಕೆ ನೇರವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿಲ್ಲ, ಆದ್ದರಿಂದ ಅವು ಮೂಲದೊಂದಿಗೆ ಸಾಮಾನ್ಯ ನೆರೆಹೊರೆಯವರನ್ನು ಹೊಂದಿರಬೇಕು, ಮತ್ತು ಈ ಸಾಮಾನ್ಯ ನೆರೆಹೊರೆಯವರೆಲ್ಲರೂ ಹಂತ 1ರಲ್ಲಿರಬೇಕು. ಹಂತ 2 ರಲ್ಲಿ ಶೃಂಗಗಳಿವೆ, ಮತ್ತು ಪ್ರತಿಯೊಂದೂ ಹಂತ 1 ರಲ್ಲಿ μ ಶೃಂಗಗಳಿಗೆ ಸಂಪರ್ಕ ಹೊಂದಿದೆ. ಆದ್ದರಿಂದ ಹಂತ 1 ಮತ್ತು ಹಂತ 2 ರ ನಡುವಿನ ಅಂಚುಗಳ ಸಂಖ್ಯೆ. ಹಂತ 1 ಮತ್ತು ಹಂತ 2 ರ ನಡುವಿನ ಅಂಚುಗಳಿಗೆ ಎರಡು ಅಭಿವ್ಯಕ್ತಿಗಳನ್ನು ಸಮೀಕರಿಸುವುದರಿಂದ, ಸಂಬಂಧವು ಅನುಸರಿಸುತ್ತದೆ. ಹೊಂದಾಣಿಕೆಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಸಮೀಕರಣಗಳು I ಐಡೆಂಟಿಟಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಸೂಚಿಸೋಣ ಮತ್ತು J ಒಂದರ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಸೂಚಿಸೋಣ, ಎರಡೂ ಕ್ರಮಗಳ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳು v. ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ನ ಹೊಂದಾಣಿಕೆಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ A ಎರಡು ಸಮೀಕರಣಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ. ಮೊದಲನೆಯದುಃ ಇದು ನಿಯಮಿತತೆಯ ಅವಶ್ಯಕತೆಯ ಪುನರಾವರ್ತನೆಯಾಗಿದೆ. ಇದು k ಎಂಬುದು ಆಲ್-ಒನ್ಸ್ ಐಗನ್ವೆಕ್ಟರ್ನೊಂದಿಗೆ ಹೊಂದಿಕೊಂಡಿರುವ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಐಗನ್ ಮೌಲ್ಯವಾಗಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಎರಡನೆಯದುಃ ಇದು ಬಲವಾದ ಕ್ರಮಬದ್ಧತೆಯನ್ನು ವ್ಯಕ್ತಪಡಿಸುತ್ತದೆ. ಎಡಭಾಗದ ಐಜ್-th ಅಂಶವು ಐ ನಿಂದ ಜೆ ಗೆ ಎರಡು-ಹಂತದ ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ನೀಡುತ್ತದೆ. ಬಲಭಾಗದ ಮೊದಲ ಪದವು i ಯಿಂದ i ಗೆ ಎರಡು-ಹಂತದ ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ನೀಡುತ್ತದೆ, ಅವುಗಳೆಂದರೆ k ಅಂಚುಗಳು ಹೊರಕ್ಕೆ ಮತ್ತು ಹಿಂಭಾಗಕ್ಕೆ. ಎರಡನೇ ಪದವು i ಮತ್ತು j ಅನ್ನು ನೇರವಾಗಿ ಸಂಪರ್ಕಿಸಿದಾಗ ಎರಡು-ಹಂತದ ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ನೀಡುತ್ತದೆ. ಐ ಮತ್ತು ಜೆ ಸಂಪರ್ಕ ಹೊಂದಿರದಿದ್ದಾಗ ಮೂರನೇ ಪದವು ಅನುಗುಣವಾದ ಮೌಲ್ಯವನ್ನು ನೀಡುತ್ತದೆ. ಈ ಮೂರು ಪ್ರಕರಣಗಳು ಪರಸ್ಪರ ಪ್ರತ್ಯೇಕವಾಗಿರುವುದರಿಂದ ಮತ್ತು ಒಟ್ಟಾರೆಯಾಗಿ ಸಮಗ್ರವಾಗಿರುವುದರಿಂದ, ಸರಳ ಸಂಯೋಜಕ ಸಮಾನತೆಯು ಅನುಸರಿಸುತ್ತದೆ. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ಮೇಲಿನ ಎರಡೂ ಷರತ್ತುಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಮತ್ತು ಸಂಪೂರ್ಣ ಅಥವಾ ಶೂನ್ಯ ಗ್ರಾಫ್ ಅಲ್ಲದ ಗ್ರಾಫ್ ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ ಆಗಿದೆ. ಐಗನ್ ಮೌಲ್ಯಗಳು ಮತ್ತು ಗ್ರಾಫ್ ಸ್ಪೆಕ್ಟ್ರಮ್ ಅಡ್ಜಸೆನ್ಸಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಎ ಸಮ್ಮಿತೀಯವಾಗಿರುವುದರಿಂದ, ಅದರ ಐಗನ್ ವೆಕ್ಟರ್ಗಳು ಆರ್ಥೋಗೋನಲ್ ಆಗಿವೆ. ನಾವು ಈಗಾಗಲೇ ಒಂದು ಐಗನ್ ವೆಕ್ಟರ್ ಅನ್ನು ಗಮನಿಸಿದ್ದೇವೆ, ಅದು ಮೇಲಿನ ಎಲ್ಲಾ ಐಗನ್ ವೆಕ್ಟರ್ಗಳಿಂದ ಮಾಡಲ್ಪಟ್ಟಿದೆ, ಇದು ಐಗನ್ ಮೌಲ್ಯ k ಗೆ ಅನುಗುಣವಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ಇತರ ಐಗನ್ ವೆಕ್ಟರ್ಗಳು x ಅನ್ನು ಪೂರೈಸಬೇಕು, ಅಲ್ಲಿ J ಮೊದಲಿನಂತೆಯೇ ಆಲ್-ಒನ್ಸ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದೆ. ಹಿಂದೆ ಸ್ಥಾಪಿಸಲಾದ ಸಮೀಕರಣವನ್ನು ತೆಗೆದುಕೊಳ್ಳಿಃ ಮತ್ತು ಮೇಲಿನ ಸಮೀಕರಣವನ್ನು ಐಗನ್ ವೆಕ್ಟರ್ x ನಿಂದ ಗುಣಿಸಿಃ ಅನುಗುಣವಾದ ಐಗನ್ ಮೌಲ್ಯವನ್ನು p ಎಂದು ಕರೆಯಿರಿ (ಗ್ರಾಫ್ ನಿಯತಾಂಕದೊಂದಿಗೆ ಗೊಂದಲಕ್ಕೀಡಾಗಬಾರದು) ಮತ್ತು ಪರ್ಯಾಯವಾಗಿ, ಮತ್ತುಃ x ಅನ್ನು ತೆಗೆದುಹಾಕಿ ಮತ್ತು ಚತುರ್ಭುಜವನ್ನು ಪಡೆಯಲು ಮರುಹೊಂದಿಸಿಃ ಇದು ಎರಡು ಹೆಚ್ಚುವರಿ ಐಗನ್ ಮೌಲ್ಯಗಳನ್ನು ನೀಡುತ್ತದೆ. ಹೀಗಾಗಿ ಬಲವಾದ ನಿಯಮಿತ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗೆ ನಿಖರವಾಗಿ ಮೂರು ಐಗನ್ ಮೌಲ್ಯಗಳಿವೆ. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ಕೇವಲ ಮೂರು ಐಗನ್ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿರುವ ಸಂಪರ್ಕಿತ ನಿಯಮಿತ ಗ್ರಾಫ್ ಬಲವಾಗಿ ನಿಯಮಿತವಾಗಿದೆ. ಹೆಚ್ಚಿನ ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ ಸಾಹಿತ್ಯದಲ್ಲಿ ಪರಿಭಾಷೆಯನ್ನು ಅನುಸರಿಸಿ, ದೊಡ್ಡ ಐಗನ್ ಮೌಲ್ಯವನ್ನು f ಗುಣಾಕಾರದೊಂದಿಗೆ r ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಚಿಕ್ಕದನ್ನು g ಗುಣಾಕಾರದೊಂದಿಗೆ s ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಎಲ್ಲಾ ಐಗನ್ ಮೌಲ್ಯಗಳ ಮೊತ್ತವು ಪಕ್ಕದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನ ಕುರುಹಾಗಿರುವುದರಿಂದ, ಇದು ಈ ಸಂದರ್ಭದಲ್ಲಿ ಶೂನ್ಯವಾಗಿರುತ್ತದೆ, ಆಯಾ ಗುಣಾಕಾರಗಳನ್ನು f ಮತ್ತು g ಅನ್ನು ಲೆಕ್ಕ ಹಾಕಬಹುದುಃ ಐಗನ್ ಮೌಲ್ಯ k ಗುಣಾಕಾರ 1 ಅನ್ನು ಹೊಂದಿದೆ. ಐಗನ್ ಮೌಲ್ಯವು ಬಹುಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿದೆ. ಐಗನ್ ಮೌಲ್ಯವು ಬಹುಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿದೆ. ಗುಣಾಕಾರಗಳು ಪೂರ್ಣಾಂಕಗಳಾಗಿರುವುದರಿಂದ, ಅವುಗಳ ಅಭಿವ್ಯಕ್ತಿಗಳು v, k, μ ಮತ್ತು λ ಮೌಲ್ಯಗಳ ಮೇಲೆ ಮತ್ತಷ್ಟು ನಿರ್ಬಂಧಗಳನ್ನು ಒದಗಿಸುತ್ತವೆ. ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳು ಅಸಮಾನ ಗುಣಾಕಾರಗಳೊಂದಿಗೆ ಪೂರ್ಣಾಂಕ ಐಗನ್ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿವೆ. ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳನ್ನು ಸಮ್ಮಿತೀಯ ಕಾನ್ಫರೆನ್ಸ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳೊಂದಿಗಿನ ಸಂಪರ್ಕದಿಂದಾಗಿ ಕಾನ್ಫರೆನ್ಸ್ ಗ್ರಾಫ್ಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಅವುಗಳ ನಿಯತಾಂಕಗಳು ಅವುಗಳ ಐಗನ್ ಮೌಲ್ಯಗಳು ಮತ್ತು, ಇವೆರಡರ ಗುಣಾಕಾರಗಳು ಸಮಾನವಾಗಿರುತ್ತವೆ. ಇದಲ್ಲದೆ, ಈ ಸಂದರ್ಭದಲ್ಲಿ, ವಿ ಎರಡು ವರ್ಗಗಳ ಮೊತ್ತಕ್ಕೆ ಸಮನಾಗಿರಬೇಕು, ಇದು ಬ್ರೂಕ್-ರೈಸರ್-ಚೌಲಾ ಪ್ರಮೇಯಕ್ಕೆ ಸಂಬಂಧಿಸಿದೆ. ಐಗನ್ ಮೌಲ್ಯಗಳು ಮತ್ತು ಅವುಗಳ ಗುಣಾಕಾರಗಳ ಹೆಚ್ಚಿನ ಗುಣಲಕ್ಷಣಗಳು ಹೀಗಿವೆಃ, ಆದ್ದರಿಂದ ಐಗನ್ ಮೌಲ್ಯಗಳು r ಮತ್ತು s ನೊಂದಿಗೆ ನೀಡಲಾದರೆ, ಅದರ ಪೂರಕವು ಐಗನ್ ಮೌಲ್ಯಗಳು-1-s ಮತ್ತು-1-r ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಂದು ಪರಿಣಾಮವಾಗಿ, ಕೆಲವು ಕ್ರಮದಲ್ಲಿ ಇದ್ದರೆ ಮತ್ತು ಮಾತ್ರ. ಕ್ರೇನ್ ಷರತ್ತುಗಳುಃ ಮತ್ತು ಸಂಪೂರ್ಣ ಬದ್ಧಃ ಮತ್ತು. ಪಂಜದ ಬಂಧಃ ವೇಳೆ, ನಂತರ ಅಥವಾ. ಯಾವುದೇ ನಿಯತಾಂಕಗಳ ಗುಂಪಿಗೆ ಮೇಲಿನ ಷರತ್ತುಗಳನ್ನು ಉಲ್ಲಂಘಿಸಿದರೆ, ಆ ನಿಯತಾಂಕಗಳಿಗೆ ಯಾವುದೇ ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ. ಅಸ್ತಿತ್ವದಲ್ಲಿರದ ಕಾರಣಗಳು ಯಾವುದಾದರೂ ಇದ್ದರೆ, ಅವುಗಳಂತಹ ಅಸ್ತಿತ್ವ ಅಥವಾ ಅಸ್ತಿತ್ವವಿಲ್ಲದ ಪಟ್ಟಿಗಳನ್ನು ಬ್ರೌವರ್ ಇಲ್ಲಿ ಸಂಗ್ರಹಿಸಿದ್ದಾರೆ. ಮೇಲೆ ತಿಳಿಸಿದಂತೆ, ಹಾಫ್ಮನ್-ಸಿಂಗ್ಲೆಟನ್ ಪ್ರಮೇಯವು ಪೂರ್ಣಾಂಕಗಳಾಗಿರಬೇಕಾದ ಐಗನ್ ಮೌಲ್ಯಗಳ ಗುಣಾಕಾರಗಳನ್ನು ನೀಡುತ್ತದೆ. 1960ರಲ್ಲಿ, ಅಲನ್ ಹಾಫ್ಮನ್ ಮತ್ತು ರಾಬರ್ಟ್ ಸಿಂಗಲ್ಟನ್ ಅವರು λ = 0 ಮತ್ತು μ = 1 ಹೊಂದಿರುವ ಮೂರ್ ಗ್ರಾಫ್ಗಳ ಮೇಲೆ ಅನ್ವಯಿಸಿದಾಗ ಆ ಅಭಿವ್ಯಕ್ತಿಗಳನ್ನು ಪರಿಶೀಲಿಸಿದರು. ಅಂತಹ ನಕ್ಷೆಗಳು ತ್ರಿಕೋನಗಳಿಂದ ಮುಕ್ತವಾಗಿರುತ್ತವೆ (ಇಲ್ಲದಿದ್ದರೆ λ ಶೂನ್ಯವನ್ನು ಮೀರುತ್ತದೆ) ಮತ್ತು ಚತುರ್ಭುಜಗಳು (ಇಲ್ಲದಿದ್ದರೆ μ 1 ಅನ್ನು ಮೀರುತ್ತದೆ), ಆದ್ದರಿಂದ ಅವು 5 ರ ಸುತ್ತಳತೆ (ಚಿಕ್ಕ ಚಕ್ರ ಉದ್ದ) ಹೊಂದಿರುತ್ತವೆ. ಸಮೀಕರಣದಲ್ಲಿ λ ಮತ್ತು μ ಮೌಲ್ಯಗಳನ್ನು ಬದಲಿಸಿದರೆ, ಅದನ್ನು ಕಾಣಬಹುದು, ಮತ್ತು ಐಗನ್ ಮೌಲ್ಯದ ಗುಣಾಕಾರಗಳು ಕಡಿಮೆಯಾಗುತ್ತವೆ ಗುಣಾಕಾರಗಳು ಪೂರ್ಣಾಂಕಗಳಾಗಬೇಕಾದರೆ, ಪ್ರಮಾಣವು ತರ್ಕಬದ್ಧವಾಗಿರಬೇಕು, ಆದ್ದರಿಂದ ಅಂಶವು ಶೂನ್ಯವಾಗಿರುತ್ತದೆ ಅಥವಾ ಛೇದವು ಪೂರ್ಣಾಂಕವಾಗಿರುತ್ತದೆ. ಅಂಶವು ಶೂನ್ಯವಾಗಿದ್ದರೆ, ಸಂಭವನೀಯತೆಗಳೆಂದರೆಃ k = 0 ಮತ್ತು v = 1 ಒಂದು ಶೃಂಗದೊಂದಿಗೆ ಮತ್ತು ಯಾವುದೇ ಅಂಚುಗಳಿಲ್ಲದ ಕ್ಷುಲ್ಲಕ ರೇಖಾಚಿತ್ರವನ್ನು ನೀಡುತ್ತದೆ, ಮತ್ತು k = 2 ಮತ್ತು v = 5 ಸಾಮಾನ್ಯವಾಗಿ ನಿಯಮಿತ ಪಂಚಭುಜವಾಗಿ ಚಿತ್ರಿಸಲಾದ 5-ಅಕ್ಷೀಯ ಚಕ್ರ ರೇಖಾಚಿತ್ರವನ್ನು ನೀಡುತ್ತದೆ. ಛೇದವು ಪೂರ್ಣಾಂಕ t ಆಗಿದ್ದರೆ, ಅದು ಪರಿಪೂರ್ಣ ವರ್ಗವಾಗಿರುತ್ತದೆ. ಬದಲಿಸುವುದುಃ ಎರಡೂ ಬದಿಗಳು ಪೂರ್ಣಾಂಕಗಳಾಗಿರುವುದರಿಂದ, ಪೂರ್ಣಾಂಕವಾಗಿರಬೇಕು, ಆದ್ದರಿಂದ t ಎಂಬುದು 15ರ ಅಂಶವಾಗಿದೆ, ಅಂದರೆ. ಪ್ರತಿಯಾಗಿಃ k = 1 ಮತ್ತು v = 2 ಒಂದು ತುದಿಯಿಂದ ಜೋಡಿಸಲಾದ ಎರಡು ಶೃಂಗಗಳ ಕ್ಷುಲ್ಲಕ ಗ್ರಾಫ್ ಅನ್ನು ನೀಡುತ್ತದೆ, k = 3 ಮತ್ತು v = 10 ಪೀಟರ್ಸನ್ ಗ್ರಾಫ್ ಅನ್ನು ನೀಡುತ್ತದೆ, k = 7 ಮತ್ತು v = 50 ಈ ವಿಶ್ಲೇಷಣೆಯ ಸಮಯದಲ್ಲಿ ಹಾಫ್ಮನ್ ಮತ್ತು ಸಿಂಗಲ್ಟನ್ ಕಂಡುಹಿಡಿದ ಹಾಫ್ಮನ್-ಸಿಂಗ್ಲೆಟನ್ ಗ್ರಾಫ್ ಅನ್ನು ನೀಡುತ್ತದೆ, ಮತ್ತು k = 57 ಮತ್ತು v = 3250 1960 ರಿಂದ ಕಂಡುಹಿಡಿಯದ ಅಥವಾ ಅದರ ಅಸ್ತಿತ್ವವನ್ನು ನಿರಾಕರಿಸದ ಪ್ರಸಿದ್ಧ ಗ್ರಾಫ್ ಅನ್ನು ಊಹಿಸುತ್ತದೆ. ಹಾಫ್ಮನ್-ಸಿಂಗ್ಲೆಟನ್ ಪ್ರಮೇಯವು ಮೇಲೆ ಪಟ್ಟಿ ಮಾಡಲಾದವುಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಯಾವುದೇ ಬಲವಾದ ನಿಯಮಿತ ಸುತ್ತಳತೆ-5 ಮೂರ್ ಗ್ರಾಫ್ಗಳಿಲ್ಲ ಎಂದು ಹೇಳುತ್ತದೆ. ಭಾಗಶಃ ರೇಖಾಗಣಿತ ಸೀಡೆಲ್ ಅಡ್ಜಸೆನ್ಸಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಎರಡು-ಗ್ರಾಫ್ ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು ಆಂಡ್ರೀಸ್ ಬ್ರೌವರ್ ಮತ್ತು ಹೆಂಡ್ರಿಕ್ ವ್ಯಾನ್ ಮಾಲ್ಡೆಘೆಮ್ (2022), ಸ್ಟ್ರಾಂಗ್ಲಿ ರೆಗ್ಯುಲರ್ ಗ್ರಾಫ್ಗಳನ್ನು ಸಹ ನೋಡಿ. ಕೇಂಬ್ರಿಡ್ಜ್ಃ ಕೇಂಬ್ರಿಡ್ಜ್ ಯೂನಿವರ್ಸಿಟಿ ಪ್ರೆಸ್. .. ಎ. ಇ. ಬ್ರೌವರ್, ಎ. ಎಮ್. ಕೋಹೆನ್, ಮತ್ತು ಎ. ನ್ಯೂಮೇಯರ್ (1989), ಡಿಸ್ಟೆನ್ಸ್ ರೆಗ್ಯುಲರ್ ಗ್ರಾಫ್ಸ್. ಬರ್ಲಿನ್, ನ್ಯೂಯಾರ್ಕ್ಃ ಸ್ಪ್ರಿಂಗರ್-ವೆರ್ಲಾಗ್. , ಕ್ರಿಸ್ ಗಾಡ್ಸಿಲ್ ಮತ್ತು ಗಾರ್ಡನ್ ರಾಯ್ಲ್ (2004), ಆಲ್ಜಿಬ್ರಾಯಿಕ್ ಗ್ರಾಫ್ ಥಿಯರಿ. ನ್ಯೂಯಾರ್ಕ್ಃ ಸ್ಪ್ರಿಂಗರ್-ವೆರ್ಲಾಗ್. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಎರಿಕ್ ಡಬ್ಲ್ಯೂ. ವೈಸ್ಸ್ಟೀನ್, ಮ್ಯಾಥ್ ವರ್ಲ್ಡ್ ಲೇಖನವು ಹಲವಾರು ಉದಾಹರಣೆಗಳೊಂದಿಗೆ. ಗಾರ್ಡನ್ ರಾಯ್ಲ್, ದೊಡ್ಡ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಕುಟುಂಬಗಳ ಪಟ್ಟಿ. ಆಂಡ್ರೀಸ್ ಇ. ಬ್ರೌವರ್, ಸ್ಟ್ರಾಂಗ್ಲಿ ರೆಗ್ಯುಲರ್ ಗ್ರಾಫ್ಗಳ ನಿಯತಾಂಕಗಳು. ಬ್ರೆಂಡನ್ ಮೆಕ್ಕೇ, ಗ್ರಾಫ್ಗಳ ಕೆಲವು ಸಂಗ್ರಹಗಳು. ಟೆಡ್ ಸ್ಪೆನ್ಸ್, ಗರಿಷ್ಠ 64 ಶೃಂಗಗಳಲ್ಲಿ ಬಲವಾಗಿ ನಿಯಮಿತವಾದ ರೇಖಾಚಿತ್ರಗಳು. ಗ್ರಾಫ್ ಕುಟುಂಬಗಳು ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳು