Directed graph
ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ಮತ್ತು ಹೆಚ್ಚು ನಿರ್ದಿಷ್ಟವಾಗಿ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ (ಅಥವಾ ಡಿಗ್ರಾಫ್) ಎನ್ನುವುದು ನಿರ್ದೇಶಿತ ಅಂಚುಗಳಿಂದ ಸಂಪರ್ಕ ಹೊಂದಿದ ಶೃಂಗಗಳ ಗುಂಪಿನಿಂದ ಕೂಡಿದ ಗ್ರಾಫ್ ಆಗಿದೆ, ಇದನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಆರ್ಕ್ಸ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ವ್ಯಾಖ್ಯಾನ ಔಪಚಾರಿಕವಾಗಿ ಹೇಳುವುದಾದರೆ, ನಿರ್ದೇಶಿತ ರೇಖಾಚಿತ್ರವು ಒಂದು ಕ್ರಮಬದ್ಧವಾದ ಜೋಡಿಯಾಗಿದ್ದು, V ಎಂಬುದು ಅದರ ಅಂಶಗಳನ್ನು ಶೃಂಗಗಳು, ನೋಡ್ಗಳು ಅಥವಾ ಬಿಂದುಗಳು ಎಂದು ಕರೆಯಲಾಗುವ ಒಂದು ಸೆಟ್ ಆಗಿದೆ; A ಎಂಬುದು ಆರ್ಕ್ಸ್, ನಿರ್ದೇಶಿತ ಅಂಚುಗಳು (ಕೆಲವೊಮ್ಮೆ ಸರಳವಾಗಿ ಎ ಬದಲಿಗೆ ಇ ಎಂಬ ಹೆಸರಿನ ಅನುಗುಣವಾದ ಗುಂಪಿನೊಂದಿಗೆ ಅಂಚುಗಳು), ಬಾಣಗಳು ಅಥವಾ ನಿರ್ದೇಶಿತ ರೇಖೆಗಳೆಂದು ಕರೆಯಲಾಗುವ ಕ್ರಮಬದ್ಧ ಜೋಡಿ ಶೃಂಗಗಳ ಒಂದು ಸೆಟ್ ಆಗಿದೆ. ಇದು ಸಾಮಾನ್ಯ ಅಥವಾ ನಿರ್ದೇಶಿಸದ ರೇಖಾಚಿತ್ರಕ್ಕಿಂತ ಭಿನ್ನವಾಗಿದೆ, ಇದರಲ್ಲಿ ಎರಡನೆಯದನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಅಂಚುಗಳು, ಕೊಂಡಿಗಳು ಅಥವಾ ರೇಖೆಗಳು ಎಂದು ಕರೆಯಲಾಗುವ ಕ್ರಮಬದ್ಧವಲ್ಲದ ಜೋಡಿ ಶೃಂಗಗಳ ಪರಿಭಾಷೆಯಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಮೇಲೆ ತಿಳಿಸಲಾದ ವ್ಯಾಖ್ಯಾನವು ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ಗೆ ಒಂದೇ ಮೂಲ ಮತ್ತು ಗುರಿ ನೋಡ್ಗಳೊಂದಿಗೆ ಅನೇಕ ಬಾಣಗಳನ್ನು ಹೊಂದಲು ಅನುಮತಿಸುವುದಿಲ್ಲ, ಆದರೆ ಕೆಲವು ಲೇಖಕರು ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ಗಳಿಗೆ ಅಂತಹ ಅನೇಕ ಆರ್ಕ್ಗಳನ್ನು ಹೊಂದಲು ಅನುವು ಮಾಡಿಕೊಡುವ ವಿಶಾಲವಾದ ವ್ಯಾಖ್ಯಾನವನ್ನು ಪರಿಗಣಿಸುತ್ತಾರೆ (ಅವುಗಳೆಂದರೆ, ಅವು ಆರ್ಕ್ ಸೆಟ್ ಅನ್ನು ಮಲ್ಟಿಸೆಟ್ ಆಗಿರಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ). ಕೆಲವೊಮ್ಮೆ ಈ ಘಟಕಗಳನ್ನು ನಿರ್ದೇಶಿತ ಬಹು ಶಾಸನಗಳು (ಅಥವಾ ಬಹು ಶಾಸನಗಳು) ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಮತ್ತೊಂದೆಡೆ, ಮೇಲೆ ತಿಳಿಸಲಾದ ವ್ಯಾಖ್ಯಾನವು ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗೆ ಲೂಪ್ಗಳನ್ನು ಹೊಂದಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ (ಅಂದರೆ, ನೋಡ್ಗಳನ್ನು ನೇರವಾಗಿ ತಮ್ಮೊಂದಿಗೆ ಸಂಪರ್ಕಿಸುವ ಆರ್ಕ್ಗಳು), ಆದರೆ ಕೆಲವು ಲೇಖಕರು ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳಿಗೆ ಲೂಪ್ಗಳನ್ನು ಹೊಂದಲು ಅನುಮತಿಸದ ಕಿರಿದಾದ ವ್ಯಾಖ್ಯಾನವನ್ನು ಪರಿಗಣಿಸುತ್ತಾರೆ. ಲೂಪ್ಗಳಿಲ್ಲದ ನಿರ್ದೇಶನದ ಗ್ರಾಫ್ಗಳನ್ನು ಸರಳ ನಿರ್ದೇಶನದ ಗ್ರಾಫ್ಗಳು ಎಂದು ಕರೆಯಬಹುದು, ಆದರೆ ಲೂಪ್ಗಳೊಂದಿಗಿನ ನಿರ್ದೇಶನದ ಗ್ರಾಫ್ಗಳನ್ನು ಲೂಪ್-ಡಿಗ್ರಾಫ್ಗಳು ಎಂದು ಕರೆಯಬಹುದು (ನಿರ್ದೇಶನದ ಗ್ರಾಫ್ನ ವಿಭಾಗ ಪ್ರಕಾರಗಳನ್ನು ನೋಡಿ). ನಿರ್ದೇಶಿತ ರೇಖಾಚಿತ್ರಗಳ ವಿಧಗಳು ಉಪವರ್ಗಗಳು ಸಮಮಿತೀಯ ನಿರ್ದೇಶಿತ ರೇಖಾಚಿತ್ರಗಳು ನಿರ್ದೇಶಿತ ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ, ಅಲ್ಲಿ ಎಲ್ಲಾ ಅಂಚುಗಳು ಎರಡು ಬಾರಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತವೆ, ಪ್ರತಿ ದಿಕ್ಕಿನಲ್ಲಿ ಒಂದು (ಅಂದರೆ, ಡಿಗ್ರ್ಯಾಫ್ಗೆ ಸೇರಿದ ಪ್ರತಿ ಬಾಣಕ್ಕೆ, ಅನುಗುಣವಾದ ವಿಲೋಮ ಬಾಣವು ಸಹ ಅದಕ್ಕೆ ಸೇರಿದೆ). (ಅಂತಹ ಅಂಚನ್ನು ಕೆಲವೊಮ್ಮೆ "ಬೈಡೈರೆಕ್ಟೆಡ್" ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಅಂತಹ ಗ್ರಾಫ್ಗಳನ್ನು ಕೆಲವೊಮ್ಮೆ "ಬೈಡೈರೆಕ್ಟೆಡ್" ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಆದರೆ ಇದು ಬೈಡೈರೆಕ್ಟೆಡ್ ಗ್ರಾಫ್ಗಳ ಅರ್ಥದೊಂದಿಗೆ ಸಂಘರ್ಷಗೊಳ್ಳುತ್ತದೆ.) ಸರಳ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳು ಯಾವುದೇ ಲೂಪ್ಗಳನ್ನು ಹೊಂದಿರದ (ನೇರವಾಗಿ ಶೃಂಗಗಳನ್ನು ತಮ್ಮೊಂದಿಗೆ ಸಂಪರ್ಕಿಸುವ ಬಾಣಗಳು) ಮತ್ತು ಒಂದೇ ಮೂಲ ಮತ್ತು ಗುರಿ ನೋಡ್ಗಳೊಂದಿಗೆ ಬಹು ಬಾಣಗಳಿಲ್ಲದ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳಾಗಿವೆ. ಈಗಾಗಲೇ ಪರಿಚಯಿಸಿದಂತೆ, ಅನೇಕ ಬಾಣಗಳ ಸಂದರ್ಭದಲ್ಲಿ ಅಸ್ತಿತ್ವವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ನಿರ್ದೇಶಿತ ಬಹು ಶಾಸನ ಎಂದು ಸಂಬೋಧಿಸಲಾಗುತ್ತದೆ. ಕೆಲವು ಲೇಖಕರು ಲೂಪ್ಗಳನ್ನು ಹೊಂದಿರುವ ಡಿಗ್ರ್ಯಾಫ್ಗಳನ್ನು ಲೂಪ್-ಡಿಗ್ರ್ಯಾಫ್ಗಳೆಂದು ವಿವರಿಸುತ್ತಾರೆ. ಸಂಪೂರ್ಣ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳು ಸರಳ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳಾಗಿದ್ದು, ಅಲ್ಲಿ ಪ್ರತಿ ಜೋಡಿ ಶೃಂಗಗಳನ್ನು ನಿರ್ದೇಶಿತ ಚಾಪಗಳ ಸಮ್ಮಿತೀಯ ಜೋಡಿಯು ಸೇರಿಸುತ್ತದೆ (ಇದು ದಿಕ್ಕಿಲ್ಲದ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಮತ್ತು ಅಂಚುಗಳನ್ನು ಜೋಡಿ ವಿಲೋಮ ಚಾಪಗಳಿಂದ ಬದಲಾಯಿಸಲಾಗುತ್ತದೆ). ಇದು ಸಂಪೂರ್ಣ ಡಿಗ್ರ್ಯಾಫ್ ಸಮ್ಮಿತೀಯವಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಅರೆ-ಪೂರ್ಣಗೊಂಡ ಬಹುಪಕ್ಷೀಯ ಡಿಗ್ರ್ಯಾಫ್ಗಳು ಸರಳವಾದ ಡಿಗ್ರ್ಯಾಫ್ಗಳಾಗಿದ್ದು, ಇದರಲ್ಲಿ ಶೃಂಗದ ಸೆಟ್ ಅನ್ನು ಸೆಟ್ಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ, ಅಂದರೆ ವಿವಿಧ ಸೆಟ್ಗಳಲ್ಲಿನ x ಮತ್ತು y ಶೃಂಗಗಳ ಪ್ರತಿ ಜೋಡಿಗೆ, x ಮತ್ತು y ನಡುವೆ ಚಾಪವಿದೆ. x ಮತ್ತು y ನಡುವೆ ಒಂದು ಚಾಪವಿರಬಹುದು ಅಥವಾ ವಿರುದ್ಧ ದಿಕ್ಕಿನಲ್ಲಿ ಎರಡು ಚಾಪಗಳಿರಬಹುದು. ಅರ್ಧ-ಪೂರ್ಣಗೊಂಡ ಡಿಗ್ರ್ಯಾಫ್ಗಳು ಸರಳ ಡಿಗ್ರ್ಯಾಫ್ಗಳಾಗಿದ್ದು, ಅಲ್ಲಿ ಪ್ರತಿ ಜೋಡಿ ಶೃಂಗಗಳ ನಡುವೆ ಚಾಪವಿರುತ್ತದೆ. ಪ್ರತಿ ಅರ್ಧ-ಪೂರ್ಣಗೊಂಡ ಡಿಗ್ರ್ಯಾಫ್ ಒಂದು ಕ್ಷುಲ್ಲಕ ರೀತಿಯಲ್ಲಿ ಅರ್ಧ-ಪೂರ್ಣವಾದ ಬಹುಪಕ್ಷೀಯ ಡಿಗ್ರ್ಯಾಫ್ ಆಗಿದ್ದು, ಪ್ರತಿ ಶೃಂಗವು ವಿಭಜನೆಯ ಗುಂಪನ್ನು ರೂಪಿಸುತ್ತದೆ. ಅರೆ-ಪರಿವರ್ತನಶೀಲ ಡಿಗ್ರ್ಯಾಫ್ಗಳು ಸರಳ ಡಿಗ್ರ್ಯಾಫ್ಗಳಾಗಿದ್ದು, ಅಲ್ಲಿ x ನಿಂದ y ಮತ್ತು y ನಿಂದ z ವರೆಗಿನ ಚಾಪಗಳನ್ನು ಹೊಂದಿರುವ ವಿಭಿನ್ನ ಶೃಂಗಗಳ ಪ್ರತಿ ಮೂರು x, y, z ಗೆ, x ಮತ್ತು z ನಡುವೆ ಒಂದು ಚಾಪವಿರುತ್ತದೆ. x ಮತ್ತು z ನಡುವೆ ಕೇವಲ ಒಂದು ಚಾಪವಿರಬಹುದು ಅಥವಾ ವಿರುದ್ಧ ದಿಕ್ಕುಗಳಲ್ಲಿ ಎರಡು ಚಾಪಗಳಿರಬಹುದು. ಅರೆ-ಪೂರ್ಣ ಡಿಗ್ರ್ಯಾಫ್ ಒಂದು ಅರೆ-ಪರಿವರ್ತಕ ಡಿಗ್ರ್ಯಾಫ್ ಆಗಿದೆ. ಕೆ-ಕ್ವಾಸಿ-ಟ್ರಾನ್ಸಿಟಿವ್ ಡಿಗ್ರ್ಯಾಫ್ಗಳು ಎಂದು ಕರೆಯಲಾಗುವ ಅರೆ-ಟ್ರಾನ್ಸಿಟಿವ್ ಡಿಗ್ರ್ಯಾಫ್ಗಳ ವಿಸ್ತರಣೆಗಳಿವೆ. ಓರಿಯೆಂಟೆಡ್ ಗ್ರಾಫ್ಗಳು ನಿರ್ದೇಶನದ ಅಂಚುಗಳ ವಿರುದ್ಧ ಜೋಡಿಗಳನ್ನು ಹೊಂದಿರದ ನಿರ್ದೇಶನದ ಗ್ರಾಫ್ಗಳಾಗಿವೆ (ಅಂದರೆ. ಗರಿಷ್ಠ ಒಂದು ಮತ್ತು ಗ್ರಾಫ್ನ ಬಾಣಗಳಾಗಿರಬಹುದು). ನಿರ್ದೇಶನದ ರೇಖಾಚಿತ್ರವು ಯಾವುದೇ 2-ಚಕ್ರವನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ ಮಾತ್ರ ಅದು ಆಧಾರಿತ ರೇಖಾಚಿತ್ರವಾಗಿದೆ ಎಂದು ಅದು ಅನುಸರಿಸುತ್ತದೆ. (ಇದು "ಓರಿಯೆಂಟೆಡ್ ಗ್ರಾಫ್" ನ ಏಕೈಕ ಅರ್ಥವಲ್ಲ; ಓರಿಯೆಂಟೇಶನ್ (ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ) ನೋಡಿ. ಪಂದ್ಯಾವಳಿಗಳು ನಿರ್ದೇಶನವಿಲ್ಲದ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಪ್ರತಿ ಅಂಚಿಗೆ ಒಂದು ದಿಕ್ಕನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ ಪಡೆದ ಆಧಾರಿತ ಗ್ರಾಫ್ಗಳಾಗಿವೆ. ಪಂದ್ಯಾವಳಿಯು ಅರ್ಧ-ಪೂರ್ಣವಾದ ಡಿಗ್ರ್ಯಾಫ್ ಆಗಿದೆ. ನಿರ್ದೇಶಿತ ರೇಖಾಚಿತ್ರವು ಯಾವುದೇ ನಿರ್ದೇಶಿತ ಚಕ್ರಗಳನ್ನು ಹೊಂದಿಲ್ಲದಿದ್ದರೆ ಅದು ಅಸೈಕ್ಲಿಕ್ ಆಗಿರುತ್ತದೆ. ಅಂತಹ ಡಿಗ್ರ್ಯಾಫ್ಗೆ ಸಾಮಾನ್ಯ ಹೆಸರು ಡೈರೆಕ್ಟ್ ಅಸೈಕ್ಲಿಕ್ ಗ್ರಾಫ್ (ಡಿಎಜಿ) ಆಗಿದೆ. ಮಲ್ಟಿಟ್ರೀಗಳು ಡಿಎಜಿಗಳಾಗಿವೆ, ಇದರಲ್ಲಿ ಒಂದೇ ಆರಂಭಿಕ ಶೃಂಗದಿಂದ ಒಂದೇ ಅಂತ್ಯದ ಶೃಂಗಕ್ಕೆ ಎರಡು ವಿಭಿನ್ನ ನಿರ್ದೇಶಿತ ಮಾರ್ಗಗಳಿಲ್ಲ. ಓರಿಯೆಂಟೆಡ್ ಮರಗಳು ಅಥವಾ ಪಾಲಿ ಟ್ರೀಗಳು ಮರಗಳ ಅಂಚುಗಳನ್ನು ಓರಿಯೆಂಟೆಡ್ ಮಾಡುವ ಮೂಲಕ ರೂಪುಗೊಂಡ ಡಿಎಜಿಗಳಾಗಿವೆ (ಸಂಪರ್ಕಿತ, ಅಸೈಕ್ಲಿಕ್ ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ಗಳು). ಬೇರೂರಿರುವ ಮರಗಳು ಓರಿಯೆಂಟೆಡ್ ಮರಗಳಾಗಿದ್ದು, ಇದರಲ್ಲಿ ಕೆಳಗಿರುವ ದಿಕ್ಕಿಲ್ಲದ ಮರದ ಎಲ್ಲಾ ಅಂಚುಗಳು ಮೂಲದಿಂದ ದೂರ ಅಥವಾ ಕಡೆಗೆ ನಿರ್ದೇಶಿಸಲ್ಪಡುತ್ತವೆ (ಅವುಗಳನ್ನು ಅನುಕ್ರಮವಾಗಿ, ಆರ್ಬೋರೆಸೆನ್ಸ್ಗಳು ಅಥವಾ ಔಟ್-ಟ್ರೀಸ್ ಮತ್ತು ಇನ್-ಟ್ರೀಸ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಪೂರಕ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿರುವ ಡಿಗ್ರ್ಯಾಫ್ಗಳು ತೂಕದ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳು (ನಿರ್ದೇಶಿತ ಜಾಲಗಳು ಎಂದೂ ಕರೆಯಲ್ಪಡುತ್ತವೆ) ಅವುಗಳ ಬಾಣಗಳಿಗೆ ನಿಗದಿಪಡಿಸಿದ ತೂಕಗಳೊಂದಿಗೆ (ಸರಳ) ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳಾಗಿವೆ, ತೂಕದ ಗ್ರಾಫ್ಗಳಂತೆಯೇ (ಇವುಗಳನ್ನು ನಿರ್ದೇಶಿಸದ ಜಾಲಗಳು ಅಥವಾ ತೂಕದ ಜಾಲಗಳು ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ). ಹರಿವಿನ ಜಾಲಗಳು ತೂಕದ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳಾಗಿದ್ದು, ಅಲ್ಲಿ ಎರಡು ನೋಡ್ಗಳನ್ನು ಪ್ರತ್ಯೇಕಿಸಲಾಗಿದೆ, ಒಂದು ಮೂಲ ಮತ್ತು ಒಂದು ಸಿಂಕ್. ರೂಟೆಡ್ ಡೈರೆಕ್ಟೆಡ್ ಗ್ರಾಫ್ಗಳು (ಫ್ಲೋ ಗ್ರಾಫ್ಗಳು ಎಂದೂ ಕರೆಯಲ್ಪಡುತ್ತವೆ) ಡಿಗ್ರ್ಯಾಫ್ಗಳಾಗಿವೆ, ಇದರಲ್ಲಿ ಶೃಂಗವನ್ನು ಮೂಲವೆಂದು ಗುರುತಿಸಲಾಗಿದೆ. ನಿಯಂತ್ರಣ-ಹರಿವಿನ ರೇಖಾಚಿತ್ರಗಳು ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ಅದರ ಕಾರ್ಯಗತಗೊಳಿಸುವಿಕೆಯ ಸಮಯದಲ್ಲಿ ಪ್ರೋಗ್ರಾಂ ಮೂಲಕ ಹಾದುಹೋಗಬಹುದಾದ ಮಾರ್ಗಗಳ ಪ್ರಾತಿನಿಧ್ಯವಾಗಿ ಬಳಸಲಾಗುವ ಬೇರೂರಿರುವ ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ. ಸಿಗ್ನಲ್-ಫ್ಲೋ ಗ್ರಾಫ್ಗಳು ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳಾಗಿವೆ, ಇದರಲ್ಲಿ ನೋಡ್ಗಳು ಸಿಸ್ಟಮ್ ಅಸ್ಥಿರಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ ಮತ್ತು ಶಾಖೆಗಳು (ಅಂಚುಗಳು, ಕಮಾನುಗಳು ಅಥವಾ ಬಾಣಗಳು) ಜೋಡಿ ನೋಡ್ಗಳ ನಡುವಿನ ಕ್ರಿಯಾತ್ಮಕ ಸಂಪರ್ಕಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ. ಹರಿವಿನ ರೇಖಾಚಿತ್ರಗಳು ರೇಖೀಯ ಬೀಜಗಣಿತದ ಅಥವಾ ಭೇದಾತ್ಮಕ ಸಮೀಕರಣಗಳ ಗುಂಪಿಗೆ ಸಂಬಂಧಿಸಿದ ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ. ರಾಜ್ಯದ ರೇಖಾಚಿತ್ರಗಳು ಸೀಮಿತ ರಾಜ್ಯದ ಯಂತ್ರಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಬಹು ಶಾಸನಗಳನ್ನು ನಿರ್ದೇಶಿಸುತ್ತವೆ. ಸಂವಹನ ರೇಖಾಚಿತ್ರಗಳು ವರ್ಗ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಬಳಸಲಾಗುವ ರೇಖಾಚಿತ್ರಗಳಾಗಿವೆ, ಅಲ್ಲಿ ಶೃಂಗಗಳು (ಗಣಿತದ) ವಸ್ತುಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ ಮತ್ತು ಬಾಣಗಳು ಮಾರ್ಫಿಸಮ್ಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ, ಒಂದೇ ಆರಂಭ ಮತ್ತು ಅಂತಿಮ ಬಿಂದುಗಳನ್ನು ಹೊಂದಿರುವ ಎಲ್ಲಾ ನಿರ್ದೇಶಿತ ಮಾರ್ಗಗಳು ಸಂಯೋಜನೆಯಿಂದ ಒಂದೇ ಫಲಿತಾಂಶಕ್ಕೆ ಕಾರಣವಾಗುತ್ತವೆ. ಲೈ ಗುಂಪುಗಳ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಕ್ವಿವರ್ ಕ್ಯೂ ಎಂಬುದು ಡೊಮೇನ್ ಆಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ಒಂದು ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಆಗಿದೆ, ಮತ್ತು ಹೀಗಾಗಿ ಒಂದು ಫಂಕ್ಟರ್ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಪ್ರಾತಿನಿಧ್ಯ ವಿ ಆಕಾರವನ್ನು ನಿರೂಪಿಸುತ್ತದೆ, ನಿರ್ದಿಷ್ಟವಾಗಿ ಫಂಕ್ಟರ್ ವರ್ಗದ ಫಿನ್ವಿಕ್ಟಿಕೆಎಫ್ (ಕ್ಯೂ) ನ ಒಂದು ವಸ್ತುವಾಗಿದ್ದು, ಅಲ್ಲಿ ಎಫ್ (ಕ್ಯೂ) ಕ್ಯೂ ನಲ್ಲಿನ ಮಾರ್ಗಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಕ್ಯೂ ಮೇಲಿನ ಮುಕ್ತ ವರ್ಗವಾಗಿದೆ ಮತ್ತು ಫಿನ್ವಿಕ್ಟಿಕೆ ಎಂಬುದು ಕೆ ಕ್ಷೇತ್ರದ ಮೇಲೆ ಸೀಮಿತ-ಆಯಾಮದ ವೆಕ್ಟರ್ ಸ್ಥಳಗಳ ವರ್ಗವಾಗಿದೆ. ಕ್ವಿವರ್ನ ಪ್ರಾತಿನಿಧ್ಯಗಳು ಅದರ ಶೃಂಗಗಳನ್ನು ವೆಕ್ಟರ್ ಸ್ಥಳಗಳು ಮತ್ತು ಅದರ ಅಂಚುಗಳೊಂದಿಗೆ (ಮತ್ತು ಆದ್ದರಿಂದ ಮಾರ್ಗಗಳು) ಅವುಗಳ ನಡುವಿನ ರೇಖೀಯ ರೂಪಾಂತರಗಳೊಂದಿಗೆ ಹೊಂದಿಕೊಳ್ಳುತ್ತವೆ ಮತ್ತು ನೈಸರ್ಗಿಕ ರೂಪಾಂತರಗಳ ಮೂಲಕ ರೂಪಾಂತರಗೊಳ್ಳುತ್ತವೆ. ಒಂದು ಚಾಪವನ್ನು x ನಿಂದ y ಗೆ ನಿರ್ದೇಶಿಸಲಾಗಿದೆ ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ; y ಅನ್ನು ತಲೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು x ಅನ್ನು ಚಾಪದ ಬಾಲ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ; y ಅನ್ನು x ನ ನೇರ ಉತ್ತರಾಧಿಕಾರಿ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ ಮತ್ತು x ಅನ್ನು y ನ ನೇರ ಪೂರ್ವವರ್ತಿ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ. ಒಂದು ಮಾರ್ಗವು x ನಿಂದ y ಗೆ ಹೋದರೆ, y ಅನ್ನು x ನ ಉತ್ತರಾಧಿಕಾರಿ ಮತ್ತು x ನಿಂದ ತಲುಪಬಹುದು ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ, ಮತ್ತು x ಅನ್ನು y ನ ಪೂರ್ವವರ್ತಿ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ. ಈ ಚಾಪವನ್ನು ರಿವರ್ಸ್ಡ್ ಆರ್ಕ್ ಆಫ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಲೂಪ್ಗಳೊಂದಿಗಿನ ಮಲ್ಟಿಡಿಗ್ರಾಫ್ನ ಹೊಂದಾಣಿಕೆಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಶೃಂಗಗಳಿಗೆ ಅನುಗುಣವಾದ ಸಾಲುಗಳು ಮತ್ತು ಕಾಲಮ್ಗಳನ್ನು ಹೊಂದಿರುವ ಪೂರ್ಣಾಂಕ-ಮೌಲ್ಯದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದೆ, ಅಲ್ಲಿ ನಾನ್ಡಿಯಾಗೊನಲ್ ನಮೂದು ಐಜ್ ಎಂದರೆ ಶೃಂಗ i ರಿಂದ ಶೃಂಗ j ವರೆಗಿನ ಚಾಪಗಳ ಸಂಖ್ಯೆ, ಮತ್ತು ಕರ್ಣೀಯ ನಮೂದು ಎಐಐ ಎಂದರೆ ಶೃಂಗ i ನಲ್ಲಿರುವ ಲೂಪ್ಗಳ ಸಂಖ್ಯೆ. ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ನ ಸಾಮೀಪ್ಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಒಂದು ತಾರ್ಕಿಕ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಆಗಿದ್ದು, ಸಾಲುಗಳು ಮತ್ತು ಕಾಲಮ್ಗಳ ಕ್ರಮಪಲ್ಲಟನೆಯವರೆಗೆ ಅನನ್ಯವಾಗಿದೆ. ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗೆ ಮತ್ತೊಂದು ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಪ್ರಾತಿನಿಧ್ಯವೆಂದರೆ ಅದರ ಇನ್ಸಿಡೆನ್ಸ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್. ಹೆಚ್ಚಿನ ವ್ಯಾಖ್ಯಾನಗಳಿಗಾಗಿ ನಿರ್ದೇಶನವನ್ನು ನೋಡಿ. ಒಂದು ಶೃಂಗಕ್ಕೆ, ಶೃಂಗದ ಪಕ್ಕದಲ್ಲಿರುವ ತಲೆಯ ತುದಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಶೃಂಗದ ಇಂಡೆಗ್ರಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಶೃಂಗದ ಪಕ್ಕದಲ್ಲಿರುವ ಬಾಲದ ತುದಿಗಳ ಸಂಖ್ಯೆಯು ಅದರ ಹೊರಭಾಗವಾಗಿದೆ (ಮರಗಳಲ್ಲಿ ಕವಲೊಡೆಯುವ ಅಂಶ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ). ಮತ್ತು ಆಗಲಿ. v ನ ಇನ್ಡೆಗ್ರೀ ಅನ್ನು ಡಿಗ್-(v) ಎಂದು ಸೂಚಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಅದರ ಔಟ್ ಡಿಗ್ರಿ ಅನ್ನು ಡಿಗ್ + (v) ಎಂದು ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಅದರ ಹೊರಬರುವ ಪ್ರತಿಯೊಂದು ಚಾಪಗಳ ಮೂಲವಾಗಿರುವುದರಿಂದ, ಅದರೊಂದಿಗಿನ ಶೃಂಗವನ್ನು ಮೂಲ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಅಂತೆಯೇ, ಅದರ ಪ್ರತಿಯೊಂದು ಒಳಬರುವ ಚಾಪಗಳ ಅಂತ್ಯವಾಗಿರುವುದರಿಂದ, ಅದರೊಂದಿಗಿನ ಶೃಂಗವನ್ನು ಸಿಂಕ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಡಿಗ್ರಿ ಮೊತ್ತದ ಸೂತ್ರವು, ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗೆ, ಪ್ರತಿ ಶೃಂಗಕ್ಕೂ, ಗ್ರಾಫ್ ಅನ್ನು ಸಮತೋಲಿತ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ನ ಡಿಗ್ರಿ ಅನುಕ್ರಮವು ಅದರ ಇನ್ಡೆಗ್ರೀ ಮತ್ತು ಔಟ್ ಡಿಗ್ರಿ ಜೋಡಿಗಳ ಪಟ್ಟಿಯಾಗಿದೆ; ಮೇಲಿನ ಉದಾಹರಣೆಗಾಗಿ ನಾವು ಡಿಗ್ರಿ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿದ್ದೇವೆ ((2,0), (2,2), (0,2), (1,1)). ಡಿಗ್ರಿ ಅನುಕ್ರಮವು ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಇನ್ವೇರಿಯಂಟ್ ಆಗಿರುವುದರಿಂದ ಐಸೊಮಾರ್ಫಿಕ್ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ಗಳು ಒಂದೇ ಡಿಗ್ರಿ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಆದಾಗ್ಯೂ, ಡಿಗ್ರಿ ಅನುಕ್ರಮವು, ಸಾಮಾನ್ಯವಾಗಿ, ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಅನ್ನು ಅನನ್ಯವಾಗಿ ಗುರುತಿಸುವುದಿಲ್ಲ; ಕೆಲವು ಸಂದರ್ಭಗಳಲ್ಲಿ, ಏಕರೂಪವಲ್ಲದ ಡಿಗ್ರ್ಯಾಫ್ಗಳು ಒಂದೇ ಡಿಗ್ರಿ ಅನುಕ್ರಮವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಸಾಕ್ಷಾತ್ಕಾರ ಸಮಸ್ಯೆಯು ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕ ಜೋಡಿಗಳ ನಿರ್ದಿಷ್ಟ ಅನುಕ್ರಮವಾದ ಡಿಗ್ರಿ ಅನುಕ್ರಮದೊಂದಿಗೆ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. (ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ಗೆ ಸೂಕ್ತ ಸಂಖ್ಯೆಯ ಪ್ರತ್ಯೇಕವಾದ ಶೃಂಗಗಳನ್ನು ಸೇರಿಸುವ ಮೂಲಕ ಅವುಗಳನ್ನು ಕ್ಷುಲ್ಲಕವಾಗಿ ಅರಿತುಕೊಳ್ಳುವುದರಿಂದ ಸೊನ್ನೆಗಳ ಹಿಂಭಾಗದ ಜೋಡಿಗಳನ್ನು ನಿರ್ಲಕ್ಷಿಸಬಹುದು.) ಒಂದು ಅನುಕ್ರಮವು ಕೆಲವು ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ನ ಡಿಗ್ರಿ ಅನುಕ್ರಮವಾಗಿದೆ, ಅಂದರೆ. ಇದಕ್ಕಾಗಿ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಸಾಕ್ಷಾತ್ಕಾರ ಸಮಸ್ಯೆಯು ಪರಿಹಾರವನ್ನು ಹೊಂದಿದೆ, ಇದನ್ನು ನಿರ್ದೇಶಿತ ಗ್ರಾಫಿಕ್ ಅಥವಾ ನಿರ್ದೇಶಿತ ಚಿತ್ರಾತ್ಮಕ ಅನುಕ್ರಮ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಈ ಸಮಸ್ಯೆಯನ್ನು ಕ್ಲೈಟ್ಮನ್-ವಾಂಗ್ ಕ್ರಮಾವಳಿ ಅಥವಾ ಫುಲ್ಕರ್ಸನ್-ಚೆನ್-ಅನ್ಸ್ಟೀ ಪ್ರಮೇಯದಿಂದ ಪರಿಹರಿಸಬಹುದು. ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಸಂಪರ್ಕವು ಗ್ರಾಫ್ನ ಎಲ್ಲಾ ನಿರ್ದೇಶಿತ ಅಂಚುಗಳನ್ನು ನಿರ್ದೇಶಿಸದ ಅಂಚುಗಳೊಂದಿಗೆ ಬದಲಿಸುವ ಮೂಲಕ ಪಡೆದ ನಿರ್ದೇಶಿಸದ ಆಧಾರವಾಗಿರುವ ಗ್ರಾಫ್ ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ ಆಗಿದ್ದರೆ ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ ಅನ್ನು ದುರ್ಬಲವಾಗಿ ಸಂಪರ್ಕಿಸಲಾಗಿದೆ (ಅಥವಾ ಕೇವಲ ಸಂಪರ್ಕಿಸಲಾಗಿದೆ). ಪ್ರತಿ ಜೋಡಿ ಶೃಂಗಗಳಿಗೆ x ನಿಂದ y ಗೆ (ಮತ್ತು y ನಿಂದ x ಗೆ) ನಿರ್ದೇಶಿತ ಮಾರ್ಗವನ್ನು ಹೊಂದಿದ್ದರೆ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಬಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದೆ ಅಥವಾ ಬಲವಾಗಿರುತ್ತದೆ. ಬಲವಾದ ಘಟಕಗಳು ಗರಿಷ್ಠ ಬಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದ ಉಪಗ್ರಫ್ಗಳಾಗಿವೆ. ಸಂಪರ್ಕಿತ ಬೇರೂರಿರುವ ರೇಖಾಚಿತ್ರವು (ಅಥವಾ ಹರಿವಿನ ರೇಖಾಚಿತ್ರ) ಪ್ರತ್ಯೇಕವಾದ ಮೂಲ ಶೃಂಗದಿಂದ ಪ್ರತಿ ಶೃಂಗಕ್ಕೂ ನಿರ್ದೇಶಿತ ಮಾರ್ಗವಿರುವ ಒಂದು ರೇಖಾಚಿತ್ರವಾಗಿದೆ. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳನ್ನೂ ಸಹ ನೋಡಿ (2007ರ ತಿದ್ದುಪಡಿ ಮಾಡಲಾದ 1ನೇ ಆವೃತ್ತಿಯು ಈಗ ಲೇಖಕರ ಜಾಲತಾಣದಲ್ಲಿ ಉಚಿತವಾಗಿ ಲಭ್ಯವಿದೆ; 2ನೇ ಆವೃತ್ತಿಯು 2009ರಲ್ಲಿ ಪ್ರಕಟವಾಯಿತು). .. .. (ಎಲೆಕ್ಟ್ರಾನಿಕ್ 3 ನೇ ಆವೃತ್ತಿಯು ಲೇಖಕರ ಜಾಲತಾಣದಲ್ಲಿ ಉಚಿತವಾಗಿ ಲಭ್ಯವಿದೆ). .. ಪೂರ್ಣಾಂಕ ಅನುಕ್ರಮಗಳ ಆನ್-ಲೈನ್ ಎನ್ಸೈಕ್ಲೋಪೀಡಿಯಾದಿಂದ n ನೋಡ್ಗಳೊಂದಿಗೆ ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ಗಳ ಸಂಖ್ಯೆ (ಅಥವಾ ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ಗಳು) ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ನಿರ್ದೇಶಿಸಿದ ಗ್ರಾಫ್ಗಳು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಗ್ರಾಫ್ ಡೇಟಾ ರಚನೆಗಳು