Frucht's theorem
ಫ್ರುಕ್ಟ್ನ ಪ್ರಮೇಯವು 1936ರಲ್ಲಿ ಡೆನೆಸ್ ಕಾನಿಗ್ ಊಹಿಸಿದ ಮತ್ತು 1939ರಲ್ಲಿ ರಾಬರ್ಟ್ ಫ್ರುಕ್ಟ್ನಿಂದ ಸಾಬೀತಾದ ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿನ ಒಂದು ಪ್ರಮೇಯವಾಗಿದೆ. ಪ್ರತಿ ಸೀಮಿತ ಗುಂಪು ಒಂದು ಸೀಮಿತ ನಿರ್ದೇಶಿಸದ ರೇಖಾಚಿತ್ರದ ಸಮ್ಮಿತಿಗಳ ಗುಂಪು ಎಂದು ಅದು ಹೇಳುತ್ತದೆ. ಹೆಚ್ಚು ಬಲವಾಗಿ, ಯಾವುದೇ ಸೀಮಿತ ಗುಂಪು G ಗೆ ಅನಂತವಾದ ಅನೇಕ ಏಕರೂಪವಲ್ಲದ ಸರಳ ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿವೆ, ಅವುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದರ ಆಟೋಮಾರ್ಫಿಸಂ ಗುಂಪು G ಗೆ ಐಸೋಮಾರ್ಫಿಕ್ ಆಗಿದೆ. ಪ್ರೂಫ್ ಐಡಿಯಾ ಪುರಾವೆಯ ಮುಖ್ಯ ಉದ್ದೇಶವೆಂದರೆ G ಯ ಕೇಲೆ ಗ್ರಾಫ್, G ಯ ಜನರೇಟರ್ಗಳನ್ನು ಪರಸ್ಪರ ಪ್ರತ್ಯೇಕಿಸಲು ಅದರ ಅಂಚುಗಳ ಮೇಲೆ ಬಣ್ಣಗಳು ಮತ್ತು ದೃಷ್ಟಿಕೋನಗಳನ್ನು ಸೇರಿಸುವುದರೊಂದಿಗೆ, ಅಪೇಕ್ಷಿತ ಆಟೋಮಾರ್ಫಿಸಂ ಗುಂಪನ್ನು ಹೊಂದಿದೆ. ಆದ್ದರಿಂದ, ಈ ಪ್ರತಿಯೊಂದು ಅಂಚುಗಳನ್ನು ಸೂಕ್ತವಾದ ಉಪಗ್ರ್ಯಾಫ್ನಿಂದ ಬದಲಾಯಿಸಿದರೆ, ಪ್ರತಿ ಬದಲಿ ಉಪಗ್ರ್ಯಾಫ್ ಸ್ವತಃ ಅಸಮ್ಮಿತವಾಗಿದ್ದರೆ ಮತ್ತು ಎರಡು ಬದಲಿಗಳು ಒಂದೇ ಬಣ್ಣದ ಅಂಚುಗಳನ್ನು ಬದಲಾಯಿಸಿದರೆ ಮಾತ್ರ ಐಸೊಮಾರ್ಫಿಕ್ ಆಗಿದ್ದರೆ, ಈ ಬದಲಿಗಳನ್ನು ನಿರ್ವಹಿಸುವ ಮೂಲಕ ರಚಿಸಲಾದ ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ ಸಹ ಅದರ ಸಮ್ಮಿತಿ ಗುಂಪಾಗಿ ಜಿ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಗ್ರಾಫ್ ಗಾತ್ರ ಮೂರು ವಿನಾಯಿತಿಗಳೊಂದಿಗೆ-3,4 ಮತ್ತು 5 ಕ್ರಮಗಳ ಆವರ್ತಕ ಗುಂಪುಗಳು-ಪ್ರತಿ ಗುಂಪನ್ನು ಗ್ರಾಫ್ನ ಸಮ್ಮಿತಿಗಳಾಗಿ ಪ್ರತಿನಿಧಿಸಬಹುದು, ಅದರ ಶೃಂಗಗಳು ಕೇವಲ ಎರಡು ಕಕ್ಷೆಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಆದ್ದರಿಂದ, ಗ್ರಾಫ್ನಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯು ಗುಂಪಿನ ಕ್ರಮಕ್ಕಿಂತ ಗರಿಷ್ಠ ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ವಿನಾಯಿತಿಗಳ ದೊಡ್ಡ ಗುಂಪಿನೊಂದಿಗೆ, ಹೆಚ್ಚಿನ ಸೀಮಿತ ಗುಂಪುಗಳನ್ನು ಗುಂಪಿನ ಕ್ರಮಕ್ಕೆ ಸಮಾನವಾದ ಹಲವಾರು ಶೃಂಗಗಳೊಂದಿಗೆ ಶೃಂಗ-ಪರಿವರ್ತಕ ಗ್ರಾಫ್ನ ಸಮ್ಮಿತಿಗಳಾಗಿ ಪ್ರತಿನಿಧಿಸಬಹುದು. ಕೆಲವು ನಿರ್ಬಂಧಿತ ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಗಳು ಯಾವುದೇ ಸಮ್ಮಿತಿ ಗುಂಪನ್ನು ಅರಿತುಕೊಳ್ಳಲು ಇನ್ನೂ ಸಾಕಷ್ಟು ಗ್ರಾಫ್ಗಳನ್ನು ಹೊಂದಿವೆ ಎಂದು ತೋರಿಸುವ ಫ್ರುಕ್ಟ್ನ ಪ್ರಮೇಯದ ಬಲವಾದ ಆವೃತ್ತಿಗಳಿವೆ. ವಾಸ್ತವವಾಗಿ ಬಯಸಿದ ಗುಣಲಕ್ಷಣಗಳೊಂದಿಗೆ ಅನೇಕ 3-ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳು ಅಸ್ತಿತ್ವದಲ್ಲಿವೆ ಎಂದು ಫ್ರುಕ್ಟ್ ಸಾಬೀತುಪಡಿಸಿದರು; ಉದಾಹರಣೆಗೆ, ಫ್ರುಕ್ಟ್ ಗ್ರಾಫ್, 12 ಶೃಂಗಗಳು ಮತ್ತು 18 ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ 3-ನಿಯಮಿತ ಗ್ರಾಫ್, ಯಾವುದೇ ಕ್ಷುಲ್ಲಕವಲ್ಲದ ಸಮ್ಮಿತಿಗಳನ್ನು ಹೊಂದಿಲ್ಲ, ಇದು ಕ್ಷುಲ್ಲಕ ಗುಂಪಿಗೆ ಈ ರೀತಿಯ ಸಾಕ್ಷಾತ್ಕಾರವನ್ನು ಒದಗಿಸುತ್ತದೆ. ಯಾವುದೇ ಗುಂಪನ್ನು ಎಲ್ಲಾ ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕ ಮೌಲ್ಯಗಳಾದ k ಗೆ (ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳಿಗೆ ಮತ್ತು k-ವರ್ಣ ಗ್ರಾಫ್ಗಳಿಗೆ) ಅನೇಕ ವಿಭಿನ್ನವಾದ k-ನಿಯಮಿತ ಗ್ರಾಫ್ಗಳು, k-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ಗಳು ಅಥವಾ k-ವರ್ಣ ಗ್ರಾಫ್ಗಳ ಸಮ್ಮಿತಿ ಗುಂಪುಗಳಾಗಿ ಅರಿತುಕೊಳ್ಳಬಹುದು ಎಂದು ಗೆರ್ಟ್ ಸಬಿಡುಸ್ಸಿ ತೋರಿಸಿದರು. ಪ್ರತಿ ರೇಖಾಚಿತ್ರವನ್ನು ಅದರ ಅಂಚುಗಳು ಮತ್ತು ಶೃಂಗಗಳ ಧಾರಕ ಭಾಗಶಃ ಕ್ರಮದಿಂದ ಪುನರ್ನಿರ್ಮಿಸಬಹುದು, ಪ್ರತಿ ಸೀಮಿತ ಭಾಗಶಃ ಕ್ರಮವು ಬಿರ್ಖೋಫ್ನ ಪ್ರಾತಿನಿಧ್ಯ ಪ್ರಮೇಯದಿಂದ ಸೀಮಿತ ವಿತರಣಾ ಜಾಲರಿಯೊಂದಿಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಎಂಬ ಅಂಶಗಳಿಂದ, ಪ್ರತಿ ಸೀಮಿತ ಗುಂಪನ್ನು ವಿತರಣಾ ಜಾಲರಿಯ ಸಮ್ಮಿತಿಗಳಾಗಿ ಮತ್ತು ಜಾಲರಿಯ ರೇಖಾಚಿತ್ರದ ಮಧ್ಯಮ ರೇಖಾಚಿತ್ರವಾಗಿ ಅರಿತುಕೊಳ್ಳಬಹುದು. ಪ್ರತಿ ಸೀಮಿತ ಗುಂಪನ್ನು ಬಲವಾದ ನಿಯಮಿತ ಗ್ರಾಫ್ನ ಸಮ್ಮಿತಿಗಳ ಗುಂಪಾಗಿ ಅರಿತುಕೊಳ್ಳಲು ಸಾಧ್ಯವಿದೆ. ಪ್ರತಿ ಸೀಮಿತ ಗುಂಪನ್ನು ಎರಡು ಸಂಖ್ಯೆಯನ್ನು ಪ್ರತ್ಯೇಕಿಸುವ ಗ್ರಾಫ್ನ ಸಮ್ಮಿತಿಗಳಾಗಿ ಸಹ ಅರಿತುಕೊಳ್ಳಬಹುದುಃ ಗ್ರಾಫ್ನ ಯಾವುದೇ ಸಮ್ಮಿತಿಗಳು ಬಣ್ಣವನ್ನು ಕಾಪಾಡಿಕೊಳ್ಳದಂತೆ ಒಬ್ಬರು (ಅಸಮರ್ಪಕವಾಗಿ) ಗ್ರಾಫನ್ನು ಎರಡು ಬಣ್ಣಗಳಿಂದ ಬಣ್ಣ ಮಾಡಬಹುದು. ಆದಾಗ್ಯೂ, ಗ್ರಾಫ್ಗಳ ಕೆಲವು ಪ್ರಮುಖ ವರ್ಗಗಳು ಎಲ್ಲಾ ಗುಂಪುಗಳನ್ನು ಅವುಗಳ ಸಮ್ಮಿತಿಗಳಾಗಿ ಅರಿತುಕೊಳ್ಳಲು ಅಸಮರ್ಥವಾಗಿವೆ. ಕ್ಯಾಮಿಲ್ಲೆ ಜೋರ್ಡಾನ್ ಮರಗಳ ಸಮ್ಮಿತಿ ಗುಂಪುಗಳನ್ನು ಕ್ಷುಲ್ಲಕ ಗುಂಪನ್ನು ಹೊಂದಿರುವ ಸೀಮಿತ ಗುಂಪುಗಳ ಚಿಕ್ಕ ಗುಂಪು ಎಂದು ನಿರೂಪಿಸಿದ್ದಾರೆ ಮತ್ತು ಪರಸ್ಪರ ನೇರ ಉತ್ಪನ್ನಗಳ ಅಡಿಯಲ್ಲಿ ಮುಚ್ಚಲಾಗಿದೆ ಮತ್ತು ಸಮ್ಮಿತೀಯ ಗುಂಪುಗಳೊಂದಿಗೆ ಹೂವಿನ ಉತ್ಪನ್ನಗಳು; ನಿರ್ದಿಷ್ಟವಾಗಿ, ಮೂರು ಕ್ರಮದ ಆವರ್ತಕ ಗುಂಪು ಮರದ ಸಮ್ಮಿತಿ ಗುಂಪಲ್ಲ. ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು ಎಲ್ಲಾ ಗುಂಪುಗಳನ್ನು ಅವುಗಳ ಸಮ್ಮಿತಿಗಳಾಗಿ ಅರಿತುಕೊಳ್ಳುವ ಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ; ಉದಾಹರಣೆಗೆ, ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳ ಸಮ್ಮಿತಿಗಳಾಗಿರುವ ಏಕೈಕ ಸೀಮಿತ ಸರಳ ಗುಂಪುಗಳು ಆವರ್ತಕ ಗುಂಪುಗಳು ಮತ್ತು ಪರ್ಯಾಯ ಗುಂಪುಗಳಾಗಿವೆ. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ಪ್ರತಿ ಸಣ್ಣ-ಮುಚ್ಚಿದ ಗ್ರಾಫ್ ಕುಟುಂಬವು ಎಲ್ಲಾ ಸೀಮಿತ ಗುಂಪುಗಳನ್ನು ಅದರ ಗ್ರಾಫ್ಗಳ ಸಮ್ಮಿತಿಗಳಿಂದ ಪ್ರತಿನಿಧಿಸಲು ಅಸಮರ್ಥವಾಗಿದೆ. ಲಾಸ್ಲೋ ಬಾಬಾಯ್, ಹೆಚ್ಚು ಬಲವಾಗಿ, ಪ್ರತಿ ಸಣ್ಣ-ಮುಚ್ಚಿದ ಕುಟುಂಬವು ಸೀಮಿತವಾಗಿ ಅನೇಕ ಆವರ್ತಕವಲ್ಲದ ಸೀಮಿತ ಸರಳ ಗುಂಪುಗಳನ್ನು ಮಾತ್ರ ಪ್ರತಿನಿಧಿಸಬಹುದು ಎಂದು ಊಹಿಸಿದ್ದಾರೆ. ಅನಂತ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಗುಂಪುಗಳಾದ ಇಜ್ಬಿಕ್ಕಿ 1959 ರಲ್ಲಿ ಈ ಫಲಿತಾಂಶಗಳನ್ನು ವಿಸ್ತರಿಸಿದರು ಮತ್ತು ಯಾವುದೇ ಸೀಮಿತ ಸಮ್ಮಿತಿ ಗುಂಪನ್ನು ಅರಿತುಕೊಳ್ಳುವ ಅಸಂಖ್ಯಾತ ಅನಂತ ಗ್ರಾಫ್ಗಳಿವೆ ಎಂದು ತೋರಿಸಿದರು. ಅಂತಿಮವಾಗಿ, ಜೋಹಾನ್ಸ್ ಡಿ ಗ್ರೂಟ್ ಮತ್ತು ಸಬಿಡುಸ್ಸಿ ಅವರು 1959/1960 ನಲ್ಲಿ ಯಾವುದೇ ಗುಂಪನ್ನು (ಗುಂಪು ಸೀಮಿತವಾಗಿದೆ ಎಂಬ ಊಹೆಯನ್ನು ಬಿಟ್ಟು, ಆದರೆ ಆಯ್ಕೆಯ ಸಿದ್ಧಾಂತದ ಊಹೆಯೊಂದಿಗೆ) ಅನಂತ ಗ್ರಾಫ್ನ ಸಮ್ಮಿತಿಗಳ ಗುಂಪಾಗಿ ಅರಿತುಕೊಳ್ಳಬಹುದು ಎಂದು ಸ್ವತಂತ್ರವಾಗಿ ಸಾಬೀತುಪಡಿಸಿದರು. ಉಲ್ಲೇಖ ಮೂಲಗಳು. .. .. .. .. .. ಉಲ್ಲೇಖಿಸಿದಂತೆ. .. .. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಬೀಜಗಣಿತದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಪ್ರಮೇಯಗಳು