Bipartite dimension
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಮತ್ತು ಕಾಂಬಿನೇಟೋರಿಯಲ್ ಆಪ್ಟಿಮೈಸೇಶನ್ನ ಗಣಿತದ ಕ್ಷೇತ್ರಗಳಲ್ಲಿ, G = (V, E) ಗ್ರಾಫ್ನ ಬೈಪಾರ್ಟೈಟ್ ಆಯಾಮ ಅಥವಾ ಬೈಕ್ಲಿಕ್ ಕವರ್ ಸಂಖ್ಯೆ ಬೈಕ್ಲಿಕ್ಗಳ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯಾಗಿದೆ (ಅದು ಸಂಪೂರ್ಣ ಬೈಪಾರ್ಟೈಟ್ ಸಬ್ಗ್ರಾಫ್ಗಳು), ಇದು Eಯಲ್ಲಿನ ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ಒಳಗೊಳ್ಳಲು ಅಗತ್ಯವಾಗಿರುತ್ತದೆ. Gಯಲ್ಲಿನ ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ಒಳಗೊಂಡ ಬೈಕ್ಲಿಕ್ಗಳ ಸಂಗ್ರಹವನ್ನು ಬೈಕ್ಲಿಕ್ ಎಡ್ಜ್ ಕವರ್ ಅಥವಾ ಕೆಲವೊಮ್ಮೆ ಬೈಕ್ಲಿಕ್ ಕವರ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಜಿ ಯ ಉಭಯಪಕ್ಷೀಯ ಆಯಾಮವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಡಿ (ಜಿ) ಚಿಹ್ನೆಯಿಂದ ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆ ಬೈಕ್ಲಿಕ್ ಎಡ್ಜ್ ಕವರ್ಗೆ ಒಂದು ಉದಾಹರಣೆಯನ್ನು ಈ ಕೆಳಗಿನ ರೇಖಾಚಿತ್ರಗಳಲ್ಲಿ ನೀಡಲಾಗಿದೆಃ ಕೆಲವು ರೇಖಾಚಿತ್ರಗಳಿಗೆ ಬೈಪಾರ್ಟೈಟ್ ಆಯಾಮ ಸೂತ್ರಗಳು ಎನ್-ವೆರ್ಟೆಕ್ಸ್ ಸಂಪೂರ್ಣ ರೇಖಾಚಿತ್ರದ ಬೈಪಾರ್ಟೈಟ್ ಆಯಾಮವು. 2n-ವೆರ್ಟೆಕ್ಸ್ ಕ್ರೌನ್ ಗ್ರಾಫ್ನ ಉಭಯಪಕ್ಷೀಯ ಆಯಾಮವು ಸಮನಾಗಿರುತ್ತದೆ, ಇದು ಕೇಂದ್ರ ದ್ವಿಪದ ಗುಣಾಂಕದ ವಿಲೋಮ ಕಾರ್ಯವಾಗಿದೆ. ಜಾಲರಿ ರೇಖಾಚಿತ್ರದ ಉಭಯಪಕ್ಷೀಯ ಆಯಾಮವು, ಸಮವಾಗಿದ್ದರೆ ಮತ್ತು ಕೆಲವು ಪೂರ್ಣಾಂಕಗಳಿಗೆ; ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ. ಕೆಲವು ವಿಶೇಷ ಗ್ರಾಫ್ಗಳಿಗೆ ಉಭಯಪಕ್ಷೀಯ ಆಯಾಮವನ್ನು ನಿರ್ಧರಿಸಿ. ಉದಾಹರಣೆಗೆ, ಮಾರ್ಗವು ಹೊಂದಿದೆ ಮತ್ತು ಚಕ್ರವು ಹೊಂದಿದೆ. ದ್ವಿ-ಪಕ್ಷೀಯ ಆಯಾಮವನ್ನು ಗಣನೆ ಮಾಡುವುದು ಒಂದು ನಿರ್ದಿಷ್ಟ ಗ್ರಾಫ್ ಜಿಗಾಗಿ ದ್ವಿ-ಪಕ್ಷೀಯ ಆಯಾಮವನ್ನು ನಿರ್ಧರಿಸುವ ಗಣನೆಯ ಕಾರ್ಯವು ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಉಭಯಪಕ್ಷೀಯ ಆಯಾಮಕ್ಕೆ ಸಂಬಂಧಿಸಿದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯನ್ನು ಈ ರೀತಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದುಃ ತ್ವರಿತಃ ಒಂದು ರೇಖಾಚಿತ್ರ ಮತ್ತು ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕ. ಪ್ರಶ್ನೆಃ ಹೆಚ್ಚಿನ ಬೈಕ್ಲಿಕ್ಗಳನ್ನು ಹೊಂದಿರುವ ಬೈಕ್ಲಿಕ್ ಅಂಚಿನ ಹೊದಿಕೆಯನ್ನು ಜಿ ಒಪ್ಪಿಕೊಳ್ಳುತ್ತದೆಯೇ? ಈ ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ.-ಪರಿಪೂರ್ಣತೆಯ ಕುರಿತಾದ ಗ್ಯಾರಿ ಮತ್ತು ಜಾನ್ಸನ್ ಅವರ ಶಾಸ್ತ್ರೀಯ ಪುಸ್ತಕದಲ್ಲಿ ಜಿ. ಟಿ. 18 ಸಮಸ್ಯೆಯಾಗಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ಇದು ಸೀಮಿತ ಗುಂಪುಗಳ ಕುಟುಂಬಗಳ ಮೇಲೆ ಮತ್ತೊಂದು ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯ ನೇರವಾದ ಸುಧಾರಣೆಯಾಗಿದೆ. ಸೆಟ್ ಬೇಸಿಸ್ ಸಮಸ್ಯೆಯು ಗ್ಯಾರಿ ಮತ್ತು ಜಾನ್ಸನ್ ಅವರ ಪುಸ್ತಕದಲ್ಲಿ ಎಸ್. ಪಿ. 7 ಸಮಸ್ಯೆಯಾಗಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತದೆ. ಇಲ್ಲಿ, ಒಂದು ಸೀಮಿತ ಗುಂಪಿನ ಉಪಗುಂಪುಗಳ ಕುಟುಂಬಕ್ಕೆ, ಒಂದು ಸೆಟ್ ಬೇಸಿಸ್ ಎಂದರೆ ಅದರ ಉಪಗುಂಪುಗಳ ಮತ್ತೊಂದು ಕುಟುಂಬವಾಗಿದೆ, ಅಂದರೆ ಪ್ರತಿ ಸೆಟ್ ಅನ್ನು ಕೆಲವು ಬೇಸಿಸ್ ಅಂಶಗಳ ಒಕ್ಕೂಟ ಎಂದು ವಿವರಿಸಬಹುದು. ಸೆಟ್ ಬೇಸಿಸ್ ಸಮಸ್ಯೆಯನ್ನು ಈಗ ಈ ಕೆಳಗಿನಂತೆ ನೀಡಲಾಗಿದೆಃ ತ್ವರಿತಃ ಒಂದು ಸೀಮಿತ ಸೆಟ್, ಉಪಗುಂಪುಗಳ ಒಂದು ಕುಟುಂಬ, ಮತ್ತು ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕ k. ಪ್ರಶ್ನೆಃ ಗಾತ್ರಕ್ಕೆ ಒಂದು ಸೆಟ್ ಬೇಸಿಸ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆಯೇ? ಅದರ ಹಿಂದಿನ ಸೂತ್ರೀಕರಣದಲ್ಲಿ, ಈ ಸಮಸ್ಯೆಯು ಉಭಯಪಕ್ಷೀಯ ರೇಖಾಚಿತ್ರಗಳಿಗೂ ಸಹ ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿದೆ ಎಂದು ಸಾಬೀತಾಯಿತು. ಒಂದು ಸೆಟ್ ಬೇಸಿಸ್ ಸಮಸ್ಯೆಯಾಗಿ ಸೂತ್ರೀಕರಣವು ಮೊದಲು ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿದೆ ಎಂದು ಸಾಬೀತಾಯಿತು. ನಾವು ನಮ್ಮ ಗಮನವನ್ನು ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ಗಳಿಗೆ ಸೀಮಿತಗೊಳಿಸಿದ್ದರೂ ಸಹ, ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿ ಉಳಿದಿದೆ, ಅದರ ಉಭಯಪಕ್ಷೀಯ ಆಯಾಮವು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ ಎಂದು ಖಾತರಿಪಡಿಸುತ್ತದೆ, ಎನ್ ನಿರ್ದಿಷ್ಟ ಸಮಸ್ಯೆಯ ಉದಾಹರಣೆಯ ಗಾತ್ರವನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಧನಾತ್ಮಕ ಬದಿಯಲ್ಲಿ, ಈ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ದ್ವಿದಲೀಯ ಡೊಮಿನೊ-ಮುಕ್ತ ರೇಖಾಚಿತ್ರಗಳಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳ ಅಸ್ತಿತ್ವಕ್ಕೆ ಸಂಬಂಧಿಸಿದಂತೆ, ಸಮಸ್ಯೆಯನ್ನು ಸರಿಯಾಗಿ ಅಂದಾಜು ಮಾಡಲು ಸಾಧ್ಯವಿಲ್ಲ ಎಂದು ಸಾಬೀತುಪಡಿಸಲಾಗಿದೆ (ಪಿ § ಎನ್. ಪಿ. ಎಂದು ಊಹಿಸಿ). ವಾಸ್ತವವಾಗಿ, ಉಭಯಪಕ್ಷೀಯ ಆಯಾಮವು ಈಗಾಗಲೇ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ಗಳಿಗೆ, ಪ್ರತಿ ಸ್ಥಿರದೊಳಗೆ ಅಂದಾಜು ಮಾಡಲು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ. ಇದಕ್ಕೆ ವ್ಯತಿರಿಕ್ತವಾಗಿ, ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಬಹುದಾದ ಸ್ಥಿರ-ನಿಯತಾಂಕ ಎಂದು ಸಾಬೀತುಪಡಿಸುವುದು ಕರ್ನಲೈಸೇಶನ್ ಕ್ರಮಾವಳಿಗಳನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸುವ ಒಂದು ಅಭ್ಯಾಸವಾಗಿದೆ, ಇದು ಪಠ್ಯಪುಸ್ತಕದಲ್ಲಿ ಕಾಣಿಸುತ್ತದೆ. ಪರಿಣಾಮವಾಗಿ ಬರುವ ಕರ್ನಲ್ನ ಗಾತ್ರದ ಮೇಲೆ ಕಾಂಕ್ರೀಟ್ ಬಂಧವನ್ನು ಸಹ ಒದಗಿಸುತ್ತದೆ, ಇದನ್ನು ಈ ಮಧ್ಯೆ ಸುಧಾರಿಸಲಾಗಿದೆ. ವಾಸ್ತವವಾಗಿ, n ಶೃಂಗಗಳ ಮೇಲೆ ನೀಡಲಾದ ಉಭಯಪಕ್ಷೀಯ ರೇಖಾಚಿತ್ರಕ್ಕೆ, ಅದರ ಉಭಯಪಕ್ಷೀಯ ಆಯಾಮವು ಗರಿಷ್ಠ k ಅನ್ವಯಗಳಾಗಿದೆಯೇ ಎಂಬುದನ್ನು ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ನಿರ್ಧರಿಸಬಹುದು. ಉದಾಹರಣೆಗೆ, ಕಂಪ್ಯೂಟರ್ ವ್ಯವಸ್ಥೆಗಳಲ್ಲಿ, ವ್ಯವಸ್ಥೆಯ ವಿವಿಧ ಬಳಕೆದಾರರಿಗೆ ವಿವಿಧ ಸಂಪನ್ಮೂಲಗಳನ್ನು ಪ್ರವೇಶಿಸಲು ಅನುಮತಿಸಬಹುದು ಅಥವಾ ಅನುಮತಿಸಲಾಗುವುದಿಲ್ಲ. ಪಾತ್ರ-ಆಧಾರಿತ ಪ್ರವೇಶ ನಿಯಂತ್ರಣ ವ್ಯವಸ್ಥೆಯಲ್ಲಿ, ಒಂದು ಪಾತ್ರವು ಸಂಪನ್ಮೂಲಗಳ ಗುಂಪಿಗೆ ಪ್ರವೇಶದ ಹಕ್ಕುಗಳನ್ನು ಒದಗಿಸುತ್ತದೆ. ಒಬ್ಬ ಬಳಕೆದಾರನು ಅನೇಕ ಪಾತ್ರಗಳನ್ನು ಹೊಂದಬಹುದು, ಮತ್ತು ಅವನ ಕೆಲವು ಪಾತ್ರಗಳಿಂದ ನೀಡಲಾದ ಎಲ್ಲಾ ಸಂಪನ್ಮೂಲಗಳನ್ನು ಪ್ರವೇಶಿಸಲು ಅವನಿಗೆ ಅನುಮತಿ ಇದೆ. ಅಲ್ಲದೆ, ಒಂದು ಪಾತ್ರವು ಅನೇಕ ಬಳಕೆದಾರರ ಒಡೆತನದಲ್ಲಿರಬಹುದು. ಪಾತ್ರದ ಗಣಿಗಾರಿಕೆಯ ಸಮಸ್ಯೆಯು ಕನಿಷ್ಠ ಪಾತ್ರಗಳ ಗುಂಪನ್ನು ಕಂಡುಹಿಡಿಯುವುದು, ಅಂದರೆ ಪ್ರತಿಯೊಬ್ಬ ಬಳಕೆದಾರರಿಗೆ, ಅವರ ಪಾತ್ರಗಳು ಒಟ್ಟಾಗಿ ಎಲ್ಲಾ ನಿರ್ದಿಷ್ಟ ಸಂಪನ್ಮೂಲಗಳಿಗೆ ಪ್ರವೇಶವನ್ನು ನೀಡುತ್ತವೆ. ವ್ಯವಸ್ಥೆಯಲ್ಲಿನ ಸಂಪನ್ಮೂಲಗಳ ಗುಂಪಿನೊಂದಿಗೆ ಬಳಕೆದಾರರ ಸಮೂಹವು ಸ್ವಾಭಾವಿಕವಾಗಿ ಉಭಯಪಕ್ಷೀಯ ರೇಖಾಚಿತ್ರವನ್ನು ಪ್ರೇರೇಪಿಸುತ್ತದೆ, ಅದರ ಅಂಚುಗಳು ಅನುಮತಿಗಳಾಗಿವೆ. ಈ ರೇಖಾಚಿತ್ರದಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ದ್ವಿಗುಣವು ಒಂದು ಸಂಭಾವ್ಯ ಪಾತ್ರವಾಗಿದೆ, ಮತ್ತು ಪಾತ್ರದ ಗಣಿಗಾರಿಕೆಯ ಸಮಸ್ಯೆಗೆ ಸೂಕ್ತವಾದ ಪರಿಹಾರಗಳು ನಿಖರವಾಗಿ ಕನಿಷ್ಠ ದ್ವಿಗುಣ ಅಂಚಿನ ಹೊದಿಕೆಗಳಾಗಿವೆ. ಇದೇ ರೀತಿಯ ಸನ್ನಿವೇಶವು ಕಂಪ್ಯೂಟರ್ ಭದ್ರತೆಯಲ್ಲಿ, ಹೆಚ್ಚು ನಿರ್ದಿಷ್ಟವಾಗಿ ಸುರಕ್ಷಿತ ಪ್ರಸಾರದಲ್ಲಿ ತಿಳಿದಿದೆ. ಆ ಸೆಟಪ್ನಲ್ಲಿ, ಅಸುರಕ್ಷಿತ ಚಾನೆಲ್ ಮೂಲಕ ಸ್ವೀಕರಿಸುವವರ ಗುಂಪಿಗೆ ಹಲವಾರು ಸಂದೇಶಗಳನ್ನು ಕಳುಹಿಸಬೇಕಾಗುತ್ತದೆ. ಉದ್ದೇಶಿತ ಸ್ವೀಕರಿಸುವವರಿಗೆ ಮಾತ್ರ ತಿಳಿದಿರುವ ಕೆಲವು ಕ್ರಿಪ್ಟೋಗ್ರಾಫಿಕ್ ಕೀಲಿಯನ್ನು ಬಳಸಿಕೊಂಡು ಪ್ರತಿ ಸಂದೇಶವನ್ನು ಎನ್ಕ್ರಿಪ್ಟ್ ಮಾಡಬೇಕಾಗುತ್ತದೆ. ಪ್ರತಿ ರಿಸೀವರ್ ಅನೇಕ ಗೂಢಲಿಪೀಕರಣ ಕೀಲಿಗಳನ್ನು ಹೊಂದಿರಬಹುದು ಮತ್ತು ಪ್ರತಿ ಕೀಲಿಗಳನ್ನು ಅನೇಕ ರಿಸೀವರ್ಗಳಿಗೆ ವಿತರಿಸಲಾಗುತ್ತದೆ. ಸುರಕ್ಷಿತ ಪ್ರಸರಣವನ್ನು ಖಾತ್ರಿಪಡಿಸಿಕೊಳ್ಳಲು ಕನಿಷ್ಠ ಗೂಢಲಿಪೀಕರಣ ಕೀಲಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಅತ್ಯುತ್ತಮ ಪ್ರಮುಖ ಪೀಳಿಗೆಯ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಮೇಲಿನಂತೆ, ಸಮಸ್ಯೆಯನ್ನು ಉಭಯಪಕ್ಷೀಯ ರೇಖಾಚಿತ್ರವನ್ನು ಬಳಸಿಕೊಂಡು ರೂಪಿಸಬಹುದು, ಅದರ ಕನಿಷ್ಠ ಬೈಕ್ಲಿಕ್ ಎಡ್ಜ್ ಕವರ್ಗಳು ಆಪ್ಟಿಮಮ್ ಕೀ ಜನರೇಷನ್ ಸಮಸ್ಯೆಯ ಪರಿಹಾರಗಳೊಂದಿಗೆ ಹೊಂದಿಕೆಯಾಗುತ್ತವೆ. ಜೀವಶಾಸ್ತ್ರದಲ್ಲಿ ಬೇರೆ ಅನ್ವಯವಿದೆ, ಅಲ್ಲಿ ಕನಿಷ್ಠ ಬೈಕ್ಲಿಕ್ ಎಡ್ಜ್ ಕವರ್ಗಳನ್ನು ಮಾನವ ಲ್ಯುಕೋಸೈಟ್ ಆಂಟಿಜೆನ್ (ಎಚ್ಎಲ್ಎ) ಸೆರೋಲಜಿಯ ಗಣಿತದ ಮಾದರಿಗಳಲ್ಲಿ ಬಳಸಲಾಗುತ್ತದೆ. ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳ ಪಟ್ಟಿಯನ್ನು ಸಹ ನೋಡಿ ಇಂಟರ್ಸೆಕ್ಷನ್ ಸಂಖ್ಯೆ (ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ), ಗ್ರಾಫ್ ಉಲ್ಲೇಖಗಳ ಅಂಚುಗಳನ್ನು ಒಳಗೊಳ್ಳಲು ಅಗತ್ಯವಿರುವ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಗುಂಪುಗಳು. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಡೇವಿಡ್ ಎಪ್ಸ್ಟೀನ್ ಅವರ ಉಭಯಪಕ್ಷೀಯ ಆಯಾಮದ ಬಗ್ಗೆ ಬ್ಲಾಗ್ ನಮೂದು ಎನ್. ಪಿ.-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳು ಗ್ರಾಫ್ ಇನ್ವೇರಿಯಂಟ್ಸ್ ಬೈಪಾರ್ಟೈಟ್ ಗ್ರಾಫ್ಗಳು ಸಮಸ್ಯೆಗಳನ್ನು ಒಳಗೊಂಡಿವೆ