Split graph
ಗಣಿತಶಾಸ್ತ್ರದ ಒಂದು ಶಾಖೆಯಾದ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ವಿಭಜಿತ ಗ್ರಾಫ್ ಎಂದರೆ ಶೃಂಗಗಳನ್ನು ಒಂದು ಗುಂಪು ಮತ್ತು ಸ್ವತಂತ್ರ ಗುಂಪಾಗಿ ವಿಂಗಡಿಸಬಹುದಾದ ಗ್ರಾಫ್ ಆಗಿದೆ. ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ಗಳನ್ನು ಮೊದಲು ಅಧ್ಯಯನ ಮಾಡಿದರು ಮತ್ತು ಸ್ವತಂತ್ರವಾಗಿ ಪರಿಚಯಿಸಿದರು. ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ ಒಂದಕ್ಕಿಂತ ಹೆಚ್ಚು ವಿಭಾಗಗಳನ್ನು ಒಂದು ಗುಂಪು ಮತ್ತು ಸ್ವತಂತ್ರ ಗುಂಪಿಗೆ ಹೊಂದಿರಬಹುದು; ಉದಾಹರಣೆಗೆ, ಮಾರ್ಗವು ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ ಆಗಿದೆ, ಅದರ ಶೃಂಗಗಳನ್ನು ಮೂರು ವಿಭಿನ್ನ ರೀತಿಯಲ್ಲಿ ವಿಂಗಡಿಸಬಹುದುಃ ಗುಂಪು ಮತ್ತು ಸ್ವತಂತ್ರ ಸೆಟ್ ಗುಂಪು ಮತ್ತು ಸ್ವತಂತ್ರ ಸೆಟ್ ಗುಂಪು ಮತ್ತು ಸ್ವತಂತ್ರ ಸೆಟ್ ಗುಂಪು ಮತ್ತು ಸ್ವತಂತ್ರ ಸೆಟ್ ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ಗಳನ್ನು ಅವುಗಳ ನಿಷೇಧಿತ ಪ್ರೇರಿತ ಉಪಗ್ರಾಫ್ಗಳ ಪರಿಭಾಷೆಯಲ್ಲಿ ನಿರೂಪಿಸಬಹುದುಃ ಯಾವುದೇ ಪ್ರೇರಿತ ಉಪಗ್ರಾಫ್ ನಾಲ್ಕು ಅಥವಾ ಐದು ಶೃಂಗಗಳ ಮೇಲೆ ಚಕ್ರವಾಗಿರದಿದ್ದರೆ ಅಥವಾ ಬೇರ್ಪಡಿಸಿದ ಅಂಚುಗಳ ಜೋಡಿಯಾಗಿದ್ದರೆ ಮಾತ್ರ ಗ್ರಾಫ್ ಅನ್ನು ವಿಭಜಿಸಲಾಗುತ್ತದೆ (4-ಚಕ್ರದ ಪೂರಕ). ಇತರ ಗ್ರಾಫ್ ಕುಟುಂಬಗಳಿಗೆ ಸಂಬಂಧ ವ್ಯಾಖ್ಯಾನದಿಂದ, ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ಗಳನ್ನು ಸ್ಪಷ್ಟವಾಗಿ ಪೂರಕತೆಯ ಅಡಿಯಲ್ಲಿ ಮುಚ್ಚಲಾಗಿದೆ. ವಿಭಜಿತ ರೇಖಾಚಿತ್ರಗಳ ಮತ್ತೊಂದು ಗುಣಲಕ್ಷಣವು ಪೂರಕತೆಯನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆಃ ಅವು ಸ್ವರಮೇಳದ ರೇಖಾಚಿತ್ರಗಳಾಗಿದ್ದು ಅವುಗಳ ಪೂರಕಗಳೂ ಸಹ ಸ್ವರಮೇಳಗಳಾಗಿರುತ್ತವೆ. ಸ್ವರಮೇಳದ ರೇಖಾಚಿತ್ರಗಳು ಮರಗಳ ಉಪವೃಕ್ಷಗಳ ಛೇದಕ ರೇಖಾಚಿತ್ರಗಳಂತೆಯೇ, ವಿಭಜಿತ ರೇಖಾಚಿತ್ರಗಳು ನಕ್ಷತ್ರ ರೇಖಾಚಿತ್ರಗಳ ವಿಭಿನ್ನ ತಲಾಧಾರಗಳ ಛೇದಕ ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ. ಬಹುತೇಕ ಎಲ್ಲಾ ಸ್ವರಮೇಳದ ರೇಖಾಚಿತ್ರಗಳು ವಿಭಜಿತ ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ; ಅಂದರೆ, n ಅನಂತಕ್ಕೆ ಹೋದ ಮಿತಿಯಲ್ಲಿ, ವಿಭಜಿತವಾಗಿರುವ n-ವೆರ್ಟೆಕ್ಸ್ ಸ್ವರಮೇಳದ ರೇಖಾಚಿತ್ರಗಳ ಭಾಗವು ಒಂದನ್ನು ಸಮೀಪಿಸುತ್ತದೆ. ಸ್ವರಮೇಳದ ರೇಖಾಚಿತ್ರಗಳು ಪರಿಪೂರ್ಣವಾಗಿರುವುದರಿಂದ, ವಿಭಜಿತ ರೇಖಾಚಿತ್ರಗಳೂ ಸಹ ಪರಿಪೂರ್ಣವಾಗಿರುತ್ತವೆ. ಡಬಲ್ ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ಗಳು, ಪ್ರತಿ ಶೃಂಗವನ್ನು ದ್ವಿಗುಣಗೊಳಿಸುವ ಮೂಲಕ ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ಗಳಿಂದ ಪಡೆದ ಗ್ರಾಫ್ಗಳ ಒಂದು ಕುಟುಂಬವಾಗಿದೆ (ಆದ್ದರಿಂದ ಕ್ಲಿಕ್ ಆಂಟಿಮ್ಯಾಚಿಂಗ್ ಅನ್ನು ಪ್ರೇರೇಪಿಸುತ್ತದೆ ಮತ್ತು ಸ್ವತಂತ್ರ ಸೆಟ್ ಹೊಂದಾಣಿಕೆಯನ್ನು ಪ್ರೇರೇಪಿಸುತ್ತದೆ), ಇದು ಪರಿಪೂರ್ಣ ಗ್ರಾಫ್ಗಳ ಐದು ಮೂಲ ವರ್ಗಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ, ಇದರಿಂದ ಇತರ ಎಲ್ಲವನ್ನು ರಚಿಸಬಹುದು ಪ್ರಬಲ ಪರಿಪೂರ್ಣ ಗ್ರಾಫ್ ಪ್ರಮೇಯದಿಂದ ಪುರಾವೆ. ಒಂದು ರೇಖಾಚಿತ್ರವು ವಿಭಜಿತ ರೇಖಾಚಿತ್ರ ಮತ್ತು ಮಧ್ಯಂತರ ರೇಖಾಚಿತ್ರ ಎರಡೂ ಆಗಿದ್ದರೆ, ಅದರ ಪೂರಕವು ವಿಭಜಿತ ರೇಖಾಚಿತ್ರ ಮತ್ತು ತುಲನಾತ್ಮಕ ರೇಖಾಚಿತ್ರ ಎರಡೂ ಆಗಿರುತ್ತದೆ. ವಿಭಜಿತ ಹೋಲಿಕೆಯ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಆದ್ದರಿಂದ ವಿಭಜಿತ ಮಧ್ಯಂತರ ಗ್ರಾಫ್ಗಳನ್ನು ಮೂರು ನಿಷೇಧಿತ ಪ್ರೇರಿತ ಉಪಗ್ರಾಫ್ಗಳ ಗುಂಪಿನ ಪರಿಭಾಷೆಯಲ್ಲಿ ನಿರೂಪಿಸಬಹುದು. ವಿಭಜಿತ ರೇಖಾಚಿತ್ರಗಳು ನಿಖರವಾಗಿ ಮಿತಿ ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ. ವಿಭಜಿತ ಕ್ರಮಪಲ್ಲಟನೆ ರೇಖಾಚಿತ್ರಗಳು ನಿಖರವಾಗಿ ಮಧ್ಯಂತರ ರೇಖಾಚಿತ್ರ ಪೂರಕಗಳನ್ನು ಹೊಂದಿರುವ ಮಧ್ಯಂತರ ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ; ಇವು ವಕ್ರ-ವಿಲೀನಗೊಂಡ ಕ್ರಮಪಲ್ಲಟನೆಗಳ ಕ್ರಮಪಲ್ಲಟನೆ ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ. ವಿಭಜಿತ ನಕ್ಷೆಗಳು ವರ್ಣತಂತು ಸಂಖ್ಯೆ 2 ಅನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಅಲ್ಗಾರಿದಮಿಕ್ ಸಮಸ್ಯೆಗಳು ಒಂದು ವಿಭಜಿತ ಗ್ರಾಫ್ ಆಗಿರಲಿ, ಇದನ್ನು ಒಂದು ಗುಂಪು ಮತ್ತು ಸ್ವತಂತ್ರ ಗುಂಪಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ. ನಂತರ ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಗರಿಷ್ಠ ಗುಂಪು ಸ್ವತಃ, ಅಥವಾ ಒಂದು ಶೃಂಗದ ನೆರೆಹೊರೆಯಾಗಿರುತ್ತದೆ. ಹೀಗಾಗಿ, ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ನಲ್ಲಿ ಗರಿಷ್ಠ ಗುಂಪು ಮತ್ತು ಪೂರಕವಾಗಿ ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಗುಂಪನ್ನು ಗುರುತಿಸುವುದು ಸುಲಭ. ಯಾವುದೇ ವಿಭಜಿತ ನಕ್ಷೆಯಲ್ಲಿ, ಈ ಕೆಳಗಿನ ಮೂರು ಸಾಧ್ಯತೆಗಳಲ್ಲಿ ಒಂದು ನಿಜವಾಗಿರಬೇಕುಃ ಸಂಪೂರ್ಣವಾದ ಒಂದು ಶೃಂಗವು ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಇದು ಗರಿಷ್ಠ ಗುಂಪು ಮತ್ತು ಇದು ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಗುಂಪಾಗಿದೆ. ಸ್ವತಂತ್ರವಾಗಿರುವಂತಹ ಒಂದು ಶೃಂಗವು ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಇದು ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಗುಂಪಾಗಿದೆ ಮತ್ತು ಇದು ಗರಿಷ್ಠ ಗುಂಪಾಗಿದೆ. ಇದು ಗರಿಷ್ಠ ಗುಂಪು ಮತ್ತು ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಗುಂಪಾಗಿದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಒಂದು ಗುಂಪು ಮತ್ತು ಸ್ವತಂತ್ರ ಗುಂಪಿಗೆ ವಿಶಿಷ್ಟವಾದ ವಿಭಾಗವನ್ನು ಹೊಂದಿದೆ, ಇದು ಗರಿಷ್ಠ ಗುಂಪು, ಮತ್ತು ಇದು ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಗುಂಪಾಗಿದೆ. ಗ್ರಾಫ್ ಬಣ್ಣವನ್ನು ಒಳಗೊಂಡಂತೆ ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಗ್ರಾಫ್ ಕುಟುಂಬಗಳಲ್ಲಿ ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿರುವ ಕೆಲವು ಇತರ ಆಪ್ಟಿಮೈಸೇಶನ್ ಸಮಸ್ಯೆಗಳು ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಇದೇ ರೀತಿ ನೇರವಾಗಿರುತ್ತವೆ. ಬಲವಾದ ಸ್ವರಮೇಳದ ರೇಖಾಚಿತ್ರಗಳಾಗಿರುವ ವಿಭಜಿತ ರೇಖಾಚಿತ್ರಗಳಿಗೂ ಸಹ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿ ಉಳಿದಿದೆ. ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ಗಳಿಗೆ ಕನಿಷ್ಠ ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿ ಉಳಿದಿದೆ ಎಂಬುದು ಎಲ್ಲರಿಗೂ ತಿಳಿದಿದೆ. ವಿಭಜಿತ ರೇಖಾಚಿತ್ರಗಳ ಒಂದು ಗಮನಾರ್ಹ ಲಕ್ಷಣವೆಂದರೆ ಅವುಗಳನ್ನು ಅವುಗಳ ಪದವಿ ಅನುಕ್ರಮಗಳಿಂದ ಮಾತ್ರ ಗುರುತಿಸಬಹುದು. ರೇಖಾಚಿತ್ರದ ಡಿಗ್ರಿ ಅನುಕ್ರಮವು ಅದರ ಅತಿದೊಡ್ಡ ಮೌಲ್ಯವಾಗಿರಲಿ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ದೊಡ್ಡ ಡಿಗ್ರಿಗಳನ್ನು ಹೊಂದಿರುವ ಶೃಂಗಗಳು ಗರಿಷ್ಠ ಗುಂಪನ್ನು ರೂಪಿಸುತ್ತವೆ ಮತ್ತು ಉಳಿದ ಶೃಂಗಗಳು ಸ್ವತಂತ್ರ ಗುಂಪನ್ನು ರೂಪಿಸುತ್ತವೆ. ಅನಿಯಂತ್ರಿತ ರೇಖಾಚಿತ್ರದ ವಿಭಜನೆಯು ಈ ಅಸಮಾನತೆಯು ಎಷ್ಟರ ಮಟ್ಟಿಗೆ ನಿಜವಾಗುವುದಿಲ್ಲ ಎಂಬುದನ್ನು ಅಳೆಯುತ್ತದೆ. ಒಂದು ರೇಖಾಚಿತ್ರವು ವಿಭಜಿತ ರೇಖಾಚಿತ್ರವಲ್ಲದಿದ್ದರೆ, ಅದನ್ನು ವಿಭಜಿತ ರೇಖಾಚಿತ್ರವನ್ನಾಗಿ ಮಾಡುವ ಅಂಚಿನ ಅಳವಡಿಕೆ ಮತ್ತು ತೆಗೆದುಹಾಕುವಿಕೆಯ ಚಿಕ್ಕ ಅನುಕ್ರಮವನ್ನು ದೊಡ್ಡ ಡಿಗ್ರಿಗಳೊಂದಿಗೆ ಶೃಂಗಗಳ ನಡುವೆ ಕಾಣೆಯಾದ ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಮತ್ತು ಉಳಿದ ಶೃಂಗಗಳ ಜೋಡಿಗಳ ನಡುವಿನ ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ತೆಗೆದುಹಾಕುವ ಮೂಲಕ ಪಡೆಯಬಹುದು; ವಿಭಜನೆಯು ಈ ಅನುಕ್ರಮದಲ್ಲಿ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸುತ್ತದೆ. ವಿಭಜಿತ ಗ್ರಾಫ್ಗಳನ್ನು ಎಣಿಸುವುದರಿಂದ, ಎನ್-ಜೊತೆಗಿನ ಎನ್-ವೆರ್ಟೆಕ್ಸ್ ವಿಭಜಿತ ಗ್ರಾಫ್ಗಳು ಕೆಲವು ಸ್ಪರ್ನರ್ ಕುಟುಂಬಗಳೊಂದಿಗೆ ಒಂದರಿಂದ ಇನ್ನೊಂದಕ್ಕೆ ಹೊಂದಿಕೆಯಾಗುತ್ತವೆ ಎಂದು ತೋರಿಸಿದೆ. ಈ ಸತ್ಯವನ್ನು ಬಳಸಿಕೊಂಡು, ಅವರು n ಶೃಂಗಗಳ ಮೇಲೆ ನಾನಿಸೋಮಾರ್ಫಿಕ್ ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ಗಳ ಸಂಖ್ಯೆಗೆ ಸೂತ್ರವನ್ನು ನಿರ್ಧರಿಸಿದರು. n = 1 ರಿಂದ ಪ್ರಾರಂಭವಾಗುವ n ನ ಸಣ್ಣ ಮೌಲ್ಯಗಳಿಗೆ, ಈ ಸಂಖ್ಯೆಗಳು 1,2,4,9,21,56,164,557,2223,10766,64956,501696,. ಈ ಎಣಿಕೆಯ ಫಲಿತಾಂಶವು ಈ ಹಿಂದೆಯೂ ಸಾಬೀತಾಗಿದೆ. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು. .. .. .. .. .. .. .. .. .. .. .. .. .. .. "ಗುರುತು ಹಾಕದ ಸಂಯೋಜಿತ ವಸ್ತುಗಳನ್ನು ಎಣಿಸುವ ಮತ್ತೊಂದು ವಿಧಾನ" ಎಂದು ಅನುವಾದಿಸಲಾಗಿದೆ (1990), ಯುಎಸ್ಎಸ್ಆರ್ನ ಅಕಾಡೆಮಿ ಆಫ್ ಸೈನ್ಸಸ್ನ ಗಣಿತ ಟಿಪ್ಪಣಿಗಳು 48 (6): 1239-1245,. .. .. ಸ್ಪ್ಲಿಟ್ ಗ್ರಾಫ್ಗಳ ಕುರಿತಾದ ಒಂದು ಅಧ್ಯಾಯವು ಮಾರ್ಟಿನ್ ಚಾರ್ಲ್ಸ್ ಗೋಲುಂಬಿಕ್ ಅವರ "ಅಲ್ಗಾರಿದಮಿಕ್ ಗ್ರಾಫ್ ಥಿಯರಿ ಅಂಡ್ ಪರ್ಫೆಕ್ಟ್ ಗ್ರಾಫ್ಸ್" ಎಂಬ ಪುಸ್ತಕದಲ್ಲಿ ಕಂಡುಬರುತ್ತದೆ. ಗ್ರಾಫ್ ಕುಟುಂಬಗಳು ಗ್ರಾಫ್ಗಳ ಇಂಟರ್ಸೆಕ್ಷನ್ ವರ್ಗಗಳು ಪರಿಪೂರ್ಣ ಗ್ರಾಫ್ಗಳು