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