Thrackle
ಥ್ರಾಕ್ಲೆ ಎಂದರೆ ಸಮತಲದಲ್ಲಿ ಗ್ರಾಫ್ ಅನ್ನು ಹುದುಗಿಸುವುದು, ಇದರಲ್ಲಿ ಪ್ರತಿ ಅಂಚು ಜೋರ್ಡಾನ್ ಆರ್ಕ್ ಆಗಿರುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಜೋಡಿ ಅಂಚುಗಳು ನಿಖರವಾಗಿ ಒಮ್ಮೆ ಸಂಧಿಸುತ್ತವೆ. ಅಂಚುಗಳು ಒಂದು ಸಾಮಾನ್ಯ ಅಂತಿಮ ಬಿಂದುವಿನಲ್ಲಿ ಸಂಧಿಸಬಹುದು, ಅಥವಾ, ಅವುಗಳಿಗೆ ಯಾವುದೇ ಸಾಮಾನ್ಯ ಅಂತಿಮ ಬಿಂದುಗಳಿಲ್ಲದಿದ್ದರೆ, ಅವುಗಳ ಒಳಾಂಗಣದ ಒಂದು ಹಂತದಲ್ಲಿ ಸಂಧಿಸಬಹುದು. ನಂತರದ ಸಂದರ್ಭದಲ್ಲಿ, ಅವರು ತಮ್ಮ ಛೇದಕ ಬಿಂದುವಿನಲ್ಲಿ ದಾಟಬೇಕುಃ ಛೇದಕವು ಅಡ್ಡವಾಗಿರಬೇಕು. ರೇಖೀಯ ಥ್ರ್ಯಾಕಲ್ ಎಂದರೆ ಅದರ ಅಂಚುಗಳು ನೇರ ರೇಖೆಯ ಭಾಗಗಳಾಗುವ ರೀತಿಯಲ್ಲಿ ಚಿತ್ರಿಸಲಾದ ಥ್ರ್ಯಾಕಲ್ ಆಗಿದೆ. ಪಾಲ್ ಎರ್ಡೋಸ್ ಗಮನಿಸಿದಂತೆ, ಪ್ರತಿ ರೇಖೀಯ ಥ್ರಾಕ್ಲೂ ಶೃಂಗಗಳಷ್ಟೇ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಂದು ಶೃಂಗವು ಮೂರು ಅಥವಾ ಹೆಚ್ಚಿನ ಅಂಚುಗಳಾದ vw, vx, ಮತ್ತು vy ಗೆ ಸಂಪರ್ಕ ಹೊಂದಿದ್ದರೆ, ಆ ಅಂಚುಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಒಂದು (vw ಎಂದು ಹೇಳಿ) ಇತರ ಎರಡು ಅಂಚುಗಳನ್ನು ಬೇರ್ಪಡಿಸುವ ರೇಖೆಯ ಮೇಲೆ ಇರುತ್ತದೆ. ನಂತರ, ಡಬ್ಲ್ಯೂ ಒಂದು ಡಿಗ್ರಿ ಹೊಂದಿರಬೇಕು, ಏಕೆಂದರೆ ಡಬ್ಲ್ಯೂ ನಲ್ಲಿ ಕೊನೆಗೊಳ್ಳುವ ಯಾವುದೇ ರೇಖೆ ವಿಭಾಗವು, ವಿಡಬ್ಲ್ಯೂ ಹೊರತುಪಡಿಸಿ, ವಿಎಕ್ಸ್ ಮತ್ತು ವೈ ಎರಡನ್ನೂ ಸ್ಪರ್ಶಿಸುವುದಿಲ್ಲ. ಡಬ್ಲ್ಯೂ ಮತ್ತು ವಿಡಬ್ಲ್ಯೂ ಅನ್ನು ತೆಗೆದುಹಾಕುವುದರಿಂದ ಅಂಚುಗಳು ಮತ್ತು ಶೃಂಗಗಳ ಸಂಖ್ಯೆಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಬದಲಾಯಿಸದೆ ಸಣ್ಣ ಥ್ರಾಕ್ಲನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ. ಈ ರೀತಿಯ ತೆಗೆದುಹಾಕುವಿಕೆಯ ನಂತರ ಪ್ರತಿ ಶೃಂಗವು ಗರಿಷ್ಠ ಎರಡು ನೆರೆಹೊರೆಗಳನ್ನು ಹೊಂದಿರುವ ಥ್ರಾಕಲ್ಗೆ ಕಾರಣವಾಗುತ್ತದೆ, ಹ್ಯಾಂಡ್ಶೇಕಿಂಗ್ ಲೆಮ್ಮಾದಿಂದ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯಾಗಿರುತ್ತದೆ. ಎರ್ಡೋಸ್ನ ಪುರಾವೆಯ ಆಧಾರದ ಮೇಲೆ, ಪ್ರತಿ ರೇಖೀಯ ತೆವಳುವಿಕೆಯು ಹುಸಿ ಅರಣ್ಯವಾಗಿದೆ ಎಂದು ಊಹಿಸಬಹುದು. ಬೆಸ ಉದ್ದದ ಪ್ರತಿಯೊಂದು ಚಕ್ರವನ್ನು ರೇಖೀಯ ಎಳೆತವನ್ನು ರೂಪಿಸಲು ಜೋಡಿಸಬಹುದು, ಆದರೆ ಸಮ-ಉದ್ದದ ಚಕ್ರಕ್ಕೆ ಇದು ಸಾಧ್ಯವಿಲ್ಲ, ಏಕೆಂದರೆ ಚಕ್ರದ ಒಂದು ತುದಿಯನ್ನು ಅನಿಯಂತ್ರಿತವಾಗಿ ಆಯ್ಕೆ ಮಾಡಿದರೆ, ಇತರ ಚಕ್ರದ ಶೃಂಗಗಳು ಈ ತುದಿಯ ಮೂಲಕ ರೇಖೆಯ ವಿರುದ್ಧ ಬದಿಗಳಲ್ಲಿ ಪರ್ಯಾಯವಾಗಿ ಇರಬೇಕಾಗುತ್ತದೆ. ರೇಖೀಯ ಥ್ರಾಕ್ಲಿನಲ್ಲಿ ಪ್ರತಿ ಅಂಚುಗಳು ಗರಿಷ್ಠ 180° ಕೋನವನ್ನು ವ್ಯಾಪಿಸುವ ಅಂತಿಮ ಬಿಂದುವನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು ಇದಕ್ಕಾಗಿ ಇದು ಈ ಅವಧಿಯೊಳಗೆ ಅತ್ಯಂತ ಪ್ರದಕ್ಷಿಣಾಕಾರದ ಅಂಚು ಎಂಬ ಅಂಶದ ಆಧಾರದ ಮೇಲೆ ರೇಖೀಯ ಥ್ರಾಕ್ಲೆಗಳು ಗರಿಷ್ಠ n ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ ಎಂಬುದಕ್ಕೆ ಮೈಕಾ ಪರ್ಲ್ಸ್ ಮತ್ತೊಂದು ಸರಳ ಪುರಾವೆಯನ್ನು ಒದಗಿಸಿದರು. ಏಕೆಂದರೆ, ಇಲ್ಲದಿದ್ದರೆ, ಎರಡು ಅಂಚುಗಳು ಇರುತ್ತವೆ, ಅವು ಅಂಚಿನ ವಿರುದ್ಧ ತುದಿಗಳಿಗೆ ಅಂಟಿಕೊಳ್ಳುತ್ತವೆ ಮತ್ತು ಅಂಚಿನ ಮೂಲಕ ರೇಖೆಯ ವಿರುದ್ಧ ಬದಿಗಳಲ್ಲಿ ಬೀಳುತ್ತವೆ, ಅವು ಪರಸ್ಪರ ದಾಟಲು ಸಾಧ್ಯವಾಗುವುದಿಲ್ಲ. ಆದರೆ ಪ್ರತಿ ಶೃಂಗವು ಒಂದೇ ಅಂಚಿಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಈ ಗುಣವನ್ನು ಹೊಂದಿರಬಹುದು, ಆದ್ದರಿಂದ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ಶೃಂಗಗಳ ಸಂಖ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ. ಎರ್ಡೋಸ್ ಗಮನಿಸಿದಂತೆ, ಒಂದು ಬಿಂದು ಗುಂಪಿನ ವ್ಯಾಸವನ್ನು ಅರಿತುಕೊಳ್ಳುವ ಜೋಡಿ ಬಿಂದುಗಳ ಸಮೂಹವು ರೇಖೀಯ ಥ್ರಾಕ್ಲನ್ನು ರೂಪಿಸಬೇಕುಃ ಯಾವುದೇ ಎರಡು ವ್ಯಾಸಗಳು ಪರಸ್ಪರ ಬೇರ್ಪಡುವಂತಿಲ್ಲ, ಏಕೆಂದರೆ ಅವು ಇದ್ದರೆ ಅವುಗಳ ನಾಲ್ಕು ಅಂತಿಮ ಬಿಂದುಗಳು ಎರಡು ಬೇರ್ಪಡುವ ಅಂಚುಗಳಿಗಿಂತ ದೂರದಲ್ಲಿ ಜೋಡಿಯನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಈ ಕಾರಣಕ್ಕಾಗಿ, ಸಮತಲದಲ್ಲಿನ n ಬಿಂದುಗಳ ಪ್ರತಿಯೊಂದು ಗುಂಪೂ ಗರಿಷ್ಠ n ವ್ಯಾಸದ ಜೋಡಿಗಳನ್ನು ಹೊಂದಿರಬಹುದು, ಇದು 1934ರಲ್ಲಿ ಹೈನ್ಜ್ ಹಾಫ್ ಮತ್ತು ಎರಿಕಾ ಪನ್ನ್ವಿಟ್ಜ್ ಅವರು ಕೇಳಿದ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸುತ್ತದೆ. ಆಂಡ್ರ್ಯೂ ವಾಸ್ಸೋನಿ ಹೆಚ್ಚಿನ ಆಯಾಮಗಳಲ್ಲಿ ವ್ಯಾಸದ ಜೋಡಿಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ಮಿತಿಯನ್ನು ಊಹಿಸಿ, ಈ ಸಮಸ್ಯೆಯನ್ನು ಸಾಮಾನ್ಯೀಕರಿಸಿದರು. ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿಯಲ್ಲಿ, ತಿರುಗುವ ಕ್ಯಾಲಿಪರ್ಗಳ ವಿಧಾನವನ್ನು ಕನ್ವೆಕ್ಸ್ ಸ್ಥಾನದಲ್ಲಿರುವ ಯಾವುದೇ ಬಿಂದುಗಳ ಗುಂಪಿನಿಂದ ರೇಖೀಯ ಥ್ರಾಕ್ಲನ್ನು ರೂಪಿಸಲು ಬಳಸಬಹುದು, ಬಿಂದುಗಳ ಕನ್ವೆಕ್ಸ್ ಹಲ್ಗೆ ಸಮಾನಾಂತರ ರೇಖೆಗಳನ್ನು ಬೆಂಬಲಿಸುವ ಜೋಡಿ ಬಿಂದುಗಳನ್ನು ಸಂಪರ್ಕಿಸುವ ಮೂಲಕ. ಈ ರೇಖಾಚಿತ್ರವು ವ್ಯಾಸದ ಜೋಡಿಗಳ ಥ್ರಾಕ್ಲನ್ನು ಉಪ ರೇಖಾಚಿತ್ರವಾಗಿ ಒಳಗೊಂಡಿದೆ. ರೇನ್ಹಾರ್ಡ್ ಬಹುಭುಜಾಕೃತಿಗಳ ವ್ಯಾಸಗಳು ರೇಖೀಯ ಥ್ರಾಕ್ಲೆಗಳನ್ನು ರೂಪಿಸುತ್ತವೆ. ಅದರ ವ್ಯಾಸಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ಗರಿಷ್ಠ ವಿಸ್ತೀರ್ಣವನ್ನು ಹೊಂದಿರುವ ಎನ್-ಗಾನ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವ ಅತಿದೊಡ್ಡ ಸಣ್ಣ ಬಹುಭುಜಾಕೃತಿಯ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ರೇಖೀಯ ಥ್ರಾಕ್ಲೆಗಳ ಗಣನೆಯನ್ನು ಬಳಸಬಹುದು. ಥ್ರಾಕ್ಲೆ ಊಹೆ ಜಾನ್ ಎಚ್. ಕಾನ್ವೇ, ಯಾವುದೇ ಥ್ರಾಕ್ಲೆನಲ್ಲಿ, ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ಶೃಂಗಗಳ ಸಂಖ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಎಂದು ಊಹಿಸಿದ್ದಾರೆ. ಕಾನ್ವೇ ಸ್ವತಃ ಪರಿಭಾಷೆಯ ಮಾರ್ಗಗಳು ಮತ್ತು ಕಲೆಗಳನ್ನು ಬಳಸಿದರು (ಅನುಕ್ರಮವಾಗಿ ಅಂಚುಗಳು ಮತ್ತು ಶೃಂಗಗಳಿಗೆ), ಆದ್ದರಿಂದ ಕಾನ್ವೇ ಅವರ ಥ್ರಾಕಲ್ ಊಹೆಯನ್ನು ಮೂಲತಃ ಪ್ರತಿ ಥ್ರಾಕಲ್ ಕನಿಷ್ಠ ಮಾರ್ಗಗಳಷ್ಟೇ ಅನೇಕ ಕಲೆಗಳನ್ನು ಹೊಂದಿರುವ ರೂಪದಲ್ಲಿ ಹೇಳಲಾಗಿದೆ. ಕಾನ್ವೇ ಅವರ 99-ಗ್ರಾಫ್ ಸಮಸ್ಯೆ, ಡ್ಯಾನ್ಜರ್ ಸೆಟ್ಗಳ ಕನಿಷ್ಠ ಅಂತರ ಮತ್ತು ಚಲನೆ 16 ರ ನಂತರ ಸಿಲ್ವರ್ ನಾಣ್ಯಗಳ ವಿಜೇತರು ಸೇರಿದಂತೆ ಬಹುಮಾನದ ಸಮಸ್ಯೆಗಳ ಗುಂಪಿನ ಭಾಗವಾಗಿ ಈ ಊಹೆಯನ್ನು ಸಾಬೀತುಪಡಿಸಿದ್ದಕ್ಕಾಗಿ ಅಥವಾ ನಿರಾಕರಿಸಿದ್ದಕ್ಕಾಗಿ ಕಾನ್ವೇ $1000 ಬಹುಮಾನವನ್ನು ನೀಡಿದರು. ಅದೇ ರೀತಿ, ಪ್ರತಿಯೊಂದು ತೊಗಲೂ ಒಂದು ಹುಸಿ ಅರಣ್ಯವಾಗಿರುವುದರಿಂದ ತೊಗಲಿನ ಊಹೆಯನ್ನು ಹೇಳಬಹುದು. ಹೆಚ್ಚು ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಥ್ರಾಕ್ಲೆ ಊಹೆಯು ನಿಜವಾಗಿದ್ದರೆ, ಥ್ರಾಕ್ಲೆಗಳನ್ನು ವುಡಾಲ್ನ ಫಲಿತಾಂಶದಿಂದ ನಿಖರವಾಗಿ ನಿರೂಪಿಸಬಹುದುಃ ಅವು ಹುಸಿ ಅರಣ್ಯಗಳಾಗಿವೆ, ಇದರಲ್ಲಿ ನಾಲ್ಕು ಉದ್ದದ ಯಾವುದೇ ಚಕ್ರವಿಲ್ಲ ಮತ್ತು ಗರಿಷ್ಠ ಒಂದು ಬೆಸ ಚಕ್ರವಿದೆ. C4 ಅನ್ನು ಹೊರತುಪಡಿಸಿ ಪ್ರತಿಯೊಂದು ಸೈಕಲ್ ಗ್ರಾಫ್ ಥ್ರಾಕಲ್ ಎಂಬೆಡಿಂಗ್ ಅನ್ನು ಹೊಂದಿದೆ ಎಂದು ಸಾಬೀತಾಗಿದೆ, ಇದು ಊಹೆಯು ತೀಕ್ಷ್ಣವಾಗಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಅಂದರೆ, ಮಾರ್ಗಗಳಷ್ಟೇ ಸಂಖ್ಯೆಯ ತಾಣಗಳನ್ನು ಹೊಂದಿರುವ ತೆಗ್ಗುಗಳು ಇವೆ. ಇನ್ನೊಂದು ತುದಿಯಲ್ಲಿ, ಅತ್ಯಂತ ಕೆಟ್ಟ ಸನ್ನಿವೇಶವೆಂದರೆ ತಾಣಗಳ ಸಂಖ್ಯೆಯು ಮಾರ್ಗಗಳ ಸಂಖ್ಯೆಯ ಎರಡು ಪಟ್ಟು ಹೆಚ್ಚಾಗಿರುತ್ತದೆ; ಇದನ್ನು ಸಹ ಸಾಧಿಸಬಹುದು. ಪ್ರತಿ ಅಂಚು x-ಮೊನೊಟೋನ್ ವಕ್ರರೇಖೆಯಾಗಿದ್ದು, ಪ್ರತಿ ಲಂಬ ರೇಖೆಯಿಂದ ಗರಿಷ್ಠ ಒಮ್ಮೆಯಾದರೂ ದಾಟುವ ರೀತಿಯಲ್ಲಿ ಚಿತ್ರಿಸಲಾದ ಥ್ರ್ಯಾಕಲ್ಗಳಿಗೆ ಥ್ರ್ಯಾಕಲ್ ಊಹೆಯು ನಿಜವೆಂದು ತಿಳಿದುಬಂದಿದೆ. ತಿಳಿದಿರುವ ಗಡಿಗಳು ಪ್ರತಿ ಉಭಯಪಕ್ಷೀಯ ಥ್ರಾಕ್ಲನ್ನು ಸಮತಟ್ಟಾದ ರೀತಿಯಲ್ಲಿ ಚಿತ್ರಿಸದಿದ್ದರೂ ಸಮತಟ್ಟಾದ ರೇಖಾಚಿತ್ರವೆಂದು ಸಾಬೀತುಪಡಿಸಿದವು. ಇದರ ಪರಿಣಾಮವಾಗಿ, n ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಪ್ರತಿ ಥ್ರಾಕ್ಲೆಬಲ್ ಗ್ರಾಫ್ ಗರಿಷ್ಠ 2n−3 ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ ಎಂದು ಅವು ತೋರಿಸುತ್ತವೆ. ಅಂದಿನಿಂದ, ಈ ಮಿತಿಯನ್ನು ಹಲವಾರು ಬಾರಿ ಸುಧಾರಿಸಲಾಗಿದೆ. ಮೊದಲಿಗೆ, ಇದನ್ನು 3 (n−1)/2ಕ್ಕೆ ಸುಧಾರಿಸಲಾಯಿತು, ಮತ್ತು ಮತ್ತೊಂದು ಸುಧಾರಣೆಯು ಸರಿಸುಮಾರು 1.428n ಗೆ ಕಾರಣವಾಯಿತು. ಇದಲ್ಲದೆ, ನಂತರದ ಫಲಿತಾಂಶವನ್ನು ಸಾಬೀತುಪಡಿಸಲು ಬಳಸುವ ವಿಧಾನವು ಯಾವುದೇ ε> 0 ಗೆ ಒಂದು ಸೀಮಿತ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡುತ್ತದೆ, ಅದು (1 + ε) n ಗೆ ಮಿತಿಯನ್ನು ಸುಧಾರಿಸುತ್ತದೆ ಅಥವಾ ಊಹೆಯನ್ನು ನಿರಾಕರಿಸುತ್ತದೆ. ಪ್ರಸ್ತುತ ದಾಖಲೆಯು 1.3984n ಗೆ ಬದ್ಧವಾಗಿದೆ ಎಂದು ಸಾಬೀತಾಗಿದೆ. ಊಹೆಯು ತಪ್ಪಾಗಿದ್ದರೆ, ಕನಿಷ್ಠ ಪ್ರತಿ-ಉದಾಹರಣೆಯು ಶೃಂಗವನ್ನು ಹಂಚಿಕೊಳ್ಳುವ ಎರಡು ಸಮಚಕ್ರಗಳ ರೂಪವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಊಹೆಯನ್ನು ಸಾಬೀತುಪಡಿಸಲು, ಈ ರೀತಿಯ ಗ್ರಾಫ್ಗಳನ್ನು ಥ್ರ್ಯಾಕಲ್ಗಳಾಗಿ ಎಳೆಯಲು ಸಾಧ್ಯವಿಲ್ಲ ಎಂದು ಸಾಬೀತುಪಡಿಸಲು ಸಾಕು. ಉಲ್ಲೇಖಗಳು ಬಾಹ್ಯ ಕೊಂಡಿಗಳು thrackle.org-ಸಮಸ್ಯೆಯ ಬಗೆಗಿನ ಜಾಲತಾಣ ಭೂವೈಜ್ಞಾನಿಕ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಜ್ಯಾಮಿತೀಯ ಛೇದನವನ್ನು ಊಹಿಸುತ್ತದೆ