Lucchesi–Younger theorem
ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳ ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ಲುಚೆಸಿ-ಯಂಗರ್ ಪ್ರಮೇಯವು ಡಿಕಟ್ಗಳು ಮತ್ತು ಡೈಜೋಯಿನ್ಗಳ ನಡುವಿನ ಸಂಬಂಧವಾಗಿದೆ. ಇದನ್ನು 1978ರಲ್ಲಿ ಕ್ಲಾಡಿಯೋ ಎಲ್. ಲುಚೆಸಿ ಮತ್ತು ಡೇನಿಯಲ್ ಎಚ್. ಯಂಗರ್ ಅವರು ಪ್ರಕಟಿಸಿದರು. ಅವರ ಪುರಾವೆಯು ಸುಮಾರು ಒಂದು ದಶಕದ ಹಿಂದೆ ಯಂಗರ್ ಮತ್ತು ನೀಲ್ ರಾಬರ್ಟ್ಸನ್ ಅವರ ಅಪ್ರಕಟಿತ ಕೃತಿಯಲ್ಲಿ ಮಂಡಿಸಿದ ಊಹೆಯನ್ನು ಪರಿಹರಿಸಿತು, ಇದು ಡೈಜೋಯಿನ್ಗಳು ಮತ್ತು ಪ್ರತಿಕ್ರಿಯೆ ಆರ್ಕ್ ಸೆಟ್ಗಳ ನಡುವಿನ ಸಮತಟ್ಟಾದ ಗ್ರಾಫ್ಗಳಲ್ಲಿನ ದ್ವಂದ್ವತೆಯಿಂದ ಪ್ರೇರೇಪಿಸಲ್ಪಟ್ಟಿದೆ. ಡಿಕೇಟ್ ಎಂದರೆ ಶೃಂಗಗಳನ್ನು ಎರಡು ಉಪಗುಂಪುಗಳಾಗಿ ವಿಭಜಿಸುವುದು, ಅಂದರೆ ವಿಭಜನೆಯನ್ನು ದಾಟುವ ಎಲ್ಲಾ ಅಂಚುಗಳು ಒಂದೇ ದಿಕ್ಕಿನಲ್ಲಿ ಹಾಗೆ ಮಾಡುತ್ತವೆ. ಡಿಜಾಯಿನ್ ಎಂಬುದು ಅಂಚುಗಳ ಉಪವಿಭಾಗವಾಗಿದ್ದು, ಸಂಕುಚಿತಗೊಂಡಾಗ, ಬಲವಾಗಿ ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ ಅನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ; ಸಮಾನವಾಗಿ, ಇದು ಪ್ರತಿ ಡಿಕೇಟ್ನಿಂದ ಕನಿಷ್ಠ ಒಂದು ಅಂಚನ್ನು ಒಳಗೊಂಡಿರುವ ಅಂಚುಗಳ ಉಪವಿಭಾಗವಾಗಿದೆ. ಡಿಕಟ್ಗಳ ಸಂಗ್ರಹವು ಎಲ್ಲಾ ಬೇರೆಯಾಗಿದ್ದರೆ, ಯಾವುದೇ ಡಿಜಾಯಿನ್ ಈ ಪ್ರತಿಯೊಂದು ಡಿಕಟ್ಗಳಿಂದ ಕನಿಷ್ಠ ಒಂದು ಅಂಚನ್ನು ಹೊಂದಿರಬೇಕು ಮತ್ತು ಸಂಗ್ರಹದ ಗಾತ್ರಕ್ಕೆ ಸಮನಾದ ಗಾತ್ರವನ್ನು ಹೊಂದಿರಬೇಕು. ಆದ್ದರಿಂದ, ಯಾವುದೇ ಗ್ರಾಫ್ನಲ್ಲಿನ ಡಿಸ್ಜಾಯಿಂಟ್ ಡಿಕಟ್ಗಳ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯು ಡಿಜಾಯಿನ್ನ ಕನಿಷ್ಠ ಗಾತ್ರಕ್ಕಿಂತ ಕಡಿಮೆ ಅಥವಾ ಸಮನಾಗಿರಬೇಕು. ಈ ಸಂಬಂಧವು ಯಾವಾಗಲೂ ಸಮಾನವಾಗಿರುತ್ತದೆ ಎಂದು ಲುಚೆಸಿ-ಯಂಗರ್ ಪ್ರಮೇಯವು ಹೇಳುತ್ತದೆ. ಡಿಜಾಯಿನ್ನ ಕನಿಷ್ಠ ಗಾತ್ರವು ನಿರ್ದಿಷ್ಟ ಗ್ರಾಫ್ನಲ್ಲಿ ಕಂಡುಬರುವ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಡಿಸ್ಜಾಯಿಂಟ್ ಡಿಕಟ್ಗಳಿಗೆ ಸಮನಾಗಿರುತ್ತದೆ. ಉಲ್ಲೇಖಗಳ ನಿರ್ದೇಶನದ ರೇಖಾಚಿತ್ರಗಳು