Induced subgraph
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಗಣಿತ ಕ್ಷೇತ್ರದಲ್ಲಿ, ಗ್ರಾಫ್ನ ಪ್ರೇರಿತ ಉಪಗ್ರಾಫ್ ಮತ್ತೊಂದು ಗ್ರಾಫ್ ಆಗಿದ್ದು, ಇದು ಗ್ರಾಫ್ನ ಶೃಂಗಗಳ ಉಪವಿಭಾಗದಿಂದ ಮತ್ತು ಆ ಉಪವಿಭಾಗದಲ್ಲಿನ ಶೃಂಗಗಳ ಜೋಡಿಗಳನ್ನು ಸಂಪರ್ಕಿಸುವ ಎಲ್ಲಾ ಅಂಚುಗಳಿಂದ (ಮೂಲ ಗ್ರಾಫ್ನಿಂದ) ರೂಪುಗೊಳ್ಳುತ್ತದೆ. ವ್ಯಾಖ್ಯಾನ ಔಪಚಾರಿಕವಾಗಿ, ಯಾವುದೇ ಗ್ರಾಫ್ ಆಗಿರಲಿ, ಮತ್ತು ಅದರ ಶೃಂಗಗಳ ಯಾವುದೇ ಉಪವಿಭಾಗವಾಗಿರಲಿ. ನಂತರ ಇಂಡ್ಯೂಸ್ಡ್ ಸಬ್ಗ್ರಾಫ್ ಎಂದರೆ ಅದರ ಶೃಂಗದ ಸೆಟ್ ಇರುವ ಗ್ರಾಫ್ ಮತ್ತು ಅದರ ಅಂಚಿನ ಸೆಟ್ ಎರಡೂ ಅಂತಿಮ ಬಿಂದುಗಳನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಅಂದರೆ, ಯಾವುದೇ ಎರಡು ಶೃಂಗಗಳಿಗೆ, ಮತ್ತು ಅವು ಪಕ್ಕದಲ್ಲಿದ್ದರೆ ಮಾತ್ರ ಪಕ್ಕದಲ್ಲಿರುತ್ತವೆ. ಅದೇ ವ್ಯಾಖ್ಯಾನವು ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ಗಳು, ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಮಲ್ಟಿಗ್ರಾಫ್ಗಳಿಗೂ ಸಹ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಇಂಡ್ಯೂಸ್ಡ್ ಸಬ್ಗ್ರಾಫ್ ಅನ್ನು ಇಂಡ್ಯೂಸ್ಡ್ ಇನ್, ಅಥವಾ (ಸಂದರ್ಭವು ನಿಸ್ಸಂದಿಗ್ಧವಾಗಿ ಆಯ್ಕೆ ಮಾಡಿದರೆ) ಇಂಡ್ಯೂಸ್ಡ್ ಸಬ್ಗ್ರಾಫ್ ಎಂದೂ ಕರೆಯಬಹುದು. ಉದಾಹರಣೆಗಳು ಪ್ರಮುಖ ರೀತಿಯ ಪ್ರೇರಿತ ಉಪಗ್ರಫ್ಗಳು ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಒಳಗೊಂಡಿವೆ. ಪ್ರೇರೇಪಿತ ಮಾರ್ಗಗಳು ಪ್ರೇರೇಪಿತ ಉಪ ನಕ್ಷೆಗಳಾಗಿದ್ದು ಅವು ಮಾರ್ಗಗಳಾಗಿವೆ. ತೂಕವಿಲ್ಲದ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಯಾವುದೇ ಎರಡು ಶೃಂಗಗಳ ನಡುವಿನ ಚಿಕ್ಕದಾದ ಮಾರ್ಗವು ಯಾವಾಗಲೂ ಪ್ರೇರಿತ ಮಾರ್ಗವಾಗಿರುತ್ತದೆ, ಏಕೆಂದರೆ ಜೋಡಿ ಶೃಂಗಗಳ ನಡುವಿನ ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಅಂಚುಗಳು ಅದನ್ನು ಪ್ರಚೋದಿಸದಿರಲು ಕಾರಣವಾಗಬಹುದು, ಅದು ಚಿಕ್ಕದಾಗಿರುವುದಿಲ್ಲ. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ದೂರ-ಆನುವಂಶಿಕ ರೇಖಾಚಿತ್ರಗಳಲ್ಲಿ, ಪ್ರತಿ ಪ್ರೇರಿತ ಮಾರ್ಗವು ಚಿಕ್ಕದಾಗಿದೆ. ಪ್ರಚೋದಿತ ಚಕ್ರಗಳು ಪ್ರಚೋದಿತ ಉಪಗ್ರಫ್ಗಳಾಗಿದ್ದು ಅವು ಚಕ್ರಗಳಾಗಿವೆ. ಗ್ರಾಫ್ನ ಸುತ್ತಳತೆಯನ್ನು ಅದರ ಚಿಕ್ಕ ಚಕ್ರದ ಉದ್ದದಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗುತ್ತದೆ, ಇದು ಯಾವಾಗಲೂ ಪ್ರೇರಿತ ಚಕ್ರವಾಗಿರುತ್ತದೆ. ಬಲವಾದ ಪರಿಪೂರ್ಣ ಗ್ರಾಫ್ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಪ್ರೇರಿತ ಚಕ್ರಗಳು ಮತ್ತು ಅವುಗಳ ಪೂರಕಗಳು ಪರಿಪೂರ್ಣ ಗ್ರಾಫ್ಗಳ ಗುಣಲಕ್ಷಣಗಳಲ್ಲಿ ನಿರ್ಣಾಯಕ ಪಾತ್ರವನ್ನು ವಹಿಸುತ್ತವೆ. ಕ್ಲಿಕ್ಗಳು ಮತ್ತು ಸ್ವತಂತ್ರ ಸೆಟ್ಗಳು ಅನುಕ್ರಮವಾಗಿ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ಗಳು ಅಥವಾ ಅಂಚುರಹಿತ ಗ್ರಾಫ್ಗಳಾಗಿರುವ ಪ್ರೇರಿತ ಉಪಗ್ರಾಫ್ಗಳಾಗಿವೆ. ಪ್ರಚೋದಿತ ಹೊಂದಾಣಿಕೆಗಳು ಪ್ರಚೋದಿತ ಉಪಗ್ರಫ್ಗಳಾಗಿದ್ದು ಅವು ಹೊಂದಾಣಿಕೆಗಳಾಗಿವೆ. ಶೃಂಗದ ನೆರೆಹೊರೆಯು ಅದರ ಪಕ್ಕದ ಎಲ್ಲಾ ಶೃಂಗಗಳ ಪ್ರೇರಿತ ಉಪ ನಕ್ಷೆಯಾಗಿದೆ. ಇಂಡ್ಯೂಸ್ಡ್ ಸಬ್ಗ್ರಾಫ್ ಐಸೊಮಾರ್ಫಿಸಮ್ ಸಮಸ್ಯೆಯು ಸಬ್ಗ್ರಾಫ್ ಐಸೊಮಾರ್ಫಿಸಮ್ ಸಮಸ್ಯೆಯ ಒಂದು ರೂಪವಾಗಿದೆ, ಇದರಲ್ಲಿ ಒಂದು ಗ್ರಾಫ್ ಅನ್ನು ಇನ್ನೊಂದರ ಇಂಡ್ಯೂಸ್ಡ್ ಸಬ್ಗ್ರಾಫ್ ಎಂದು ಕಂಡುಹಿಡಿಯಬಹುದೇ ಎಂದು ಪರೀಕ್ಷಿಸುವುದು ಗುರಿಯಾಗಿದೆ. ಇದು ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿ ಗುಂಪಿನ ಸಮಸ್ಯೆಯನ್ನು ಒಳಗೊಂಡಿರುವುದರಿಂದ, ಇದು ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಆಗಿದೆ. ಉಲ್ಲೇಖಗಳು ಗ್ರಾಫ್ ಕಾರ್ಯಾಚರಣೆಗಳು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ವಸ್ತುಗಳು