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