Ore's theorem
ಓರೆ ಪ್ರಮೇಯವು 1960ರಲ್ಲಿ ನಾರ್ವೇಜಿಯನ್ ಗಣಿತಶಾಸ್ತ್ರಜ್ಞ ಓಸ್ಟೀನ್ ಓರೆ ಸಾಬೀತುಪಡಿಸಿದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಫಲಿತಾಂಶವಾಗಿದೆ. ಇದು ರೇಖಾಚಿತ್ರವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿರಲು ಸಾಕಷ್ಟು ಷರತ್ತನ್ನು ನೀಡುತ್ತದೆ, ಮೂಲಭೂತವಾಗಿ ಸಾಕಷ್ಟು ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ರೇಖಾಚಿತ್ರವು ಹ್ಯಾಮಿಲ್ಟನ್ ಚಕ್ರವನ್ನು ಹೊಂದಿರಬೇಕು ಎಂದು ಹೇಳುತ್ತದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಪ್ರಮೇಯವು ಪಕ್ಕದ ಅಲ್ಲದ ಶೃಂಗಗಳ ಜೋಡಿಗಳ ಡಿಗ್ರಿಗಳ ಮೊತ್ತವನ್ನು ಪರಿಗಣಿಸುತ್ತದೆಃ ಅಂತಹ ಪ್ರತಿಯೊಂದು ಜೋಡಿಯು ಗ್ರಾಫ್ನಲ್ಲಿನ ಒಟ್ಟು ಶೃಂಗಗಳ ಸಂಖ್ಯೆಗೆ ಸಮನಾದ ಮೊತ್ತವನ್ನು ಹೊಂದಿದ್ದರೆ, ಗ್ರಾಫ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿರುತ್ತದೆ. ಔಪಚಾರಿಕ ಹೇಳಿಕೆಯು ಶೃಂಗಗಳೊಂದಿಗೆ (ಸೀಮಿತ ಮತ್ತು ಸರಳ) ಗ್ರಾಫ್ ಆಗಿರಲಿ. ನಾವು ಒಂದು ಶೃಂಗದ ಮಟ್ಟದಿಂದ ಸೂಚಿಸುತ್ತೇವೆ, ಅಂದರೆ. ಘಟನೆಯ ಅಂಚುಗಳ ಸಂಖ್ಯೆ. ನಂತರ, ಓರೆ ಪ್ರಮೇಯವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಎಂದು ಹೇಳುತ್ತದೆ. ಪುರಾವೆ ಇದು ಪ್ರತಿ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಅಲ್ಲದ ಗ್ರಾಫ್ ಷರತ್ತನ್ನು ಪಾಲಿಸುವುದಿಲ್ಲ ಎಂದು ತೋರಿಸಲು ಸಮಾನವಾಗಿದೆ. ಅಂತೆಯೇ, ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಅಲ್ಲದ ಶೃಂಗಗಳ ಮೇಲೆ ಗ್ರಾಫ್ ಆಗಿರಲಿ, ಮತ್ತು ಯಾವುದೇ ಹೆಚ್ಚಿನ ಅಂಚುಗಳನ್ನು ಸೇರಿಸುವವರೆಗೆ, ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವನ್ನು ರಚಿಸದ ಅಂಚುಗಳನ್ನು ಒಂದು ಸಮಯದಲ್ಲಿ ಒಂದನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ರಚಿಸೋಣ. ಯಾವುದೇ ಎರಡು ಪಕ್ಕದಲ್ಲಿಲ್ಲದ ಶೃಂಗಗಳಿರಲಿ ಮತ್ತು ಆಗಿರಲಿ. ನಂತರ ಅಂಚನ್ನು ಸೇರಿಸುವುದರಿಂದ ಕನಿಷ್ಠ ಒಂದು ಹೊಸ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವನ್ನು ರಚಿಸುತ್ತದೆ, ಮತ್ತು ಅಂತಹ ಚಕ್ರವನ್ನು ಹೊರತುಪಡಿಸಿ ಇತರ ಅಂಚುಗಳು ಮತ್ತು ಜೊತೆ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಮಾರ್ಗವನ್ನು ರೂಪಿಸಬೇಕು. ಶ್ರೇಣಿಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಸೂಚ್ಯಂಕಕ್ಕೂ, ಎರಡು ಸಂಭಾವ್ಯ ಅಂಚುಗಳನ್ನು ಪರಿಗಣಿಸಿ. ಈ ಎರಡು ಅಂಚುಗಳಲ್ಲಿ ಹೆಚ್ಚಿನವುಗಳಲ್ಲಿ ಒಂದನ್ನು ಹೊಂದಿರಬಹುದು, ಇಲ್ಲದಿದ್ದರೆ ಚಕ್ರವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವಾಗಿರುತ್ತದೆ. ಹೀಗಾಗಿ, ಒಟ್ಟು ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ಎರಡೂ ಅಥವಾ ಹೆಚ್ಚಿನವುಗಳ ಆಯ್ಕೆಗಳ ಸಂಖ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಈ ಒಟ್ಟು ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು () ಗಿಂತ ಹೆಚ್ಚಾಗಿರಬೇಕು ಅಥವಾ ಸಮನಾಗಿರಬೇಕು ಎಂಬ ಗುಣಲಕ್ಷಣವನ್ನು ( ಕಾಯ಼) ಪಾಲಿಸುವುದಿಲ್ಲ. ಶೃಂಗದ ಡಿಗ್ರಿಗಳು ಗರಿಷ್ಠ ಡಿಗ್ರಿಗಳಿಗೆ ಸಮಾನವಾಗಿರುವುದರಿಂದ, ಇದು ಗುಣಲಕ್ಷಣವನ್ನು (ir) ಪಾಲಿಸುವುದಿಲ್ಲ. ಅಲ್ಗಾರಿದಮ್ ಓರ್ನ ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸುವ ಗ್ರಾಫ್ನಲ್ಲಿ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವನ್ನು ನಿರ್ಮಿಸಲು ಈ ಕೆಳಗಿನ ಸರಳ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ವಿವರಿಸುತ್ತದೆ. ಗ್ರಾಫ್ ನಲ್ಲಿರುವ ಸಾಮೀಪ್ಯಗಳನ್ನು ನಿರ್ಲಕ್ಷಿಸಿ, ಶೃಂಗಗಳನ್ನು ಅನಿಯಂತ್ರಿತವಾಗಿ ಒಂದು ಚಕ್ರದಲ್ಲಿ ಜೋಡಿಸಿ. ಈ ಚಕ್ರವು ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಪಕ್ಕದಲ್ಲಿರದ ಎರಡು ಅನುಕ್ರಮ ಶೃಂಗಗಳಾದ vi ಮತ್ತು vi + 1 ಅನ್ನು ಹೊಂದಿದ್ದರೂ, ಈ ಕೆಳಗಿನ ಎರಡು ಹಂತಗಳನ್ನು ನಿರ್ವಹಿಸಿಃ ಸೂಚ್ಯಂಕ j ಅನ್ನು ಹುಡುಕಿ, ಅಂದರೆ vi, vi + 1, vj, ಮತ್ತು vj + 1 ಎಂಬ ನಾಲ್ಕು ಶೃಂಗಗಳು ಎಲ್ಲಾ ವಿಭಿನ್ನವಾಗಿವೆ ಮತ್ತು ರೇಖಾಚಿತ್ರವು vi ಯಿಂದ vj ವರೆಗೆ ಮತ್ತು vj + 1 ರಿಂದ vi + 1 ರವರೆಗೆ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು vi + 1 ಮತ್ತು vj (ಸೇರಿದಂತೆ) ನಡುವಿನ ಚಕ್ರದ ಭಾಗವನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸಿ. ಪ್ರತಿ ಹಂತವು ಗ್ರಾಫ್ನ ಪಕ್ಕದಲ್ಲಿರುವ ಚಕ್ರದಲ್ಲಿ ಸತತ ಜೋಡಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಒಂದು ಅಥವಾ ಎರಡು ಜೋಡಿಗಳಿಂದ ಹೆಚ್ಚಿಸುತ್ತದೆ (vj ಮತ್ತು vj + 1 ಈಗಾಗಲೇ ಪಕ್ಕದಲ್ಲಿವೆಯೇ ಎಂಬುದನ್ನು ಅವಲಂಬಿಸಿ), ಆದ್ದರಿಂದ ಅಲ್ಗಾರಿದಮ್ ಕೊನೆಗೊಳ್ಳುವ ಮೊದಲು ಹೊರಗಿನ ಲೂಪ್ ಹೆಚ್ಚಿನ n ಬಾರಿ ಮಾತ್ರ ಸಂಭವಿಸಬಹುದು, ಅಲ್ಲಿ n ಎಂಬುದು ನೀಡಲಾದ ಗ್ರಾಫ್ನಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆ. ಪ್ರಮೇಯದ ಪುರಾವೆಯಲ್ಲಿರುವ ವಾದದಂತೆಯೇ, ಅಪೇಕ್ಷಿತ ಸೂಚ್ಯಂಕ ಜೆ ಅಸ್ತಿತ್ವದಲ್ಲಿರಬೇಕು, ಇಲ್ಲದಿದ್ದರೆ ಪಕ್ಕದಲ್ಲಿಲ್ಲದ ಶೃಂಗಗಳು vi ಮತ್ತು vi + 1 ತುಂಬಾ ಚಿಕ್ಕ ಮೊತ್ತವನ್ನು ಹೊಂದಿರುತ್ತವೆ. i ಮತ್ತು j ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಮತ್ತು ಚಕ್ರದ ಭಾಗವನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸುವುದು, ಇವೆಲ್ಲವನ್ನೂ O (n) ಸಮಯದಲ್ಲಿ ಸಾಧಿಸಬಹುದು. ಆದ್ದರಿಂದ, ಅಲ್ಗಾರಿದಮ್ನ ಒಟ್ಟು ಸಮಯವು O (n2) ಆಗಿದ್ದು, ಇದು ಇನ್ಪುಟ್ ಗ್ರಾಫ್ನಲ್ಲಿರುವ ಅಂಚುಗಳ ಸಂಖ್ಯೆಗೆ ಹೊಂದಿಕೆಯಾಗುತ್ತದೆ. ಸಂಬಂಧಿತ ಫಲಿತಾಂಶಗಳು ಓರೆ ಪ್ರಮೇಯವು ಡಿರಾಕ್ನ ಪ್ರಮೇಯದ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿದ್ದು, ಪ್ರತಿ ಶೃಂಗವು ಕನಿಷ್ಠ ಮಟ್ಟವನ್ನು ಹೊಂದಿರುವಾಗ, ರೇಖಾಚಿತ್ರವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿರುತ್ತದೆ. ಏಕೆಂದರೆ, ಒಂದು ರೇಖಾಚಿತ್ರವು ಡಿರಾಕ್ನ ಷರತ್ತನ್ನು ಪೂರೈಸಿದರೆ, ಸ್ಪಷ್ಟವಾಗಿ ಪ್ರತಿ ಜೋಡಿ ಶೃಂಗಗಳು ಕನಿಷ್ಠ ಡಿಗ್ರಿಗಳನ್ನು ಸೇರಿಸುತ್ತವೆ. ಪ್ರತಿಯಾಗಿ ಓರೆ ಪ್ರಮೇಯವನ್ನು ಬಾಂಡಿ-ಚ್ವಾಟಲ್ ಪ್ರಮೇಯದಿಂದ ಸಾಮಾನ್ಯೀಕರಿಸಲಾಗಿದೆ. ಒಂದು ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಒಂದು ಮುಚ್ಚುವಿಕೆಯ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಇದರಲ್ಲಿ ಎರಡು ಪಕ್ಕದಲ್ಲಿಲ್ಲದ ಶೃಂಗಗಳು ಕನಿಷ್ಠ ಡಿಗ್ರಿಗಳನ್ನು ಸೇರಿಸಿದಾಗ, ಅವುಗಳನ್ನು ಸಂಪರ್ಕಿಸುವ ಒಂದು ಅಂಚನ್ನು ಸೇರಿಸುತ್ತದೆ; ಒಂದು ರೇಖಾಚಿತ್ರವು ಓರೆ ಪ್ರಮೇಯದ ಷರತ್ತುಗಳನ್ನು ಪೂರೈಸಿದರೆ, ಅದರ ಮುಚ್ಚುವಿಕೆಯು ಸಂಪೂರ್ಣ ರೇಖಾಚಿತ್ರವಾಗಿದೆ. ಬಾಂಡಿ-ಚಾವಟಲ್ ಪ್ರಮೇಯವು ಒಂದು ರೇಖಾಚಿತ್ರವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿದ್ದರೆ ಮತ್ತು ಅದರ ಮುಚ್ಚುವಿಕೆಯು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿದ್ದರೆ ಮಾತ್ರ ಅದು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಎಂದು ಹೇಳುತ್ತದೆ; ಸಂಪೂರ್ಣ ರೇಖಾಚಿತ್ರವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿರುವುದರಿಂದ, ಓರೆ ಪ್ರಮೇಯವು ತಕ್ಷಣದ ಪರಿಣಾಮವಾಗಿದೆ. ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳಿಗೆ ಅನ್ವಯವಾಗುವ ಓರೆ ಪ್ರಮೇಯದ ಒಂದು ಆವೃತ್ತಿಯನ್ನು ಕಂಡುಹಿಡಿದಿದೆ. ಡಿಗ್ರ್ಯಾಫ್ G ಯು ಪ್ರತಿ ಎರಡು ಶೃಂಗಗಳಾದ u ಮತ್ತು v ಗೆ, u ನಿಂದ v ಗೆ ಒಂದು ಅಂಚು ಇದೆ ಅಥವಾ u ನ ಹೊರ ಡಿಗ್ರಿ ಜೊತೆಗೆ v ನ ಇನ್ಡೆಗ್ರೀ G ಯಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಅಥವಾ ಮೀರುತ್ತದೆ ಎಂಬ ಗುಣವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ಒಂದು ನಿರ್ದಿಷ್ಟ ನಿರ್ದೇಶನವಿಲ್ಲದ ರೇಖಾಚಿತ್ರದ ಪ್ರತಿಯೊಂದು ಅಂಚನ್ನು ಒಂದು ಜೋಡಿ ನಿರ್ದೇಶನದ ಅಂಚುಗಳಿಂದ ಬದಲಾಯಿಸುವ ಮೂಲಕ ಓರೆ ಪ್ರಮೇಯವನ್ನು ವುಡಾಲ್ನಿಂದ ಪಡೆಯಬಹುದು. ಎನ್-ವೆರ್ಟೆಕ್ಸ್ ಬಲವಾಗಿ ಡಿಗ್ರ್ಯಾಫ್ ಅನ್ನು ಗುಣಲಕ್ಷಣದೊಂದಿಗೆ ಸಂಪರ್ಕಿಸಿದೆ ಎಂದು ಹೇಳುವ ಒಂದು ನಿಕಟವಾದ ಪ್ರಮೇಯವು, ಪ್ರತಿ ಎರಡು ಪಕ್ಕದ ಶೃಂಗಗಳಾದ ಯು ಮತ್ತು ವಿ ಗೆ, ಯು ಅಥವಾ ವಿ ಗೆ ಒಟ್ಟು ಅಂಚುಗಳ ಸಂಖ್ಯೆ ಕನಿಷ್ಠ 2n−1 ಆಗಿರಬೇಕು. ಪ್ರಮೇಯದಲ್ಲಿನ ಡಿಗ್ರಿ ಸ್ಥಿತಿಯ ಪರಿಣಾಮವಾಗಿ ಹ್ಯಾಮಿಲ್ಟೋನಿಸಿಟಿಗಿಂತ ಬಲವಾದ ತೀರ್ಮಾನವನ್ನು ನೀಡಲು ಓರೆ ಪ್ರಮೇಯವನ್ನು ಸಹ ಬಲಪಡಿಸಬಹುದು. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಓರೆ ಪ್ರಮೇಯದ ಷರತ್ತುಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುವ ಪ್ರತಿಯೊಂದು ಗ್ರಾಫ್ ನಿಯಮಿತವಾದ ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ ಆಗಿರುತ್ತದೆ ಅಥವಾ ಪ್ಯಾನ್ಸೈಕ್ಲಿಕ್ ಆಗಿರುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು. .. .. .. .. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿನ ಬಾಹ್ಯ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಪ್ರಮೇಯಗಳು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಮಾರ್ಗಗಳು ಮತ್ತು ಚಕ್ರಗಳ ಪುರಾವೆಗಳನ್ನು ಹೊಂದಿರುವ ಲೇಖನಗಳು