Series–parallel graph
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ಗಳು ಟರ್ಮಿನಲ್ಗಳು ಎಂದು ಕರೆಯಲ್ಪಡುವ ಎರಡು ವಿಶಿಷ್ಟ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ಗಳಾಗಿದ್ದು, ಎರಡು ಸರಳ ಸಂಯೋಜನೆಯ ಕಾರ್ಯಾಚರಣೆಗಳಿಂದ ಪುನರಾವರ್ತಿತವಾಗಿ ರೂಪುಗೊಳ್ಳುತ್ತವೆ. ಅವುಗಳನ್ನು ಸರಣಿ ಮತ್ತು ಸಮಾನಾಂತರ ವಿದ್ಯುತ್ ಸರ್ಕ್ಯೂಟ್ಗಳನ್ನು ರೂಪಿಸಲು ಬಳಸಬಹುದು. ವ್ಯಾಖ್ಯಾನ ಮತ್ತು ಪರಿಭಾಷೆ ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಗ್ರಾಫ್ ಎಂಬ ಪದವು ಬಹುವಿಜ್ಞಾನ ಎಂದರ್ಥ. ಸರಣಿ-ಸಮಾನಾಂತರ ರೇಖಾಚಿತ್ರಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲು ಹಲವಾರು ಮಾರ್ಗಗಳಿವೆ. ಈ ಕೆಳಗಿನ ವ್ಯಾಖ್ಯಾನವು ಮೂಲತಃ ಡೇವಿಡ್ ಎಪ್ಸ್ಟೀನ್ ಬಳಸಿದ ವ್ಯಾಖ್ಯಾನವನ್ನು ಅನುಸರಿಸುತ್ತದೆ. ಎರಡು-ಟರ್ಮಿನಲ್ ಗ್ರಾಫ್ (ಟಿಟಿಜಿ) ಯು ಎರಡು ವಿಶಿಷ್ಟ ಶೃಂಗಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ ಆಗಿದೆ, ಎಸ್ ಮತ್ತು ಟಿ ಅನ್ನು ಅನುಕ್ರಮವಾಗಿ ಸೋರ್ಸ್ ಮತ್ತು ಸಿಂಕ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. X ಮತ್ತು Y ಎಂಬ ಎರಡು TTGಗಳ ಸಮಾನಾಂತರ ಸಂಯೋಜನೆಯಾದ Pc = Pc (X, Y), X ಮತ್ತು Y ರೇಖಾಚಿತ್ರಗಳ ಬೇರ್ಪಡಿಸಿದ ಸಂಯೋಜನೆಯಿಂದ ರಚಿಸಲಾದ TTGಯಾಗಿದ್ದು, ಇದು X ಮತ್ತು Y ಮೂಲಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಿ PCಯ ಮೂಲವನ್ನು ಸೃಷ್ಟಿಸುತ್ತದೆ ಮತ್ತು X ಮತ್ತು Yಯ ಸಿಂಕ್ಗಳನ್ನು ವಿಲೀನಗೊಳಿಸಿ PCಯ ಸಿಂಕ್ ಅನ್ನು ರಚಿಸುತ್ತದೆ. ಎರಡು ಟಿಟಿಜಿಗಳಾದ ಎಕ್ಸ್ ಮತ್ತು ವೈ ಗಳ ಸರಣಿ ಸಂಯೋಜನೆಯಾದ ಎಸ್ಸಿ = ಎಸ್ಸಿ (ಎಕ್ಸ್, ವೈ) ಯು ಎಕ್ಸ್ ಮತ್ತು ವೈ ರೇಖಾಚಿತ್ರಗಳ ಬೇರ್ಪಡುವ ಒಕ್ಕೂಟದಿಂದ ರಚಿಸಲಾದ ಟಿಟಿಜಿಯಾಗಿದ್ದು, ಎಕ್ಸ್ ನ ಸಿಂಕ್ ಅನ್ನು ವೈ ಮೂಲದೊಂದಿಗೆ ವಿಲೀನಗೊಳಿಸುತ್ತದೆ. X ನ ಮೂಲವು SC ನ ಮೂಲವಾಗುತ್ತದೆ ಮತ್ತು Y ನ ಸಿಂಕ್ SC ನ ಸಿಂಕ್ ಆಗುತ್ತದೆ. ಎರಡು-ಟರ್ಮಿನಲ್ ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ (ಟಿಟಿಎಸ್ಪಿಜಿ) ಎನ್ನುವುದು ನಿಗದಿಪಡಿಸಿದ ಟರ್ಮಿನಲ್ಗಳೊಂದಿಗೆ ಏಕ-ಅಂಚಿನ ಗ್ರಾಫ್ ಕೆ 2 ನ ಪ್ರತಿಗಳ ಗುಂಪಿನಿಂದ ಪ್ರಾರಂಭವಾಗುವ ಸರಣಿ ಮತ್ತು ಸಮಾನಾಂತರ ಸಂಯೋಜನೆಗಳ ಅನುಕ್ರಮದಿಂದ ನಿರ್ಮಿಸಬಹುದಾದ ಗ್ರಾಫ್ ಆಗಿದೆ. ವ್ಯಾಖ್ಯಾನ 1. ಅಂತಿಮವಾಗಿ, ಗ್ರಾಫ್ ಅನ್ನು ಸರಣಿ-ಸಮಾನಾಂತರ (ಎಸ್. ಪಿ.-ಗ್ರಾಫ್) ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಅದು ಟಿ. ಟಿ. ಎಸ್. ಪಿ. ಜಿ ಆಗಿದ್ದರೆ, ಅದರ ಕೆಲವು ಎರಡು ಶೃಂಗಗಳನ್ನು ಮೂಲ ಮತ್ತು ಸಿಂಕ್ ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. ಇದೇ ರೀತಿಯಲ್ಲಿ ಒಬ್ಬರು ಸರಣಿ-ಸಮಾನಾಂತರ ಡಿಗ್ರ್ಯಾಫ್ಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಏಕ-ಕಮಾನಿನ ಗ್ರಾಫ್ಗಳ ಪ್ರತಿಗಳಿಂದ ನಿರ್ಮಿಸಲಾಗಿದೆ, ಮೂಲದಿಂದ ಸಿಂಕ್ಗೆ ನಿರ್ದೇಶಿಸಲಾದ ಕಮಾನುಗಳೊಂದಿಗೆ. ಪರ್ಯಾಯ ವ್ಯಾಖ್ಯಾನ ಈ ಕೆಳಗಿನ ವ್ಯಾಖ್ಯಾನವು ಅದೇ ವರ್ಗದ ಗ್ರಾಫ್ಗಳನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸುತ್ತದೆ. ವ್ಯಾಖ್ಯಾನ 2. ಈ ಕೆಳಗಿನ ಕಾರ್ಯಾಚರಣೆಗಳ ಅನುಕ್ರಮದಿಂದ ಅದನ್ನು ಕೆ2 ಆಗಿ ಪರಿವರ್ತಿಸಬಹುದಾದರೆ ಗ್ರಾಫ್ ಒಂದು ಎಸ್. ಪಿ-ಗ್ರಾಫ್ ಆಗಿರುತ್ತದೆಃ ಸಮಾನಾಂತರ ಅಂಚುಗಳ ಜೋಡಿಯನ್ನು ಅವುಗಳ ಸಾಮಾನ್ಯ ಅಂತಿಮ ಬಿಂದುಗಳನ್ನು ಸಂಪರ್ಕಿಸುವ ಒಂದೇ ಅಂಚಿನೊಂದಿಗೆ ಬದಲಾಯಿಸುವುದು. ಗುಣಲಕ್ಷಣಗಳು ಪ್ರತಿ ಸರಣಿ-ಸಮಾನಾಂತರ ರೇಖಾಚಿತ್ರವು ಗರಿಷ್ಠ 2 ನೇ ತ್ರಿ ಅಗಲ ಮತ್ತು ಗರಿಷ್ಠ 2 ನೇ ಶಾಖೆಯ ಅಗಲವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ವಾಸ್ತವವಾಗಿ, ಪ್ರತಿ ದ್ವಿ-ಸಂಪರ್ಕಿತ ಘಟಕವು ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ ಆಗಿದ್ದರೆ ಮತ್ತು ಅದು ಗರಿಷ್ಠ 2 ಶಾಖೆಯ ಅಗಲವನ್ನು ಹೊಂದಿದ್ದರೆ ಮಾತ್ರ ಗ್ರಾಫ್ ಗರಿಷ್ಠ 2 ತ್ರಿ-ಅಗಲವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಗರಿಷ್ಠ ಸರಣಿ-ಸಮಾನಾಂತರ ರೇಖಾಚಿತ್ರಗಳು, ಅವುಗಳ ಸರಣಿ-ಸಮಾನಾಂತರ ರಚನೆಯನ್ನು ನಾಶಪಡಿಸದೆ ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಅಂಚುಗಳನ್ನು ಸೇರಿಸಲಾಗದ ರೇಖಾಚಿತ್ರಗಳು ನಿಖರವಾಗಿ 2-ಮರಗಳಾಗಿವೆ. 2-ಸಂಪರ್ಕಿತ ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ಗಳು ಕೆ4 ಗೆ ಯಾವುದೇ ಉಪಗ್ರ್ಯಾಫ್ ಹೋಮಿಯೊಮಾರ್ಫಿಕ್ ಅನ್ನು ಹೊಂದಿಲ್ಲ. ಸರಣಿಯ ಸಮಾನಾಂತರ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಅವುಗಳ ಕಿವಿ ವಿಭಜನೆಗಳಿಂದಲೂ ನಿರೂಪಿಸಬಹುದು. ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಎಸ್. ಪಿ-ಗ್ರಾಫ್ಗಳನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಗುರುತಿಸಬಹುದು ಮತ್ತು ಅವುಗಳ ಸರಣಿ-ಸಮಾನಾಂತರ ವಿಭಜನೆಯನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲೂ ನಿರ್ಮಿಸಬಹುದು. ಕೆಲವು ರೀತಿಯ ವಿದ್ಯುತ್ ಜಾಲಗಳ ಮಾದರಿಯಾಗಿರುವುದರ ಜೊತೆಗೆ, ಈ ಗ್ರಾಫ್ಗಳು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಆಸಕ್ತಿಯನ್ನು ಹೊಂದಿವೆ, ಏಕೆಂದರೆ ಗರಿಷ್ಠ ಹೊಂದಾಣಿಕೆ, ಗರಿಷ್ಠ ಸ್ವತಂತ್ರ ಸೆಟ್, ಕನಿಷ್ಠ ಪ್ರಾಬಲ್ಯದ ಸೆಟ್ ಮತ್ತು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಪೂರ್ಣಗೊಳಿಸುವಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಸೇರಿದಂತೆ ಹಲವಾರು ಪ್ರಮಾಣಿತ ಗ್ರಾಫ್ ಸಮಸ್ಯೆಗಳನ್ನು ಎಸ್. ಪಿ-ಗ್ರಾಫ್ಗಳಲ್ಲಿ ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಈ ಕೆಲವು ಸಮಸ್ಯೆಗಳು ಸಾಮಾನ್ಯ ಗ್ರಾಫ್ಗಳಿಗೆ ಎನ್. ಪಿ-ಪೂರ್ಣವಾಗಿವೆ. ಈ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಒಂದಕ್ಕೆ ಉತ್ತರಗಳು ಎರಡು ಎಸ್. ಪಿ-ಗ್ರಾಫ್ಗಳಿಗೆ ತಿಳಿದಿದ್ದರೆ, ಅವರ ಸರಣಿ ಮತ್ತು ಸಮಾನಾಂತರ ಸಂಯೋಜನೆಗಳಿಗೆ ಉತ್ತರವನ್ನು ತ್ವರಿತವಾಗಿ ಕಂಡುಹಿಡಿಯಬಹುದು ಎಂಬ ಅಂಶವನ್ನು ಪರಿಹಾರವು ಲಾಭ ಮಾಡಿಕೊಳ್ಳುತ್ತದೆ. ಸಾಮಾನ್ಯೀಕರಣ ಸಾಮಾನ್ಯೀಕೃತ ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ಗಳು (ಜಿಎಸ್ಪಿ-ಗ್ರಾಫ್ಗಳು) ಉಲ್ಲೇಖಿಸಲಾದ ಸಮಸ್ಯೆಗಳಿಗೆ ಅದೇ ಕ್ರಮಾವಳಿ ದಕ್ಷತೆಯನ್ನು ಹೊಂದಿರುವ ಎಸ್ಪಿ-ಗ್ರಾಫ್ಗಳ ವಿಸ್ತರಣೆಯಾಗಿದೆ. ಜಿಎಸ್ಪಿ-ಗ್ರಾಫ್ಗಳ ವರ್ಗವು ಎಸ್ಪಿ-ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಔಟರ್ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳ ವರ್ಗಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಜಿ. ಎಸ್. ಪಿ ಗ್ರಾಫ್ಗಳನ್ನು ವ್ಯಾಖ್ಯಾನ 2ರ ಮೂಲಕ ನಿರ್ದಿಷ್ಟಪಡಿಸಬಹುದು, ಇದು ತೂಗಾಡುತ್ತಿರುವ ಶೃಂಗವನ್ನು (ಡಿಗ್ರಿ 1ರ ಶೃಂಗ) ಅಳಿಸುವ ಮೂರನೇ ಕಾರ್ಯಾಚರಣೆಯೊಂದಿಗೆ ವರ್ಧಿತವಾಗಿದೆ. ಪರ್ಯಾಯವಾಗಿ, 1ನೇ ವ್ಯಾಖ್ಯಾನವನ್ನು ಈ ಕೆಳಗಿನ ಕಾರ್ಯಾಚರಣೆಯೊಂದಿಗೆ ಹೆಚ್ಚಿಸಬಹುದು. X ಮತ್ತು Y ಎಂಬ ಎರಡು TTGಗಳ S = M (X, Y) ಅನ್ನು ವಿಲೀನಗೊಳಿಸುವ ಮೂಲವು, Xನ ಮೂಲವನ್ನು Yನ ಮೂಲದೊಂದಿಗೆ ವಿಲೀನಗೊಳಿಸುವ ಮೂಲಕ X ಮತ್ತು Y ನಕ್ಷೆಗಳ ಬೇರ್ಪಡುವ ಸಂಯೋಜನೆಯಿಂದ ರಚಿಸಲಾದ TTG ಆಗಿದೆ. Xನ ಮೂಲ ಮತ್ತು ಮುಳುಗುವಿಕೆಯು ಅನುಕ್ರಮವಾಗಿ Pನ ಮೂಲ ಮತ್ತು ಮುಳುಗುವಿಕೆಯಾಗುತ್ತವೆ. ಎಸ್ಪಿಕ್ಯುಆರ್ ಮರವು ಒಂದು ಮರದ ರಚನೆಯಾಗಿದ್ದು, ಇದನ್ನು ಅನಿಯಂತ್ರಿತ 2-ವೆರ್ಟೆಕ್ಸ್-ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ಗೆ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. ಇದು ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ಗಳಲ್ಲಿನ ಸರಣಿ ಸಂಯೋಜನೆಯ ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ಹೋಲುವ ಎಸ್-ನೋಡ್ಗಳನ್ನು, ಸರಣಿ-ಸಮಾನಾಂತರ ಗ್ರಾಫ್ಗಳಲ್ಲಿನ ಸಮಾನಾಂತರ ಸಂಯೋಜನೆಯ ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ಹೋಲುವ ಪಿ-ನೋಡ್ಗಳನ್ನು ಮತ್ತು ಸರಣಿ-ಸಮಾನಾಂತರ ಸಂಯೋಜನೆಯ ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ಹೊಂದಿಕೆಯಾಗದ ಆರ್-ನೋಡ್ಗಳನ್ನು ಹೊಂದಿದೆ. ಅದರ ಎಸ್ಪಿಕ್ಯುಆರ್ ಮರದಲ್ಲಿ ಯಾವುದೇ ಆರ್-ನೋಡ್ಗಳಿಲ್ಲದಿದ್ದರೆ ಮಾತ್ರ 2-ಸಂಪರ್ಕಿತ ಗ್ರಾಫ್ ಸರಣಿ-ಸಮಾನಾಂತರವಾಗಿರುತ್ತದೆ. ಥ್ರೆಶೋಲ್ಡ್ ಗ್ರಾಫ್ ಸಹ ನೋಡಿ ಗ್ರಾಫ್ ಹ್ಯಾನರ್ ಪಾಲಿಟೋಪ್ ಸರಣಿ-ಸಮಾನಾಂತರ ಭಾಗಶಃ ಕ್ರಮ ಉಲ್ಲೇಖಗಳು ಗ್ರಾಫ್ ಕುಟುಂಬಗಳು ಗ್ರಾಫ್ ಕಾರ್ಯಾಚರಣೆಗಳು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು