Wagner's theorem
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ವ್ಯಾಗ್ನರ್ ಅವರ ಪ್ರಮೇಯವು ಸಮತಟ್ಟಾದ ಗ್ರಾಫ್ಗಳ ಗಣಿತದ ನಿಷೇಧಿತ ಗ್ರಾಫ್ ಗುಣಲಕ್ಷಣವಾಗಿದೆ, ಇದನ್ನು ಕ್ಲಾಸ್ ವ್ಯಾಗ್ನರ್ ಅವರ ಹೆಸರಿಡಲಾಗಿದೆ, ಅದರ ಚಿಕ್ಕವುಗಳು ಕೆ5 (ಐದು ಶೃಂಗಗಳ ಮೇಲೆ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್) ಅಥವಾ ಕೆ3,3 (ಯುಟಿಲಿಟಿ ಗ್ರಾಫ್, ಆರು ಶೃಂಗಗಳ ಮೇಲೆ ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್) ಅನ್ನು ಒಳಗೊಂಡಿಲ್ಲದಿದ್ದರೆ ಮಾತ್ರ ಸೀಮಿತ ಗ್ರಾಫ್ ಸಮತಟ್ಟಾಗಿರುತ್ತದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಇದು ಗ್ರಾಫ್ ಮೈನರ್ಗಳ ಸಿದ್ಧಾಂತದ ಆರಂಭಿಕ ಫಲಿತಾಂಶಗಳಲ್ಲಿ ಒಂದಾಗಿತ್ತು ಮತ್ತು ಇದನ್ನು ರಾಬರ್ಟ್ಸನ್-ಸೈಮೂರ್ ಪ್ರಮೇಯದ ಮುಂಚೂಣಿಯಾಗಿ ಕಾಣಬಹುದು. ವ್ಯಾಖ್ಯಾನಗಳು ಮತ್ತು ಹೇಳಿಕೆ ಯುಕ್ಲಿಡಿಯನ್ ಸಮತಲದಲ್ಲಿರುವ ರೇಖಾಚಿತ್ರದ ರೇಖಾಚಿತ್ರದ ರೇಖಾಚಿತ್ರವಾಗಿದ್ದು, ಅದರ ತುದಿಗಳಿಗೆ ಬಿಂದುಗಳು ಮತ್ತು ಅದರ ಅಂಚುಗಳಿಗೆ ವಕ್ರಾಕೃತಿಗಳನ್ನು ಹೊಂದಿದ್ದು, ಎರಡು ಅಂಚುಗಳ ಜೋಡಿಗಳ ನಡುವಿನ ಏಕೈಕ ಛೇದಕಗಳು ಒಂದೇ ಅಂತ್ಯ ಬಿಂದುವಿನಲ್ಲಿ ಇರುತ್ತವೆ. ನೀಡಲಾದ ರೇಖಾಚಿತ್ರದ ಚಿಕ್ಕದು ಶೃಂಗಗಳನ್ನು ಅಳಿಸಿ, ಅಂಚುಗಳನ್ನು ಅಳಿಸಿ ಮತ್ತು ಅಂಚುಗಳನ್ನು ಕುಗ್ಗಿಸುವ ಮೂಲಕ ರೂಪುಗೊಂಡ ಮತ್ತೊಂದು ರೇಖಾಚಿತ್ರವಾಗಿದೆ. ಒಂದು ತುದಿಯನ್ನು ಸಂಕುಚಿತಗೊಳಿಸಿದಾಗ, ಅದರ ಎರಡು ಅಂತಿಮ ಬಿಂದುಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಿ ಒಂದೇ ಶೃಂಗವನ್ನು ರೂಪಿಸಲಾಗುತ್ತದೆ. ಗ್ರಾಫ್ ಮೈನರ್ ಸಿದ್ಧಾಂತದ ಕೆಲವು ಆವೃತ್ತಿಗಳಲ್ಲಿ ಸಂಕೋಚನದಿಂದ ಉಂಟಾಗುವ ಗ್ರಾಫ್ ಅನ್ನು ಸ್ವಯಂ-ಲೂಪ್ಗಳು ಮತ್ತು ಅನೇಕ ಸಮೀಪಗಳನ್ನು ತೆಗೆದುಹಾಕುವ ಮೂಲಕ ಸರಳೀಕರಿಸಲಾಗುತ್ತದೆ, ಆದರೆ ಇತರ ಆವೃತ್ತಿಗಳಲ್ಲಿ ಮಲ್ಟಿಗ್ರಾಫ್ಗಳನ್ನು ಅನುಮತಿಸಲಾಗಿದೆ, ಆದರೆ ಈ ಬದಲಾವಣೆಯು ವ್ಯಾಗ್ನರ್ ಅವರ ಪ್ರಮೇಯಕ್ಕೆ ಯಾವುದೇ ವ್ಯತ್ಯಾಸವನ್ನು ಬೀರುವುದಿಲ್ಲ. ವ್ಯಾಗ್ನರ್ ಅವರ ಪ್ರಮೇಯವು ಪ್ರತಿ ಗ್ರಾಫ್ ಪ್ಲ್ಯಾನರ್ ಎಂಬೆಡಿಂಗ್ ಅನ್ನು ಹೊಂದಿದೆ, ಅಥವಾ ಎರಡು ವಿಧಗಳಲ್ಲಿ ಒಂದಾದ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ K5 ಅಥವಾ ಸಂಪೂರ್ಣ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ K3,3 ಅನ್ನು ಹೊಂದಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. (ಒಂದೇ ರೇಖಾಚಿತ್ರವು ಎರಡೂ ರೀತಿಯ ಚಿಕ್ಕ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಹೊಂದಲು ಸಹ ಸಾಧ್ಯವಿದೆ.) ಕೊಟ್ಟಿರುವ ರೇಖಾಚಿತ್ರವು ಸಮತಟ್ಟಾಗಿದ್ದರೆ, ಅದರ ಎಲ್ಲಾ ಚಿಕ್ಕವುಗಳೂ ಸಹಃ ಶೃಂಗ ಮತ್ತು ಅಂಚಿನ ಅಳಿಸುವಿಕೆಯು ಸ್ಪಷ್ಟವಾಗಿ ಸಮತಟ್ಟನ್ನು ಕಾಪಾಡುತ್ತದೆ, ಮತ್ತು ಅಂಚಿನ ಸಂಕೋಚನವನ್ನು ಸಮತಟ್ಟನ್ನು ಸಂರಕ್ಷಿಸುವ ರೀತಿಯಲ್ಲಿ ಸಹ ಮಾಡಬಹುದು, ಸಂಕುಚಿತ ಅಂಚಿನ ಎರಡು ಅಂತಿಮ ಬಿಂದುಗಳಲ್ಲಿ ಒಂದನ್ನು ಸ್ಥಳದಲ್ಲಿ ಬಿಟ್ಟು ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ಸಂಕುಚಿತ ಅಂಚಿನ ಹಾದಿಯಲ್ಲಿ ಇತರ ಅಂತಿಮ ಬಿಂದುವಿಗೆ ತಿರುಗಿಸುವ ಮೂಲಕ. ಸಣ್ಣ-ಕನಿಷ್ಠ ಸಮತಲವಲ್ಲದ ರೇಖಾಚಿತ್ರವು ಸಮತಟ್ಟಲ್ಲದ ರೇಖಾಚಿತ್ರವಾಗಿದೆ, ಆದರೆ ಇದರಲ್ಲಿ ಎಲ್ಲಾ ಸರಿಯಾದ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರು (ಕನಿಷ್ಠ ಒಂದು ಅಳಿಸುವಿಕೆ ಅಥವಾ ಸಂಕೋಚನದಿಂದ ರೂಪುಗೊಂಡ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರು) ಸಮತಟ್ಟಾಗಿರುತ್ತಾರೆ. ವ್ಯಾಗ್ನರ್ ಅವರ ಪ್ರಮೇಯವನ್ನು ಹೇಳುವ ಮತ್ತೊಂದು ವಿಧಾನವೆಂದರೆ ಕೆ5 ಮತ್ತು ಕೆ3,3 ಎಂಬ ಎರಡು ಸಣ್ಣ-ಕನಿಷ್ಠ ಸಮತಲವಲ್ಲದ ಗ್ರಾಫ್ಗಳು ಮಾತ್ರ ಇವೆ. ಕೆಲವೊಮ್ಮೆ ವ್ಯಾಗ್ನರ್ ಪ್ರಮೇಯ ಎಂದೂ ಕರೆಯಲ್ಪಡುವ ಮತ್ತೊಂದು ಫಲಿತಾಂಶವು, ನಾಲ್ಕು-ಸಂಪರ್ಕಿತ ರೇಖಾಚಿತ್ರವು ಕೆ5 ಮೈನರ್ ಅನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ ಮಾತ್ರ ಸಮತಟ್ಟಾಗಿರುತ್ತದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಅಂದರೆ, ಹೆಚ್ಚಿನ ಮಟ್ಟದ ಸಂಪರ್ಕವನ್ನು ಊಹಿಸುವ ಮೂಲಕ, ಕೆ3,3 ನಕ್ಷೆಯನ್ನು ಗುಣಲಕ್ಷಣಗಳಲ್ಲಿ ಅನಗತ್ಯವಾಗಿಸಬಹುದು, ಕೇವಲ ಒಂದು ನಿಷೇಧಿತ ಮೈನರ್, ಕೆ5 ಅನ್ನು ಮಾತ್ರ ಬಿಡಬಹುದು. ಅದಕ್ಕೆ ಅನುಗುಣವಾಗಿ, ಕೆಲ್ಮಾನ್ಸ್-ಸೈಮೂರ್ ಊಹೆಯು, 5-ಸಂಪರ್ಕಿತ ರೇಖಾಚಿತ್ರವು ಕೆ5 ಅನ್ನು ಟೋಪೋಲಾಜಿಕಲ್ ಮೈನರ್ ಆಗಿ ಹೊಂದಿಲ್ಲದಿದ್ದರೆ ಮಾತ್ರ ಸಮತಟ್ಟಾಗಿರುತ್ತದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಇತಿಹಾಸ ಮತ್ತು ಕುರಾಟೋವ್ಸ್ಕಿಯ ಪ್ರಮೇಯಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ ವ್ಯಾಗ್ನರ್ 1937 ರಲ್ಲಿ ಎರಡೂ ಪ್ರಮೇಯಗಳನ್ನು ಪ್ರಕಟಿಸಿದರು, 1930 ರಲ್ಲಿ ಕುರಾಟೋವ್ಸ್ಕಿಯ ಪ್ರಮೇಯದ ಪ್ರಕಟಣೆಯ ನಂತರ, ಅದರ ಪ್ರಕಾರ ಗ್ರಾಫ್ ಕೆ5 ಮತ್ತು ಕೆ3,3 ಎಂಬ ಎರಡು ನಿಷೇಧಿತ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಒಂದರ ಉಪವಿಭಾಗವನ್ನು ಉಪಗ್ರಾಫ್ನಂತೆ ಹೊಂದಿಲ್ಲದಿದ್ದರೆ ಮಾತ್ರ ಸಮತಟ್ಟಾಗಿರುತ್ತದೆ. ಒಂದು ಅರ್ಥದಲ್ಲಿ, ಕುರಾಟೋವ್ಸ್ಕಿಯ ಪ್ರಮೇಯವು ವ್ಯಾಗ್ನರ್ ಅವರ ಪ್ರಮೇಯಕ್ಕಿಂತ ಪ್ರಬಲವಾಗಿದೆಃ ಉಪವಿಭಾಗ ಪ್ರಕ್ರಿಯೆಯಿಂದ ರೂಪುಗೊಂಡ ಪ್ರತಿ ಮಾರ್ಗದಲ್ಲಿ ಒಂದು ಅಂಚನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲವನ್ನೂ ಸಂಕುಚಿತಗೊಳಿಸುವ ಮೂಲಕ ಉಪವಿಭಾಗವನ್ನು ಒಂದೇ ರೀತಿಯ ಸಣ್ಣದಾಗಿ ಪರಿವರ್ತಿಸಬಹುದು, ಆದರೆ ಚಿಕ್ಕದನ್ನು ಒಂದೇ ರೀತಿಯ ಉಪವಿಭಾಗವಾಗಿ ಪರಿವರ್ತಿಸುವುದು ಯಾವಾಗಲೂ ಸಾಧ್ಯವಿಲ್ಲ. ಆದಾಗ್ಯೂ, ಕೆ5 ಮತ್ತು ಕೆ3,3 ಎಂಬ ಎರಡು ಗ್ರಾಫ್ಗಳ ಸಂದರ್ಭದಲ್ಲಿ, ಈ ಎರಡು ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಒಂದನ್ನು ಚಿಕ್ಕದಾಗಿ ಹೊಂದಿರುವ ಗ್ರಾಫ್ ಸಹ ಅವುಗಳಲ್ಲಿ ಕನಿಷ್ಠ ಒಂದನ್ನು ಉಪವಿಭಾಗವಾಗಿ ಹೊಂದಿದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸುವುದು ಸರಳವಾಗಿದೆ, ಆದ್ದರಿಂದ ಎರಡು ಪ್ರಮೇಯಗಳು ಸಮಾನವಾಗಿವೆ. ಪರಿಣಾಮಗಳು ನಾಲ್ಕು-ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ಗಳಿಗೆ ವ್ಯಾಗ್ನರ್ ಪ್ರಮೇಯದ ಬಲವಾದ ಆವೃತ್ತಿಯ ಒಂದು ಪರಿಣಾಮವೆಂದರೆ ಕೆ5 ಮೈನರ್ ಅನ್ನು ಹೊಂದಿರದ ಗ್ರಾಫ್ಗಳನ್ನು ನಿರೂಪಿಸುವುದು. ಅಂತಹ ಪ್ರತಿಯೊಂದು ರೇಖಾಚಿತ್ರವು ಸಮತಟ್ಟಾಗಿರುತ್ತದೆ ಅಥವಾ ಅದನ್ನು ಸರಳವಾದ ತುಣುಕುಗಳಾಗಿ ವಿಭಜಿಸಬಹುದು ಎಂದು ಹೇಳುವ ಮೂಲಕ ಪ್ರಮೇಯವನ್ನು ಪುನರಾವರ್ತಿಸಬಹುದು. ಈ ಕಲ್ಪನೆಯನ್ನು ಬಳಸಿಕೊಂಡು, ಕೆ5-ಮೈನರ್-ಫ್ರೀ ಗ್ರಾಫ್ಗಳನ್ನು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಎಂಟು-ವೆರ್ಟೆಕ್ಸ್ ವ್ಯಾಗ್ನರ್ ಗ್ರಾಫ್ಗಳ ಸಂಯೋಜನೆಯಾಗಿ ರಚಿಸಬಹುದಾದ ಗ್ರಾಫ್ಗಳಾಗಿ ನಿರೂಪಿಸಬಹುದು, ಇವುಗಳನ್ನು ಗುಂಪು-ಮೊತ್ತದ ಕಾರ್ಯಾಚರಣೆಗಳಿಂದ ಒಟ್ಟಿಗೆ ಅಂಟಿಸಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, K3,3 ಅನ್ನು ಈ ರೀತಿಯಲ್ಲಿ ಮೂರು ಸಮತಟ್ಟಾದ ರೇಖಾಚಿತ್ರಗಳ ಗುಂಪು-ಮೊತ್ತವಾಗಿ ರಚಿಸಬಹುದು, ಅವುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ ಚತುಷ್ಕೋಣೀಯ ರೇಖಾಚಿತ್ರ K4 ನ ನಕಲಾಗಿದೆ. ವ್ಯಾಗ್ನರ್ ಅವರ ಪ್ರಮೇಯವು ಗ್ರಾಫ್ ಮೈನರ್ಗಳ ಸಿದ್ಧಾಂತಕ್ಕೆ ಪ್ರಮುಖ ಪೂರ್ವಸೂಚಕವಾಗಿದೆ, ಇದು ಎರಡು ಆಳವಾದ ಮತ್ತು ದೂರಗಾಮಿ ಫಲಿತಾಂಶಗಳ ಪುರಾವೆಗಳಲ್ಲಿ ಕೊನೆಗೊಂಡಿತುಃ ಗ್ರಾಫ್ ರಚನೆಯ ಪ್ರಮೇಯ (ವ್ಯಾಗ್ನರ್ ಅವರ ಕೆ5-ಮೈನರ್-ಮುಕ್ತ ಗ್ರಾಫ್ಗಳ ಗುಂಪು-ಮೊತ್ತ ವಿಭಜನೆಯ ಸಾಮಾನ್ಯೀಕರಣ) ಮತ್ತು ರಾಬರ್ಟ್ಸನ್-ಸೈಮೂರ್ ಪ್ರಮೇಯ (ಪ್ಲಾನರ್ ಗ್ರಾಫ್ಗಳ ನಿಷೇಧಿತ ಸಣ್ಣ ಗುಣಲಕ್ಷಣಗಳ ಸಾಮಾನ್ಯೀಕರಣ, ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಕಾರ್ಯಾಚರಣೆಯ ಅಡಿಯಲ್ಲಿ ಮುಚ್ಚಿದ ಪ್ರತಿ ಗ್ರಾಫ್ ಕುಟುಂಬವು ಸೀಮಿತ ಸಂಖ್ಯೆಯ ನಿಷೇಧಿತ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ). ವ್ಯಾಗ್ನರ್ ಅವರ ಪ್ರಮೇಯದ ಸಾದೃಶ್ಯಗಳನ್ನು ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳ ಸಿದ್ಧಾಂತಕ್ಕೂ ವಿಸ್ತರಿಸಬಹುದುಃ ನಿರ್ದಿಷ್ಟವಾಗಿ, ಅದೇ ಎರಡು ಗ್ರಾಫ್ಗಳಾದ K5 ಮತ್ತು K3,3 (ಇತರ ಮೂರು ನಿಷೇಧಿತ ಸಂರಚನೆಗಳೊಂದಿಗೆ) ನಿಷೇಧಿತ ಮ್ಯಾಟ್ರೋಯಿಡ್ ಅಪ್ರಾಪ್ತ ವಯಸ್ಕರಿಂದ ಗ್ರಾಫಿಕ್ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳ ಗುಣಲಕ್ಷಣಗಳಲ್ಲಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತವೆ. ಉಲ್ಲೇಖಗಳು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು ಗ್ರಾಫ್ ಸಣ್ಣ ಸಿದ್ಧಾಂತ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿನ ಪ್ರಮೇಯಗಳು