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