Woodall's conjecture
ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳ ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ವುಡಾಲ್ನ ಊಹೆಯು ಡಿಕಟ್ಗಳು ಮತ್ತು ಡಿಜಾಯಿನ್ಗಳ ನಡುವಿನ ಸಾಬೀತಾಗದ ಸಂಬಂಧವಾಗಿದೆ. ಇದನ್ನು 1976 ರಲ್ಲಿ ಡೌಗ್ಲಾಸ್ ವುಡಾಲ್ ಅವರು ಪ್ರದರ್ಶಿಸಿದರು. ಹೇಳಿಕೆಯು ಡಿಕ್ಟ್ ಎಂದರೆ ಶೃಂಗಗಳನ್ನು ಎರಡು ಉಪಗುಂಪುಗಳಾಗಿ ವಿಭಜಿಸುವುದು, ಅಂದರೆ ವಿಭಜನೆಯನ್ನು ದಾಟುವ ಎಲ್ಲಾ ಅಂಚುಗಳು ಒಂದೇ ದಿಕ್ಕಿನಲ್ಲಿ ಹಾಗೆ ಮಾಡುತ್ತವೆ. ಡಿಜಾಯಿನ್ ಎಂಬುದು ಅಂಚುಗಳ ಉಪವಿಭಾಗವಾಗಿದ್ದು, ಸಂಕುಚಿತಗೊಂಡಾಗ, ಬಲವಾಗಿ ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ ಅನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ; ಸಮಾನವಾಗಿ, ಇದು ಪ್ರತಿ ಡಿಕೇಟ್ನಿಂದ ಕನಿಷ್ಠ ಒಂದು ಅಂಚನ್ನು ಒಳಗೊಂಡಿರುವ ಅಂಚುಗಳ ಉಪವಿಭಾಗವಾಗಿದೆ. ಒಂದು ಅಣೆಕಟ್ಟಿನಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಅಂಚುಗಳಿದ್ದರೆ, ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಹೆಚ್ಚಿನ ಬೇರ್ಪಡುವಿಕೆಗಳು ಇರಬಹುದು, ಏಕೆಂದರೆ ಪ್ರತಿಯೊಂದೂ ಚಿಕ್ಕ ಅಣೆಕಟ್ಟೆಯಿಂದ ವಿಭಿನ್ನವಾದ ಅಂಚನ್ನು ಹೊಂದಿರಬೇಕು. ವುಡಾಲ್ನ ಊಹೆಯು, ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಬೇರ್ಪಡುವ ಜೋಡಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಯಾವಾಗಲೂ ಸಾಧ್ಯವಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಅಂದರೆ, ಯಾವುದೇ ನಿರ್ದೇಶನದ ರೇಖಾಚಿತ್ರವು, ಒಂದು ಕೊಳವೆಯಲ್ಲಿನ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಅಂಚುಗಳು, ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಕಂಡುಬರುವ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಬೇರ್ಪಡುವ ದ್ವಿಜೋಡುಗಳಿಗೆ ಸಮನಾಗಿರುತ್ತದೆ (ದ್ವಿಜೋಡುಗಳ ಪ್ಯಾಕಿಂಗ್). ಭಾಗಶಃ ಫಲಿತಾಂಶಗಳು ಕನಿಷ್ಠ ಎರಡು ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ನಿರ್ದೇಶಿತ ರೇಖಾಚಿತ್ರಗಳಿಗೆ ಈ ಪ್ರಮೇಯವು ನಿಜವಾಗಿದೆ ಎಂಬುದು ಜಾನಪದ ಕಥೆಯ ಫಲಿತಾಂಶವಾಗಿದೆ. ಸಮಸ್ಯೆಯ ಯಾವುದೇ ನಿದರ್ಶನವನ್ನು ಸಾಂದ್ರೀಕರಣವನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ ನಿರ್ದೇಶಿತ ಅಸೈಕ್ಲಿಕ್ ಗ್ರಾಫ್ಗೆ ಕಡಿಮೆ ಮಾಡಬಹುದು, ಬಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದ ಪ್ರತಿಯೊಂದು ಘಟಕವನ್ನು ಒಂದೇ ಶೃಂಗಕ್ಕೆ ಸಂಕುಚಿತಗೊಳಿಸುವ ಮೂಲಕ ರಚಿಸಲಾದ ಗ್ರಾಫ್. ಪ್ರಮೇಯವು ನಿಜವೆಂದು ಸಾಬೀತಾಗಿರುವ ಗ್ರಾಫ್ಗಳ ಮತ್ತೊಂದು ವರ್ಗವೆಂದರೆ ನಿರ್ದೇಶಿತ ಅಸೈಕ್ಲಿಕ್ ಗ್ರಾಫ್ಗಳು, ಇದರಲ್ಲಿ ಪ್ರತಿ ಮೂಲ ಶೃಂಗವು (ಒಳಬರುವ ಅಂಚುಗಳಿಲ್ಲದ ಶೃಂಗ) ಪ್ರತಿ ಸಿಂಕ್ ಶೃಂಗಕ್ಕೆ (ಹೊರಹೋಗುವ ಅಂಚುಗಳಿಲ್ಲದ ಶೃಂಗ) ಮಾರ್ಗವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಸಂಬಂಧಿತ ಫಲಿತಾಂಶಗಳು ಜ್ಯಾಕ್ ಎಡ್ಮಂಡ್ಸ್ ಮತ್ತು ರಿಕ್ ಗೈಲ್ಸ್ ಅವರು ಮಂಡಿಸಿದ ಊಹೆಯ ಭಾಗಶಃ ತೂಕದ ಆವೃತ್ತಿಯನ್ನು ಅಲೆಕ್ಸಾಂಡರ್ ಶ್ರೈಜ್ವರ್ ನಿರಾಕರಿಸಿದರು. ಇನ್ನೊಂದು ದಿಕ್ಕಿನಲ್ಲಿ, ಲೂಚೆಸಿ-ಯಂಗರ್ ಪ್ರಮೇಯವು ಒಂದು ಡೈಜೋಯಿನ್ನ ಕನಿಷ್ಠ ಗಾತ್ರವು ನಿರ್ದಿಷ್ಟ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಕಂಡುಬರುವ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಡಿಸ್ಜಾಯಿಂಟ್ ಡಿಕಟ್ಗಳಿಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ನಿರ್ದೇಶಿತ ರೇಖಾಚಿತ್ರಗಳು