Erdős–Gallai theorem
ಎರ್ಡೋಸ್-ಗಲ್ಲೈ ಪ್ರಮೇಯವು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಒಂದು ಫಲಿತಾಂಶವಾಗಿದೆ, ಇದು ಸಂಯೋಜಿತ ಗಣಿತಶಾಸ್ತ್ರದ ಒಂದು ಶಾಖೆಯಾಗಿದೆ. ಇದು ಗ್ರಾಫ್ ಸಾಕ್ಷಾತ್ಕಾರ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ತಿಳಿದಿರುವ ಎರಡು ವಿಧಾನಗಳಲ್ಲಿ ಒಂದನ್ನು ಒದಗಿಸುತ್ತದೆ, ಅಂದರೆ. ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಸೀಮಿತ ಅನುಕ್ರಮವು ಸರಳ ಗ್ರಾಫ್ನ ಡಿಗ್ರಿ ಅನುಕ್ರಮವಾಗಲು ಇದು ಅಗತ್ಯ ಮತ್ತು ಸಾಕಷ್ಟು ಷರತ್ತನ್ನು ನೀಡುತ್ತದೆ. ಈ ಷರತ್ತುಗಳನ್ನು ಪಾಲಿಸುವ ಅನುಕ್ರಮವನ್ನು "ಗ್ರಾಫಿಕ್" ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಈ ಪ್ರಮೇಯವನ್ನು 1960 ರಲ್ಲಿ ಪಾಲ್ ಎರ್ಡೋಸ್ ಮತ್ತು ಟಿಬೋರ್ ಗಲ್ಲಾಯ್ ಅವರು ಪ್ರಕಟಿಸಿದರು, ಅವರ ಹೆಸರನ್ನು ಇಡಲಾಗಿದೆ. ಹೇಳಿಕೆಯು ಋಣಾತ್ಮಕವಲ್ಲದ ಪೂರ್ಣಾಂಕಗಳ ಅನುಕ್ರಮವನ್ನು n ಶೃಂಗಗಳ ಮೇಲೆ ಒಂದು ಸೀಮಿತ ಸರಳ ರೇಖಾಚಿತ್ರದ ಡಿಗ್ರಿ ಅನುಕ್ರಮವಾಗಿ ಪ್ರತಿನಿಧಿಸಬಹುದು ಮತ್ತು ಅದು ಸಮವಾಗಿದ್ದರೆ ಮತ್ತು ಪ್ರತಿ ಇಂಚಿಗೆ ಹಿಡಿದಿಟ್ಟುಕೊಂಡರೆ ಮಾತ್ರ. ಪುರಾವೆಗಳು ಎರ್ಡೋಸ್-ಗಲ್ಲೈ ಪ್ರಮೇಯದ ಷರತ್ತುಗಳು ಸಂಖ್ಯೆಗಳ ಅನುಕ್ರಮವು ಗ್ರಾಫಿಕ್ ಆಗಿರಲು ಅಗತ್ಯವೆಂದು ತೋರಿಸುವುದು ಕಷ್ಟವೇನಲ್ಲ. ಡಿಗ್ರಿಗಳ ಮೊತ್ತವು ಸಮವಾಗಿರಬೇಕು ಎಂಬ ಅವಶ್ಯಕತೆಯು ಹ್ಯಾಂಡ್ಶೇಕಿಂಗ್ ಲೆಮ್ಮಾವಾಗಿದೆ, ಇದನ್ನು ಈಗಾಗಲೇ ಯೂಲರ್ ತನ್ನ 1736 ರ ಕಾಗದದಲ್ಲಿ ಕೋನಿಗ್ಸ್ಬರ್ಗ್ನ ಸೇತುವೆಗಳ ಮೇಲೆ ಬಳಸಿದ್ದಾನೆ. ಅತಿದೊಡ್ಡ ಡಿಗ್ರಿಗಳ ಮೊತ್ತ ಮತ್ತು ಉಳಿದ ಡಿಗ್ರಿಗಳ ಮೊತ್ತದ ನಡುವಿನ ಅಸಮಾನತೆಯನ್ನು ಎರಡು ಎಣಿಕೆಗಳಿಂದ ಸ್ಥಾಪಿಸಬಹುದುಃ ಎಡಭಾಗವು ಉನ್ನತ-ಡಿಗ್ರಿ ಶೃಂಗಗಳ ನಡುವೆ ಅಂಚು-ಶೃಂಗದ ಸಾಮೀಪ್ಯಗಳ ಸಂಖ್ಯೆಯನ್ನು ನೀಡುತ್ತದೆ, ಅಂತಹ ಪ್ರತಿಯೊಂದು ಸಾಮೀಪ್ಯವು ಒಂದು ಅಥವಾ ಎರಡು ಉನ್ನತ-ಡಿಗ್ರಿ ಅಂತಿಮ ಬಿಂದುಗಳೊಂದಿಗೆ ಅಂಚಿನಲ್ಲಿರಬೇಕು, ಬಲಭಾಗದಲ್ಲಿರುವ ಪದವು ಎರಡೂ ಅಂತಿಮ ಬಿಂದುಗಳು ಹೆಚ್ಚಿನ ಮಟ್ಟವನ್ನು ಹೊಂದಿರುವ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಅಂಚು-ಶೃಂಗದ ಸಾಮೀಪ್ಯಗಳನ್ನು ನೀಡುತ್ತದೆ, ಮತ್ತು ಬಲ ಮೇಲಿನ ಮಿತಿಯಲ್ಲಿ ಉಳಿದ ಪದವು ನಿಖರವಾಗಿ ಒಂದು ಉನ್ನತ ಡಿಗ್ರಿ ಅಂತಿಮ ಬಿಂದುವನ್ನು ಹೊಂದಿರುವ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯನ್ನು ನೀಡುತ್ತದೆ. ಹೀಗಾಗಿ, ಈ ಷರತ್ತುಗಳನ್ನು ಪಾಲಿಸುವ ಸಂಖ್ಯೆಗಳ ಯಾವುದೇ ಅನುಕ್ರಮಕ್ಕೆ, ಅದು ಡಿಗ್ರಿ ಅನುಕ್ರಮವಾಗಿರುವ ಗ್ರಾಫ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ ಎಂದು ತೋರಿಸುವುದು ಪುರಾವೆಯ ಹೆಚ್ಚು ಕಷ್ಟಕರವಾದ ಭಾಗವಾಗಿದೆ. ಇದರ ಮೂಲ ಪುರಾವೆಯು ದೀರ್ಘವಾಗಿತ್ತು ಮತ್ತು ಒಳಗೊಂಡಿತ್ತು. ಜಾಲಬಂಧ ಹರಿವಿನ ಕಲ್ಪನೆಗಳ ಆಧಾರದ ಮೇಲೆ ಕ್ಲೌಡ್ ಬರ್ಜ್ ಅವರ ಸಣ್ಣ ಪುರಾವೆಯನ್ನು ಉಲ್ಲೇಖಿಸಿದ್ದಾರೆ. ಚೌದುಮ್ ಬದಲಿಗೆ ಡಿಗ್ರಿಗಳ ಮೊತ್ತದ ಮೇಲೆ ಗಣಿತದ ಪ್ರಚೋದನೆಯ ಮೂಲಕ ಪುರಾವೆಯನ್ನು ಒದಗಿಸುತ್ತಾನೆಃ ಅವನು ಅನುಕ್ರಮದಲ್ಲಿ ಒಂದು ಸಂಖ್ಯೆಯ ಮೊದಲ ಸೂಚ್ಯಂಕವಾಗಿರಲು ಅವಕಾಶ ಮಾಡಿಕೊಡುತ್ತಾನೆ (ಅಥವಾ ಎಲ್ಲಾ ಸಮಾನವಾಗಿದ್ದರೆ ಕೊನೆಯ ಸಂಖ್ಯೆ), ಅನುಕ್ರಮದಲ್ಲಿ ಕೊನೆಯ ಸಂಖ್ಯೆಯಿಂದ ಮತ್ತು ಒಂದನ್ನು ಕಳೆಯುವ ಮೂಲಕ ರೂಪುಗೊಂಡ ಅನುಕ್ರಮವು (ಮತ್ತು ಈ ವ್ಯವಕಲನವು ಶೂನ್ಯವಾಗಲು ಕಾರಣವಾದರೆ ಕೊನೆಯ ಸಂಖ್ಯೆಯನ್ನು ತೆಗೆದುಹಾಕುವುದು) ಮತ್ತೆ ಗ್ರಾಫಿಕ್ ಆಗಿದೆ ಎಂದು ತೋರಿಸಲು ಕೇಸ್ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಬಳಸುತ್ತದೆ, ಮತ್ತು ಒಂದನ್ನು ಕಳೆಯಲಾದ ಎರಡು ಸ್ಥಾನಗಳ ನಡುವೆ ಅಂಚನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಮೂಲ ಅನುಕ್ರಮವನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಗ್ರಾಫ್ ಅನ್ನು ರೂಪಿಸುತ್ತದೆ. "ಸಬ್ರಿಯಲೈಸೇಶನ್" ಗಳ ಅನುಕ್ರಮವನ್ನು ಪರಿಗಣಿಸಿ, ಅದರ ಡಿಗ್ರಿಗಳು ಮೇಲಿನ ಡಿಗ್ರಿ ಅನುಕ್ರಮದಿಂದ ಸುತ್ತುವರೆದಿವೆ. G ಒಂದು ಸಬ್ರಿಯಲೈಸೇಶನ್ ಆಗಿದ್ದರೆ, ಮತ್ತು i ಎಂಬುದು Gಯಲ್ಲಿನ ಒಂದು ಶೃಂಗದ ಅತ್ಯಂತ ಚಿಕ್ಕ ಸೂಚ್ಯಂಕವಾಗಿದ್ದರೆ, ಅದರ ಡಿಗ್ರಿ ಡಿ ಗೆ ಸಮನಾಗಿಲ್ಲದಿದ್ದರೆ, Gಯನ್ನು ಮತ್ತೊಂದು ಸಬ್ರಿಯಲೈಸೇಶನ್ ಅನ್ನು ಉತ್ಪಾದಿಸುವ ರೀತಿಯಲ್ಲಿ ಮಾರ್ಪಡಿಸಬಹುದು, ಇದು ಅನುಕ್ರಮದಲ್ಲಿ ಹಿಂದಿನ ಶೃಂಗಗಳ ಡಿಗ್ರಿಗಳನ್ನು ಬದಲಾಯಿಸದೆ ಶೃಂಗದ ಡಿಗ್ರಿ i ಅನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ. ಈ ರೀತಿಯ ಪುನರಾವರ್ತಿತ ಹಂತಗಳು ಅಂತಿಮವಾಗಿ ಕೊಟ್ಟಿರುವ ಅನುಕ್ರಮದ ಸಾಕ್ಷಾತ್ಕಾರವನ್ನು ತಲುಪಬೇಕು, ಇದು ಪ್ರಮೇಯವನ್ನು ಸಾಬೀತುಪಡಿಸುತ್ತದೆ. ಪೂರ್ಣಾಂಕ ವಿಭಜನೆಗಳೊಂದಿಗಿನ ಸಂಬಂಧವು ಎರ್ಡೋಸ್-ಗಲ್ಲೈ ಪ್ರಮೇಯ ಮತ್ತು ಪೂರ್ಣಾಂಕ ವಿಭಜನೆಗಳ ಸಿದ್ಧಾಂತದ ನಡುವಿನ ನಿಕಟ ಸಂಪರ್ಕಗಳನ್ನು ವಿವರಿಸುತ್ತದೆ. ಲೆಟ್; ನಂತರ ಒಟ್ಟುಗೂಡಿಸುವ ವಿಂಗಡಿಸಲಾದ ಪೂರ್ಣಾಂಕ ಅನುಕ್ರಮಗಳನ್ನು ವಿಭಾಗಗಳಾಗಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. ಅವುಗಳ ಪೂರ್ವಪ್ರತ್ಯಯ ಮೊತ್ತಗಳ ಬಹುಸಂಖ್ಯೆಯ ಅಡಿಯಲ್ಲಿ, ವಿಭಾಗಗಳು ಜಾಲರಿಯನ್ನು ರೂಪಿಸುತ್ತವೆ, ಇದರಲ್ಲಿ ಪ್ರತ್ಯೇಕ ವಿಭಾಗ ಮತ್ತು ವಿಭಜನೆಯ ಕ್ರಮದಲ್ಲಿ ಕೆಳಗಿರುವ ಮತ್ತೊಂದು ವಿಭಾಗದ ನಡುವಿನ ಕನಿಷ್ಠ ಬದಲಾವಣೆಯು ಒಂದು ಸಂಖ್ಯೆಯಿಂದ ಒಂದನ್ನು ಕಳೆಯುವುದು ಮತ್ತು ಅದನ್ನು ಕನಿಷ್ಠ ಎರಡು (ಶೂನ್ಯವಾಗಿರಬಹುದು) ಚಿಕ್ಕದಾಗಿರುವ ಸಂಖ್ಯೆಗೆ ಸೇರಿಸುವುದು. ಐಗ್ನರ್ ಮತ್ತು ಟ್ರೈಷ್ ತೋರಿಸಿದಂತೆ, ಈ ಕಾರ್ಯಾಚರಣೆಯು ಗ್ರಾಫಿಕ್ ಆಗಿರುವ ಗುಣವನ್ನು ಸಂರಕ್ಷಿಸುತ್ತದೆ, ಆದ್ದರಿಂದ ಎರ್ಡೋಸ್-ಗಲ್ಲೈ ಪ್ರಮೇಯವನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಈ ಪ್ರಮುಖ ಕ್ರಮದಲ್ಲಿ ಗರಿಷ್ಠವಾದ ಗ್ರಾಫಿಕ್ ಅನುಕ್ರಮಗಳನ್ನು ನಿರೂಪಿಸಲು ಸಾಕು. ಅವು ಅನುಗುಣವಾದ ವಿಭಾಗಗಳ ಫೆರೆರ್ಸ್ ರೇಖಾಚಿತ್ರಗಳ ಪರಿಭಾಷೆಯಲ್ಲಿ ಅಂತಹ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಒದಗಿಸುತ್ತವೆ ಮತ್ತು ಇದು ಎರ್ಡೋಸ್-ಗಲ್ಲೈ ಪ್ರಮೇಯಕ್ಕೆ ಸಮಾನವಾಗಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಇತರ ರೀತಿಯ ಗ್ರಾಫ್ಗಳಿಗೆ ಗ್ರಾಫಿಕ್ ಅನುಕ್ರಮಗಳು ಇದೇ ರೀತಿಯ ಪ್ರಮೇಯಗಳು ಸರಳ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳ ಡಿಗ್ರಿ ಅನುಕ್ರಮಗಳು, ಲೂಪ್ಗಳೊಂದಿಗೆ ಸರಳ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಸರಳ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ಗಳನ್ನು ವಿವರಿಸುತ್ತವೆ. ಮೊದಲ ಸಮಸ್ಯೆಯನ್ನು ಫುಲ್ಕರ್ಸನ್-ಚೆನ್-ಅನ್ಸ್ಟೀ ಪ್ರಮೇಯವು ನಿರೂಪಿಸುತ್ತದೆ. ಸಮಾನವಾದ ನಂತರದ ಎರಡು ಪ್ರಕರಣಗಳನ್ನು ಗೇಲ್-ರೈಸರ್ ಪ್ರಮೇಯವು ನಿರೂಪಿಸುತ್ತದೆ. ಬಲವಾದ ಆವೃತ್ತಿಯು ಅಸಮಾನತೆಯನ್ನು ಪರಿಗಣಿಸಲು ಸಾಕಾಗುತ್ತದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸಿತು. ವಿರುದ್ಧವಾದ ಒತ್ತಡದಲ್ಲಿ ಗ್ರಾಫ್ಗಳಿಗೆ ಅಸಮಾನತೆಗಳ ಗುಂಪನ್ನು ನಿರ್ಬಂಧಿಸಿ. ಸಮ-ಸಾರಾಂಶ ಧನಾತ್ಮಕ ಅನುಕ್ರಮವು ಗರಿಷ್ಠ ಮತ್ತು ಕನಿಷ್ಠವನ್ನು ಹೊರತುಪಡಿಸಿ ಯಾವುದೇ ಪುನರಾವರ್ತಿತ ನಮೂದುಗಳನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ (ಮತ್ತು ಉದ್ದವು ಅತಿದೊಡ್ಡ ನಮೂದನ್ನು ಮೀರಿದೆ), ಆಗ ಅದು ಕೇವಲ ಒಂಬತ್ತನೇ ಅಸಮಾನತೆಯನ್ನು ಪರಿಶೀಲಿಸಲು ಸಾಕಾಗುತ್ತದೆ, ಅಲ್ಲಿ. ಸಾಮಾನ್ಯೀಕರಣ ಋಣಾತ್ಮಕವಲ್ಲದ ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಸೀಮಿತ ಅನುಕ್ರಮವು ಸಮವಾಗಿದ್ದರೆ ಗ್ರಾಫಿಕ್ ಆಗಿರುತ್ತದೆ ಮತ್ತು ಗ್ರಾಫಿಕ್ ಮತ್ತು ಪ್ರಮುಖವಾದ ಅನುಕ್ರಮವು ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ. ಈ ಫಲಿತಾಂಶವನ್ನು ನೀಡಲಾಗಿದೆ. ಅದನ್ನು ಮರುಶೋಧಿಸಿದರು ಮತ್ತು ಹೆಚ್ಚು ನೇರವಾದ ಪುರಾವೆಯನ್ನು ನೀಡಿದರು. ಹಾವೆಲ್-ಹಾಕಿಮಿ ಅಲ್ಗಾರಿದಮ್ ಉಲ್ಲೇಖಗಳನ್ನು ಸಹ ನೋಡಿ. .. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಗಲ್ಲೈ ಪ್ರಮೇಯ ಪ್ರಮೇಯಗಳು