ಗ್ರಾಫ್ ಸಿದ್ದಾಂತ್ ಮೂವರು ಹೂಟ್ಟೆಕಿಚ್ಚಿನ ಗಂಡಂದಿರ ಪೇಚು;ಮೂರು ಗಂಡ ಹೆಂಡಂದಿರ ಜೋಡಿಗಳು ತಮ್ಮ ಪ್ರವಾಸದಲ್ಲಿ ಒಂದು ನದಿಯನ್ನು ದಾಟ್ಟುವ ಪ್ರಸಂಗ ಬರುತ್ತದೆ.ಆಲ್ಲಿ ಇದ್ದ ಸಣ್ಣ ನಾವೆ ಒಂದು ಇಬ್ಬರನ್ನು ಮಾತ್ರ ಒಯ್ಯಬಲ್ಲದು.ಪ್ರತಿಯೂಂದು ವ್ಯಕ್ತಿಗೂ ದೋಣೆ ನಡೆಸಲು ಬರುತ್ತದೆ.ಎಲ್ಲ ಗಂಡಂದಿರೂ ಬಲು ಹೂಟ್ಟೆಕಿಚ್ಚಿನವರು ಮತ್ತು ಸಂಶಯಪ್ರಕೃತಿಯವರು.ತಾವಿಲ್ಲದಿರುವಾಗ ತಮ್ಮ ಹೆಂಡಂದಿರನ್ನು ಪರಪುರುಷ ಇರುವಲ್ಲಿ ಬಿಡಲು ಒಲ್ಲದವರು .ಹಾಗಾದರೆ ಆ ದಂಪತಿಗಳು ನದಿಯನ್ನು ಹೇಗೆ ದಾಟುತ್ತಾರೆ?ಈ ಸಮಸ್ಯೆಗೆ ಯುಕ್ತ ಪರಿಹಾರವನ್ನು ಗ್ರಾಫಿನ ಮೂಲಕ ಪಡೆಯಬಹುದು.ಆಟಗಳು ಮತ್ತು ಗ್ರಾಫುಗಳು ; ಈ ಮೂದಲೇ ಹೇಳಿರುವಂತೆ ಗ್ರಾಫುಗಳನ್ನು ಆಟಗಳಿಗೂ ಸಂಯೋಜಿಸಲಾಗಿದೆ;ಹೀಗೆ ಮಾಡುವಾಗ ಸಾಮಾನ್ಯವಾಗಿ ಗ್ರಾಫಿನ ಶೃಂಗಗಳು ಆಟದಲ್ಲಿಯ ಸ್ಥಾನಗಳನ್ನು ಗುರುತಿಸುತ್ತವೆ;ಮತ್ತು ಆಂಚುಗಳು ಆಟದಲ್ಲಿಯ ನಿಯಮಗಳಿಗೆ ಆನುಸಾರವಾದ ಚಲನಗಳನ್ನು ಗುರುತಿಸುತ್ತವೆ.ಒಂದು ಸ್ಥಾನದ್ದಿಂದ ಮತ್ತೂಂದು ನಿದಿ೯ಷ್ಟ ಸ್ಥಾನಕ್ಕೆ ಹೋಗಲು ಸಾಧ್ಯವೇ ಎಂಬುದು ಆಟಗಳಲ್ಲಿನ ಒಂದು ಸಾಮಾನ್ಯ ಸಮಸ್ಯೆ.ಈ ಸಮಸ್ಯೆಯನ್ನು ಗ್ರಾಫಿನ ಭಾಷೆಯಲ್ಲಿ ಹೀಗೆನ್ನಬಹುದು;ಆಟವನ್ನು ಗ್ರಾಫಿನ ಮೂಲಕ ನಿರೂಅಪಿಸಿದಾಗ ಎರುಡು ದತ್ತ ಶೃಂಗಗಳು ಗ್ರಾಫಿನ ಒಂದೇ ಸಂಯೋಜಿತ ಘಟಕದಲ್ಲಿ (ಕನೆಕ್ಟೆಡ್ ಕಾಂಪೂನೆಂಟ್)ಇರುತ್ತವೆಯೂ ಇಲ್ಲವೂ ಎಂಬುದನ್ನು ಕಂಡುಹಿಡಿಯುವಿಕೆ.ಉದಾಹರಣೆಗಾಗಿ ಚದುರಂಗದ ಆಟವನ್ನು ತೆಗೆದುಕೂಳ್ಳೋಣ.ಇದರಲ್ಲಿರುವ ೬೪ ಚೌಕಗಳನ್ನು ೬೪ ಶೃಂಗಗಳಿಂದ ಗುರುತಿಸೋಣ.ಈ ಆಟದಲ್ಲಿ ಮಂತ್ರಿಯ ನಡೆಯನ್ನು ಗಮನಿಸೋಣ.ಇದು ಆಷ್ಟೂಂದು .ಕಾರಣ ಮಂತ್ರಿ ಒಂದು ಚೌಕದಿಂದ ಯಾವ ಮತ್ತೂಂದು ಚೌಕಕ್ಕಾದರೂ ಹೋಗಬಲ್ಲವನಾಗಿದ್ದಾನೆ.ಈ ೬೪ ಶೃಂಗಗಳ ಮೇಲೆ ಮಂತ್ರಿಯ ನಡೆಯನ್ನು ನಿರೂಪಿಸುವ ಗ್ರಾಫನ್ನು ಎಳೆಯೋಣ.ಗ್ರಾಫಿನಲ್ಲಿ ಮಂತ್ರಿ ಒಂದು ಶೃಂಗದಿಂದ ಮತ್ತೂಂದು ಶೃಂಗಕ್ಕೆ ಒಂದು ನಡೆಯಲ್ಲಿ ಹೋಗುವುದಕ್ಕಾದರೆ ಆವೆರಡು ಬಿಂದುಗಳನ್ನು ಒಂದು ಆಂಚಿನಿಂದ ಸೇರಿಸುತ್ತೆವೆ.ಮಂತ್ರಿ ಒಂದು ಚೌಕದಿಂದ ಹೂರಟು ಪ್ರತಿಯೊಂದು ಚೌಕಕ್ಕೂ ಒಮ್ಮೆ ಮಾತ್ರ ಹೋಗಿ ೬೪ ಚೌಕಗಳನ್ನೂ ಸುತ್ತಿ ತನ್ನ ಮೊದಲಿನ ಸ್ಥಾನಕ್ಕೆ ಬರಬಹುದೇ ಎಂಬುದು ಇಲ್ಲಿನ ಒಂದು ಸುಪ್ರಸಿದ್ಧ ಸಮಸ್ಯೆ ಇದನ್ನೇ ಗ್ರಾಫಿನ ಒಂದು ಸಮಸ್ಯೆಯನ್ನಾಗಿ ಹೀಗೆ ಹೇಳಬಹುದು;ಈ ಆಟದ ಒಂದು ಗ್ರಾಫಿನಲ್ಲಿ ಹ್ಯಾಮಿಲ್ವನ್ನನ ಒಂದು ಚಕ್ರವಿದೆಯೇ? ಇದಕ್ಕೆ ಆನೇಕ ಉತ್ತರಗಳಿವೆ. ೬೩ ೨೨ ೧೫ ೪೦ ೧ ೪೨ ೫೮ ೧೮ ೧೪ ೩೯ ೬೪ ೨೧ ೬೦ ೧೭ ೨ ೪೩ ೩೭ ೬೨ ೨೩ ೧೬ ೪೧ ೪ ೧೯ ೫೮ ೨೪ ೧೩ ೩೬ ೬೧ ೨೦ ೫೭ ೪೪ ೩ ೧೧ ೩೬ ೨೫ ೫೨ ೨೯ ೪೬ ೫ ೫೬ ೨೬ ೫೧ ೧೨ ೩೩ ೮ ೫೫ ೩೦ ೪೫ ೩೫ ೧೦ ೪೯ ೨೮ ೫೩ ೩೨ ೪೭ ೬ ೫೦ ೨೭ ೩೪ ೯ ೪೮ ೭ ೫೪ ೩೧ ವೃಕ್ಷ; ಚಕ್ರಗಳಿಲ್ಲದ ಸಂಯೋಜಕ ಗ್ರಾಫಿಗೆ ವೃಕ್ಷ (ಟ್ರೀ) ಎಂದು ಹೆಸರು.ಉದಾಹರಣೆಗೆ ಚಿತ್ರ(೯) ನ್ನು ನೋಡಬಹುದು.ಇಂಥ ಒಂದು ವೃಕ್ಷದಲ್ಲಿ v ಶೃಂಗಗಳೂ e ಆಂಚಗಳೂ ಇದ್ದರೆ ಆವುಗಳ ನಡುವೆ v=e+1 ಎಂಬ ಸುಲಭ ಸಂಬಂಧವಿರುವುದು ಕಾಣುತ್ತದೆ.ಸಾಮ್ಯಗಳು (ಮ್ಯಾಚಿಂಗ್ಸ್);ಉದ್ಯೋಗಾವಕಾಶಗಳು ಮತ್ತು ಆಭ್ಯಥಿ೯ಗಳು;ಒಂದು ಕಾಖಾ೯ನೆಯಲ್ಲಿ ಕೆಲವು ಖಾಲಿ ಹುದ್ದೆಗಳು ಮತ್ತು ಆವಕ್ಕೆ ಕೆಲವು ಆಭ್ಯಥಿ೯ಗಳು ಇರಲಿ.ಆಗ ಈ ಕೆಳಗಿನ ಸಮಸ್ಯೆ ಉದ್ಭವಿಸುತ್ತದೆ;ಪ್ರತಿಯೊಂದು ಆಭ್ಯಥಿ೯ಗೂ ಅವನ ಆಹ೯ತೆಗೆ ಸರಿಯಾದ ಒಂದು ಹುದ್ದೆಯನ್ನು ಕೂಡಲು ಸಾಧ್ಯವೇ? ಈ ಸಂದಭ್೯ವನ್ನು ಒಂದು ಗ್ರಾಫಿನ ಮೂಲಕ ವಿವರಿಸಬಹುದು.ಉದಾಹರಣೆಗಾಗಿ ಚಿತ್ರ(೯)ನೋಡಬಹುದು.ಇದರಲ್ಲಿ M ಹುದ್ದೆಗಳ ಗುಂಪನ್ನೂ P ಆಭ್ಯಥಿ೯ಗಳ ಗುರುತಿಸಲಿ.m1,m2,m3,m4 ಬೇರೆ ಬೇರೆ ಖಾಲಿ ಹುದ್ದೆಗಳನ್ನೂ p1,p2,p3,p4,p5 ಈ ಹುದ್ದೆಗಳಿಗೆ ಆಭ್ಯಥಿ೯ಗಳನ್ನೂ ಸೂಚಿಸಲಿ.ಈ ಶೃಂಗಗಳ ಮೇಲೆ ಒಂದು ಗ್ರಾಫನ್ನು ಹೀಗೆ ರಚಿಸಬಹುದು.
p ಆಭ್ಯಥಿ೯ m ಹುದ್ದೆಗೆ ಅಹ೯ನಾಗಿದ್ದರೆ PM ಆಂಚನ್ನು ಎಳೆಯುತ್ತೇವೆ.ಉಆಭ್ಯಥಿ೯ಗಳದಾಹರಣೆಗಾಗಿ ಚಿತ್ರ (೯)ರಲ್ಲಿ P1 ಆಭ್ಯಥಿ೯ m2 ಮತ್ತು m3 ಹುದ್ದೆಗಳಿಗೆ ಆಹ೯ ಎಂದು ಕಾಣಬಹುದು.ಇಲ್ಲಿ ಗಮನಿಸಬೇಕಾದ ವಿಷಯವೆಂದರೆ ಆಭ್ಯಥಿ೯ಗಳ ಗುಂಪಿನಲ್ಲಿ ಆಭ್ಯಥಿ೯ಗಳನ್ನು ಕೂಡಿಸುವ ಆಂಚುಗಳು ಹಾಗೂ ಹುದ್ದೆಗೆಳ ಗುಂಪಿನಲ್ಲಿ ಹುದ್ದೆಗಳನ್ನು ಕೂಡಿಸುವ ಆಂಚಗಳು ಇಲ್ಲ.ಇಂಥ ಒಂದು ಗ್ರಾಫಿನ ಶೃಂಗಗಣವನ್ನು p ಮತ್ತು m ಎಂಬ ಎರಡು ವಿಘಟಿತ ಗಣಗಳನ್ನಾಗಿ ವಿಂಗ
ಡಿಸಿ, P ಮತ್ತು M ಶೃಂಗಗಳನ್ನು ಮಾತ್ರ ಜೋಡಿಸಿ ಪಡೆಯುವ ಗ್ರಾಫಿಗೆ ದ್ವಿಭಾಜಿತ ಗ್ರಾಫ ಎಂದು ಹೆಸರು.ಚಿತ್ರ (೯) ಒಂದು ದ್ವಿಭಾಜಿತ್ ಗ್ರಾಫ್.ಆಭ್ಯಥಿ೯ಗಳೆಲ್ಲರಿಗೂ ಹುದ್ದೆಗಳನ್ನು ಕೂಡಬೇಕಾದರೆ ಮೊದಲು ಎಷ್ಟು ಆಭ್ಯಥಿ೯ಗಳಿರುವರೋ ಆಷ್ಟು ಹುದ್ದೆಗಳಿರಬೇಕು.ಆದರೆ ಇಷ್ಟೇ ಸಾಲದು.ಉದಾಹರಣೆಗೆ ಆಭ್ಯಥಿ೯ಗಳಲ್ಲಿ ಇಬ್ಬರು ಮರಗೆಲಸ (ಬಡಗಿತನ)ಬಲ್ಲವರು ಮತ್ತು ಒಬ್ಬ ಬಡಗಿತನ ಹಾಗೂ ಕೊಳಾಯಿ ಕೆಲಸ ಬಲ್ಲವ ಇರಲ್ಲಿ.ಹುದ್ದೆಗಳಲ್ಲಿ ಒಂದು ಬಡಗಿತನದ ಹುದ್ದೆ ಮತ್ತು ಮೂರು ಕೂಳಾಯಿಗಾರ ಹುದ್ದೆಗಳು ಖಾಲಿ ಇರಲಿ.ಈ ಸಂದಭ೯ದಲ್ಲಿ ಒಂದು ಬಡಗಿತನದ ಹುದ್ದೆಯನ್ನು ಮೂವರಲ್ಲಿ ಯಾರಿಗಾದರೂ ಕೂಡಬಹುದು.ಮೂರು ಕೂಳಾಯಿಗಾರ ಹುದ್ದೆಗಳಲ್ಲಿ ಒಂದನ್ನು ಆ ಕೆಲಸ ಬಲ್ಲವನಿಗೆ ಕೂಡಬಹುದು.ಹೀಗಾದಲ್ಲಿ ಬಡಗಿಯೂಬ್ಬನಿಗೆ ಹುದ್ದೆ ಇಲ್ಲದಂತೆ ಆಗುತ್ತದೆ.ಈಗ n ಆಭ್ಯಥಿ೯ಗಳ
j ಹುದ್ದೆಗಳಿಗೆ ಅಜಿ೯ ಹಾಕಿದ್ದಾರೆಂದು ಭಾವಿಸೋಣ.ಆಗ ಪ್ರತಿಯೊಬ್ಬ ಆಭ್ಯಥಿ೯ಗೂ ಅವನ ಆಹ೯ತೆಗೆ ಸರಿಯಾದ ಒಂದು ಹುದ್ದೆಯನ್ನು ಈ ಕೆಳಗಿನ ನಿಯಮ ನಿಜ,ಮತ್ತು ನಿಜವಾದರೆ ಮಾತ್ರ ಕೂಡಬಹುದು.ಪ್ರತಿಯೊಂದು ಸಂಖ್ಯೆ k=1,2,......n
ಗೂ k ಆಭ್ಯಥಿ೯ಗಳು ಸಮಗ್ರವಾಗಿ ಆಹ೯ತೆ ಪಡೆದಿರುವ ಕನಿಷ್ಟ k ಹುದ್ದೆಗಳು ಇರಲೇಬೇಕು.ಆಯ್ಲರನ ಸೂತ್ರ;ಒಂದು ಬಹುಫಲಕದಲ್ಲಿ (ಪಾಲಿಹೆಡ್ರ)v ಶೃಂಗಗಳು, E ಆಂಚುಗಳು ಹಾಗೂ F ಫಲಕಗಳು ಇರಲಿ,ಆಯ್ಲರನ
ಸೂತ್ರದ ಮೇರೆಗೆ ಯಾವಾಗಲೂ V-E+F=2 ಆಗಿರುತ್ತದೆ. ಉದಾಹರಣೆಗೆ ಘನ ತ್ರಿಕೋನದಲ್ಲಿ V=4,E=6,F=4 ಘನಚೌಕದಲ್ಲಿ V=8,E=12,F=6 ನಕ್ಷೆಗಳಿಗೆ ಬಣ್ಣ ಬಳಿಯುವಿಕೆ;ಒಂದು ದೇಶದ ನಕ್ಷೆಯಲ್ಲಿರುವ (ಮ್ಯಾಪ್)ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ರಾಜ್ಯಗಳಿಗೆ ಉಭಯಸಾಮಾನ್ಯವಾದ ಒಂದು ಸರಹದ್ದು ಇದ್ದರೆ ಅವುಗಳಿಗೆ ಅಕ್ಕಪಕ್ಕದ ರಾಜ್ಯಗಳು ಎಂದು ಹೆಸರು.ಒಂದು ನಕ್ಷೆಗೆ ಬಣ್ಣ ಬಳಿಯುವಿಕೆ ಎಂದರೆ.
