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