Degree (graph theory)
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಗ್ರಾಫ್ನ ಶೃಂಗದ ಡಿಗ್ರಿ (ಅಥವಾ ವೇಲೆನ್ಸಿ) ಎಂದರೆ ಶೃಂಗಕ್ಕೆ ಸಂಬಂಧಿಸಿದ ಅಂಚುಗಳ ಸಂಖ್ಯೆ; ಬಹು ಲಿಪಿಯಲ್ಲಿ, ಒಂದು ಲೂಪ್ ಶೃಂಗದ ಡಿಗ್ರಿಗೆ 2 ಅನ್ನು ಕೊಡುಗೆ ನೀಡುತ್ತದೆ, ಅಂಚಿನ ಎರಡು ತುದಿಗಳಿಗೆ. ಶೃಂಗದ ಮಟ್ಟವನ್ನು ಅಥವಾ ಎಂದು ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಒಂದು ರೇಖಾಚಿತ್ರದ ಗರಿಷ್ಠ ಡಿಗ್ರಿ, ಮತ್ತು ಅದರ ಮೂಲಕ ಸೂಚಿಸಲಾದ ರೇಖಾಚಿತ್ರದ ಕನಿಷ್ಠ ಡಿಗ್ರಿ, ಅದರ ಶೃಂಗಗಳ ಡಿಗ್ರಿಗಳ ಗರಿಷ್ಠ ಮತ್ತು ಕನಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಬಲಭಾಗದಲ್ಲಿ ತೋರಿಸಿರುವ ಬಹು ಲಿಪಿಯಲ್ಲಿ, ಗರಿಷ್ಠ ಪದವಿ 5 ಮತ್ತು ಕನಿಷ್ಠ ಪದವಿ 0 ಆಗಿದೆ. ನಿಯಮಿತ ರೇಖಾಚಿತ್ರದಲ್ಲಿ, ಪ್ರತಿಯೊಂದು ಶೃಂಗವು ಒಂದೇ ಮಟ್ಟವನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ನಾವು ರೇಖಾಚಿತ್ರದ ಮಟ್ಟವನ್ನು ಕುರಿತು ಮಾತನಾಡಬಹುದು. ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ (ಸೂಚಿಸಲಾದ, ಗ್ರಾಫ್ನಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆ) ಒಂದು ವಿಶೇಷ ರೀತಿಯ ನಿಯಮಿತ ಗ್ರಾಫ್ ಆಗಿದ್ದು, ಅಲ್ಲಿ ಎಲ್ಲಾ ಶೃಂಗಗಳು ಸಾಧ್ಯವಾದಷ್ಟು ಗರಿಷ್ಠ ಮಟ್ಟವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಸಹಿ ಮಾಡಲಾದ ರೇಖಾಚಿತ್ರದಲ್ಲಿ, ಶೃಂಗಕ್ಕೆ ಜೋಡಿಸಲಾದ ಧನಾತ್ಮಕ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಧನಾತ್ಮಕ ಡಿಗ್ರಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಜೋಡಿಸಲಾದ ಋಣಾತ್ಮಕ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಋಣಾತ್ಮಕ ಡಿಗ್ರಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಹ್ಯಾಂಡ್ಶೇಕಿಂಗ್ ಲೆಮ್ಮಾ ಡಿಗ್ರಿ ಮೊತ್ತದ ಸೂತ್ರವು, ಗ್ರಾಫ್ ಅನ್ನು ನೀಡಿದರೆ, ಎಂದು ಹೇಳುತ್ತದೆ. ಸೂತ್ರವು ಯಾವುದೇ ನಿರ್ದೇಶಿಸದ ರೇಖಾಚಿತ್ರದಲ್ಲಿ, ಬೆಸ ಡಿಗ್ರಿ ಹೊಂದಿರುವ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯು ಸಮವಾಗಿರುತ್ತದೆ ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ಈ ಹೇಳಿಕೆಯನ್ನು (ಹಾಗೆಯೇ ಡಿಗ್ರಿ ಮೊತ್ತದ ಸೂತ್ರ) ಹ್ಯಾಂಡ್ಶೇಕಿಂಗ್ ಲೆಮ್ಮಾ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಎರಡನೆಯ ಹೆಸರು ಜನಪ್ರಿಯ ಗಣಿತದ ಸಮಸ್ಯೆಯಿಂದ ಬಂದಿದೆ, ಇದು ಯಾವುದೇ ಗುಂಪಿನ ಜನರಲ್ಲಿ, ಗುಂಪಿನ ಬೆಸ ಸಂಖ್ಯೆಯ ಇತರ ಜನರೊಂದಿಗೆ ಕೈಕುಲುಕಿದ ಜನರ ಸಂಖ್ಯೆ ಸಮವಾಗಿದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸುತ್ತದೆ. ಡಿಗ್ರಿ ಅನುಕ್ರಮವು ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ನ ಡಿಗ್ರಿ ಅನುಕ್ರಮವು ಅದರ ಶೃಂಗದ ಡಿಗ್ರಿಗಳ ಹೆಚ್ಚಾಗದ ಅನುಕ್ರಮವಾಗಿದೆ; ಮೇಲಿನ ಗ್ರಾಫ್ಗೆ ಇದು (5,3,3,2,2,1,0). ಡಿಗ್ರಿ ಅನುಕ್ರಮವು ಗ್ರಾಫ್ ಅಸ್ಥಿರವಾಗಿದೆ, ಆದ್ದರಿಂದ ಐಸೊಮಾರ್ಫಿಕ್ ಗ್ರಾಫ್ಗಳು ಒಂದೇ ಡಿಗ್ರಿ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಆದಾಗ್ಯೂ, ಡಿಗ್ರಿ ಅನುಕ್ರಮವು, ಸಾಮಾನ್ಯವಾಗಿ, ಗ್ರಾಫ್ ಅನ್ನು ಅನನ್ಯವಾಗಿ ಗುರುತಿಸುವುದಿಲ್ಲ; ಕೆಲವು ಸಂದರ್ಭಗಳಲ್ಲಿ, ಐಸೋಮಾರ್ಫಿಕ್ ಅಲ್ಲದ ಗ್ರಾಫ್ಗಳು ಒಂದೇ ಡಿಗ್ರಿ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಡಿಗ್ರಿ ಸೀಕ್ವೆನ್ಸ್ ಸಮಸ್ಯೆಯು ಕೆಲವು ಅಥವಾ ಎಲ್ಲಾ ಗ್ರಾಫ್ಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯಾಗಿದ್ದು, ಡಿಗ್ರಿ ಸೀಕ್ವೆನ್ಸ್ ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕಗಳ ಹೆಚ್ಚದ ಅನುಕ್ರಮವಾಗಿದೆ. (ಗ್ರಾಫ್ಗೆ ಸೂಕ್ತ ಸಂಖ್ಯೆಯ ಪ್ರತ್ಯೇಕವಾದ ಶೃಂಗಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಅವುಗಳನ್ನು ಕ್ಷುಲ್ಲಕವಾಗಿ ಅರಿತುಕೊಳ್ಳುವುದರಿಂದ ಹಿಂಬಾಲಿಸುವ ಶೂನ್ಯಗಳನ್ನು ನಿರ್ಲಕ್ಷಿಸಬಹುದು.) ಒಂದು ಅನುಕ್ರಮವು ಕೆಲವು ಗ್ರಾಫ್ನ ಡಿಗ್ರಿ ಅನುಕ್ರಮವಾಗಿದೆ, ಅಂದರೆ. ಡಿಗ್ರಿ ಸೀಕ್ವೆನ್ಸ್ ಸಮಸ್ಯೆಯು ಪರಿಹಾರವನ್ನು ಹೊಂದಿರುವ ಇದನ್ನು ಗ್ರಾಫಿಕ್ ಅಥವಾ ಗ್ರಾಫಿಕಲ್ ಸೀಕ್ವೆನ್ಸ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಡಿಗ್ರಿ ಮೊತ್ತದ ಸೂತ್ರದ ಪರಿಣಾಮವಾಗಿ, (3,3,1) ನಂತಹ ಬೆಸ ಮೊತ್ತವನ್ನು ಹೊಂದಿರುವ ಯಾವುದೇ ಅನುಕ್ರಮವನ್ನು ಗ್ರಾಫ್ನ ಡಿಗ್ರಿ ಅನುಕ್ರಮವಾಗಿ ಅರಿತುಕೊಳ್ಳಲು ಸಾಧ್ಯವಿಲ್ಲ. ವಿಲೋಮವು ಸಹ ನಿಜವಾಗಿದೆಃ ಒಂದು ಅನುಕ್ರಮವು ಸಮ ಮೊತ್ತವನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದು ಬಹು ಲಿಪಿಯ ಡಿಗ್ರಿ ಅನುಕ್ರಮವಾಗಿದೆ. ಅಂತಹ ರೇಖಾಚಿತ್ರದ ರಚನೆಯು ಸರಳವಾಗಿದೆಃ ಶೃಂಗಗಳನ್ನು ಬೆಸ ಡಿಗ್ರಿಗಳೊಂದಿಗೆ ಜೋಡಿಯಾಗಿ ಜೋಡಿಸಿ (ಹೊಂದಾಣಿಕೆಯನ್ನು ರೂಪಿಸುತ್ತದೆ), ಮತ್ತು ಉಳಿದ ಸಮ ಡಿಗ್ರಿ ಎಣಿಕೆಗಳನ್ನು ಸ್ವಯಂ-ಲೂಪ್ಗಳಿಂದ ಭರ್ತಿ ಮಾಡಿ. ಒಂದು ನಿರ್ದಿಷ್ಟ ಪದವಿ ಅನುಕ್ರಮವನ್ನು ಸರಳ ರೇಖಾಚಿತ್ರದಿಂದ ಅರಿತುಕೊಳ್ಳಬಹುದೇ ಎಂಬ ಪ್ರಶ್ನೆಯು ಹೆಚ್ಚು ಸವಾಲಿನದ್ದಾಗಿದೆ. ಈ ಸಮಸ್ಯೆಯನ್ನು ಗ್ರಾಫ್ ಸಾಕ್ಷಾತ್ಕಾರ ಸಮಸ್ಯೆ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಇದನ್ನು ಎರ್ಡೋಸ್-ಗಲ್ಲೈ ಪ್ರಮೇಯ ಅಥವಾ ಹಾವೆಲ್-ಹಾಕಿಮಿ ಕ್ರಮಾವಳಿಗಳಿಂದ ಪರಿಹರಿಸಬಹುದು. ನಿರ್ದಿಷ್ಟ ಪದವಿ ಅನುಕ್ರಮದೊಂದಿಗೆ ಗ್ರಾಫ್ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವ ಅಥವಾ ಅಂದಾಜು ಮಾಡುವ ಸಮಸ್ಯೆಯು ಗ್ರಾಫ್ ಎಣಿಕೆಯ ಕ್ಷೇತ್ರದಿಂದ ಒಂದು ಸಮಸ್ಯೆಯಾಗಿದೆ. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ಹೈಪರ್ಗ್ರಾಫ್ನ ಡಿಗ್ರಿ ಅನುಕ್ರಮವು ಅದರ ಶೃಂಗದ ಡಿಗ್ರಿಗಳ ಹೆಚ್ಚಾಗದ ಅನುಕ್ರಮವಾಗಿದೆ. ಒಂದು ಅನುಕ್ರಮವು ಕೆಲವು ಏಕರೂಪದ ಹೈಪರ್ಗ್ರಾಫ್ನ ಡಿಗ್ರಿ ಅನುಕ್ರಮವಾಗಿದ್ದರೆ ಅದು-ಗ್ರಾಫಿಕ್ ಆಗಿರುತ್ತದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ, ಗ್ರಾಫಿಕ್ ಅನುಕ್ರಮವು ಗ್ರಾಫಿಕ್ ಆಗಿದೆ. ಕೊಟ್ಟಿರುವ ಅನುಕ್ರಮವು-ಗ್ರಾಫಿಕ್ ಆಗಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ಎರ್ಡೋಸ್-ಗಲ್ಲೈ ಪ್ರಮೇಯದ ಮೂಲಕ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಮಾಡಬಹುದಾದ ಆದರೆ ಎಲ್ಲರಿಗೂ ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿದೆ. ವಿಶೇಷ ಮೌಲ್ಯಗಳು ಡಿಗ್ರಿ 0 ಹೊಂದಿರುವ ಶೃಂಗವನ್ನು ಪ್ರತ್ಯೇಕವಾದ ಶೃಂಗ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಡಿಗ್ರಿ 1 ಹೊಂದಿರುವ ಶೃಂಗವನ್ನು ಎಲೆಯ ಶೃಂಗ ಅಥವಾ ಅಂತಿಮ ಶೃಂಗ ಅಥವಾ ಪೆಂಡೆಂಟ್ ಶೃಂಗ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಆ ಶೃಂಗದೊಂದಿಗಿನ ಅಂಚಿನ ಘಟನೆಯನ್ನು ಪೆಂಡೆಂಟ್ ಎಡ್ಜ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಬಲಭಾಗದಲ್ಲಿರುವ ರೇಖಾಚಿತ್ರದಲ್ಲಿ, {3,5} ಒಂದು ಪೆಂಡೆಂಟ್ ಎಡ್ಜ್ ಆಗಿದೆ. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಮರಗಳ ಅಧ್ಯಯನದಲ್ಲಿ ಮತ್ತು ವಿಶೇಷವಾಗಿ ದತ್ತಾಂಶ ರಚನೆಗಳಾಗಿ ಮರಗಳ ಅಧ್ಯಯನದಲ್ಲಿ ಈ ಪರಿಭಾಷೆಯು ಸಾಮಾನ್ಯವಾಗಿದೆ. n ಶೃಂಗಗಳ ಮೇಲಿನ ರೇಖಾಚಿತ್ರದಲ್ಲಿ n-1 ಡಿಗ್ರಿ ಹೊಂದಿರುವ ಶೃಂಗವನ್ನು ಪ್ರಾಬಲ್ಯದ ಶೃಂಗ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಜಾಗತಿಕ ಗುಣಲಕ್ಷಣಗಳು ಗ್ರಾಫ್ನ ಪ್ರತಿಯೊಂದು ಶೃಂಗವು ಒಂದೇ ಡಿಗ್ರಿ k ಅನ್ನು ಹೊಂದಿದ್ದರೆ, ಗ್ರಾಫ್ ಅನ್ನು k-ನಿಯಮಿತ ಗ್ರಾಫ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಗ್ರಾಫ್ ಸ್ವತಃ ಡಿಗ್ರಿ k ಅನ್ನು ಹೊಂದಿದೆ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ. ಅಂತೆಯೇ, ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್, ಇದರಲ್ಲಿ ಉಭಯಪಕ್ಷೀಯತೆಯ ಒಂದೇ ಬದಿಯಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಎರಡು ಶೃಂಗಗಳು ಪರಸ್ಪರ ಒಂದೇ ಡಿಗ್ರಿ ಹೊಂದಿರುತ್ತವೆ, ಇದನ್ನು ಬೈರೆಗುಲರ್ ಗ್ರಾಫ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ನಿರ್ದೇಶಿಸದ, ಸಂಪರ್ಕಿತ ರೇಖಾಚಿತ್ರವು ಬೆಸ ಮಟ್ಟದ 0 ಅಥವಾ 2 ಶೃಂಗಗಳನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಯೂಲೆರಿಯನ್ ಮಾರ್ಗವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಇದು ಬೆಸ ಹಂತದ 0 ಶೃಂಗಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಯೂಲೆರಿಯನ್ ಮಾರ್ಗವು ಯೂಲೆರಿಯನ್ ಸರ್ಕ್ಯೂಟ್ ಆಗಿದೆ. ಪ್ರತಿ ಶೃಂಗವು ಗರಿಷ್ಠ 1 ಡಿಗ್ರಿ ಹೊರಭಾಗವನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ನಿರ್ದೇಶಿತ ನಕ್ಷೆಯು ನಿರ್ದೇಶಿತ ಹುಸಿ ಅರಣ್ಯವಾಗಿದೆ. ಕ್ರಿಯಾತ್ಮಕ ರೇಖಾಚಿತ್ರವು ಪ್ರತಿ ಶೃಂಗವು ನಿಖರವಾಗಿ 1 ಡಿಗ್ರಿ ಹೊಂದಿರುವ ಹುಸಿ ಅರಣ್ಯದ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ. ಬ್ರೂಕ್ಸ್ನ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಒಂದು ಗುಂಪು ಅಥವಾ ಬೆಸ ಚಕ್ರವನ್ನು ಹೊರತುಪಡಿಸಿ ಯಾವುದೇ ಗ್ರಾಫ್ ಜಿ ಗರಿಷ್ಠ ವರ್ಣಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ವೈಜಿಂಗ್ನ ಪ್ರಮೇಯದ ಪ್ರಕಾರ ಯಾವುದೇ ಗ್ರಾಫ್ ಗರಿಷ್ಠ ವರ್ಣಸೂಚಿಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಕೆ-ಡಿಜೆನರೇಟ್ ಗ್ರಾಫ್ ಎನ್ನುವುದು ಪ್ರತಿ ಉಪಗ್ರಾಫ್ ಗರಿಷ್ಠ ಕೆ ಡಿಗ್ರಿ ಶೃಂಗವನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ ಆಗಿದೆ. ದ್ವಿ-ಪಕ್ಷೀಯ ಗ್ರಾಫ್ಗಳ ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳಿಗಾಗಿ ಡಿಗ್ರ್ಯಾಫ್ಗಳ ಡಿಗ್ರಿ ವಿತರಣಾ ಡಿಗ್ರಿ ಅನುಕ್ರಮಕ್ಕೆ ಔಟ್ ಡಿಗ್ರಿ ಇಂಡೆಗ್ರೀ ಅನ್ನು ಸಹ ನೋಡಿ. .. .. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ