ಗ್ರಾಫ್ ಸಿಧಾಂತ
ನಡೆ ಅಲ್ಲ. V1 V2 V3 V4 V2 ಆದರೂ V1,V2 ತುಣುಕು ನಡೆ; ಆದರೆ ಇದು V1 V2 ದಾರಿಯಲ್ಲ. ಈಗ V1 V2 V3 V4 V5 V6 ಎಂಬುದು V1-V6 ದಾರಿ ಮತ್ತು V1 V2 V3 V4 V2 ಒಂದು ಚಕ್ರ ಈಗ V1 V2 V3 V4 V5 V6 ಎಂಬುದು V2-V6 ದಾರಿ ಮತ್ತು,V2 V3 V4 V2 ಒಂದು ಚಕ್ರ.
ಒಂದು ಗ್ರಾಫಿನಲ್ಲಿ ಪ್ರತಿ ಒಂದು ಜೊತೆ ಶ್ರಂಗಗಳಿಗೂ ಅವನ್ನು ಸೇರಿಸುವ ಒಂದು ದಾರಿ ಇದ್ದರೆ ಆ ಗ್ರಾಫಿಗೆ ಸಂಯೋಜತ ಗ್ರಾಫ್ ಎಂದು ಹೆಸರು.
ಕ್ಯೋನಿಷ್ ಬರ್ಗ್ ಸೇತುವೆಗಳ ಸಮಸ್ಯೆ: ಪ್ರಕೃತ ಕ್ಯಾಲಿನಿನ್ ಗ್ರಾಡ್ ಎಂದು ಹೆಸರಿರುವ ಕ್ಯೋನಿಷ್ ಬರ್ಗ್ ಪೊರ್ವ ಪ್ರಷ್ಯದಲ್ಲಿನ ಒಂದು ನಗರ. ಇದು ನಡುಗಡ್ಡೆಗಳನ್ನೊಳಗೊಂಡಿರುವ ಪ್ರಗಲ್ ಎಂಬ ಹೆಸರಿನ ನದಿಯ ದಂಡೆಯಲ್ಲಿದೆ. ಈ ಪಟ್ಟಣ್ಣದ ನಡುಗಡ್ಡೆಗಳನ್ನೊ ಉಳಿದ ಭಾಗಗಳನ್ನೊ ಚಿತ್ರ(4)ರಲ್ಲಿ ತೋರಿಸಿರುವಂತೆ P,Q,R,S,T,U,V ಎಂಬ ಏಳು ಸೇತುವೆಗಳಿಂದ ಜೋಡಿಸಲಾಗದೆ. ಕ್ಯೋನಿಷ್ ಬರ್ಗ್ ಸೇತುವೆಗಳ ಸಮಸ್ಯೆಯ ನಿರೂಪಣೆ ಹೀಗಿದೆ:
ಯಾವುದಾದರೊಂದು ಸ್ಥಳದಿಂದ ಹೊರಟು ಏಳು ಸೇತುವೆಗಳನ್ನೊ,ಪ್ರತಿಯೊಂದನ್ನು ಒಮ್ಮೆ ಮಾತ್ರ.ದಾಟಿ ಮತ್ತು ಅದೇ ಸ್ಥಳಕ್ಕೆ ತಿರುಗಿಬರುವ ಕ್ರಮ ಏನು? ಹಿಂದೆ ಹೇಳಿರುವಂತೆ ಆಯ್ಲರನ 1736 ರ ಸುಪ್ರಸಿದ್ಧ ನಾಂದೀ ಪ್ರಬಂಧ ಈ ಸಮಸ್ಯಯ ಪರಿಹಾರ.ಆಯ್ಲರನ ಉತ್ತರ ಬಲು ಸ್ವಾರಸ್ಯಕರವಾಗಿದೆ.ಇದನ್ನು ಚಿತ್ರ 5ರಲ್ಲಿ ಗ್ರಾಫ್ ರೊಪದಲ್ಲಿ ಬಿಡಿಸಿ ತೋರಿಸಿದೆ.
ಪಟ್ಟಣದ ನಾಲ್ಕು ಭಾಗಗಳನ್ನು A,B.C.D ಶೃಂಗಗಳಿಂದ ಗುರುತಿಸಲಾಗಿದೆ.; (ಚಿತ್ರ 4 ನ್ನು ಸಹ ನೋಡಬಹುದು); ಪಟ್ಟಣದ ಏಳು ಸೇತುವೆಗಳನ್ನು ಈ ಗ್ರಾಫಿನ ಏಳು ಅಂಚುಗಳಿಂದ ಗುರುತಿಸಲಾಗಿದೆ.ಅಂದರೆ ಚಿತ್ರ(4)ರಲ್ಲಿ ಸಮಸ್ಯಯನ್ನು ಚಿತ್ರ (5)ರಲ್ಲಿರುವ ಗ್ರಾಫ್ ಪ್ರತೀಕೀಕರಿಸುತ್ತದೆ.ಈ ಮೇಲಿನ ಸಮಸ್ಯಯನ್ನು ಚಿತ್ರ(4)ರಲ್ಲಿರುವ ಒಂದು ಗ್ರಾಫಿನ ಸಮಸ್ಯಯಾಗಿ ಹೀಗೆ ಹೇಳಬಹುದು.ಈ ಗ್ರಾಫಿನಲ್ಲಿ ಯಾವುದಾದರು ಒಂದು ಶೃಂಗದಿಂದ ಪ್ರಾರಂಭ ಮಾಡಿ, ಎಲ್ಲ ಅಂಚುಗಳನ್ನು ಒಮ್ಮೆ ಮಾತ್ರ ಹಾಯ್ದು ಮತ್ತೆ ಅದೇ ಶೃಂಗಕ್ಕೆ ಮರಳಿ ಬರುವುದು ಸಾಧ್ಯವೇ? ಇದು ಅಸಾಧ್ಯ ಎಂದು ಆಯ್ಲರ್ ಸಾಧಿಸಿದ್ದಾನೆ.ಈ ಸಾಧನೆಯ ವಿವರಣೆಯನ್ನು ಈಗ ನೋಡೋಣ.
ಆಯ್ಲರ್ ನ ಗ್ರಾಫುಗಳು:ಯಾವ ಗ್ರಾಫಿನಲ್ಲಿ ಯಾವುದೇ ಒಂದು ಶೃಂಗದಿಂದ ಹೊರಟು ಎಲ್ಲ ಆಂಚುಗಳನ್ನೊ ಒಮ್ಮೆ ಮಾತ್ರ ಹಾಯ್ದು ಮತ್ತೆ ಅದೇ ಶೃಂಗಕ್ಕೆ ಮರಳಿ ಬರುವುದು ಸಾಧ್ಯವೋ ಅಂಥ ಗ್ರಾಫ್ ಆಗಿರಬೇಕಾದರೆ ಬೇಕಾದ ಮತ್ತು ಸಾಕಾದ (ನೆಸಸರಿ ಅಂಡ್ ಸಫಿಷಿಯಂಟ್) ನಿರ್ಬಂಧಗಳನ್ನು ಆಯ್ಲರ್ ಈ ಕೆಳಗಿನ ಪ್ರಮೇಯದಲ್ಲಿ ಹೇಳಿದ್ದಾನೆ.
ಪ್ರಮೇಯ 3: ಒಂದು ಸಂಯೋಜಕ ಗ್ರಾಫಿನ ಪ್ರತಿಯೊಂದು ಶೃಂಗದ ಸ್ತರ ಒಂದು ಸಮಸಂಖ್ಯೆ ಆಗಿದ್ದರೆ ಮತ್ತು ಆಗಿದ್ದರೆ ಮಾತ್ರ ಆ ಗ್ರಾಫ್ ಆಯ್ಲರನ ಗ್ರಾಫ್ ಆಗುತ್ತದೆ.
ಈ ಪ್ರಮೇಯದ ಮೂಲದ ಚಿತ್ರ(5)ರಲ್ಲಿರುವ ಗ್ರಾಫ್ ಆಯ್ಲರನ ಗ್ರಾಫ್ ಅಲ್ಲ ಎಂದು ತಿಳಿದುಬರುತ್ತದೆ;ಮತ್ತು ಈ ಮೇಲಿನ ಸಮಸ್ಯಗೆ ಪರಿಹಾರ ದೊರೆಯುತ್ತದೆ.
ಹ್ಯಾಮಿಲ್ಟನ್ ಗ್ರಾಫುಗಳ:ಸುಪ್ರಸಿದ್ದ ಐರಿಷ್ ಗಣಿತಶಾಸ್ತ್ರಜ ವಿಲಿಯಮ್ ಹ್ಯಾಮಿಲ್ಟನ್ (1805-65) ಒಂದು ವಿಶೇಷವಾದ ಒಗಟನ್ನು 1859 ರಲ್ಲಿ ಬಹಿರಂಗಪಡಿಸಿದ.ಚಿತ್ರ(6)ರಲ್ಲಿನ ಗ್ರಾಫಿನಲ್ಲಿ 20 ಶೃಂಗಗಳಿವೆ.ಪ್ರತಿಯೊಂದು ಶೃಂಗವೊ ಪ್ರಪಂಚದ ಒಂದು ದೊಡ್ಡ ಪಟ್ಟಣವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ.ಈಗ ಸಮಾಸ್ಯೆ ಹೀಗಿದೆ:ಈ ಗ್ರಾಫಿನಲ್ಲಿ ಯಾವುದಾದರೂ ಒಂದು ಶೃಂಗದಿಂದ ಪ್ರಾರಂಭಮಾಡಿ ಪ್ರತಿಯೊಂದು ಶೃಂಗವನ್ನೂ ಒಂದೇ ಒಂದು ಸಲ ಹಾದು ಹೋಗುವ ಒಂದು ಚಕ್ರೀಯ ದಾರಿಯನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು.ಇಂಥ ಒಂದು ಚಕ್ರೀಯ ದಾರಿ ಇದ್ದರೆ ಅದಕ್ಕೆ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಗ್ರಾಫ್ ಎಂಬ ಹೆಸರುಂಟು.ಚಿತ್ರ(6)ರಲ್ಲಿರುವ ಗ್ರಾಫ್ ಒಂದು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಗ್ರಾಫ್ .ಕಾರಣ 1,2,3,.....20,1 ಇದರಲ್ಲಿ ಒಂದು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರ ಸಾಮಾನ್ಯವಾಗಿ ಒಂದು ದತ್ತ ಗ್ರಾಫ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಗ್ರಾಫ್ ಹೌದೇ ಅಲ್ಲವೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ಅಷ್ಟು ಸುಲಭವಲ್ಲ.
ಒಗಟುಗಳು ಮತ್ತು ಗ್ರಾಫುಗಳು: ಗ್ರಾಫ್ ಸಿದ್ಢಾಂತದ ಆರಂಭದ ದಿವಸಗಳಲ್ಲಿ ಒಗಟುಗಳು ಒಡಪು ಈ ಸಿದ್ಡಾಂತ ಒಂದು ಪ್ರಧಾನ ಅಂಗವೇ ಆಗಿತ್ತು.ಇಂದಿಹಗೂ ಒಗಟುಗಳು ಪರಿಶೀಲನೆ ಈ ಸಿದ್ಢಾಂತದ ಮೂಲಕ ನಡೆದಿದೆ.ಕೆಲವನ್ನು ಇಲ್ಲಿ ಬರೆದಿದೆ.
ಅಂಬಿಗನ ಒಗಟು: ಒಬ್ಬ ಅಂಬಿಗ (A) ತನ್ನೊಂದಿಗಿರುವ ಒಂದು ನಾಯಿ (B),ಒಂದು ಕುರಿ (C) ಮತ್ತು ಕೋಸುಗಡ್ಡೆ (D) ಇವನ್ನು ಹೊಳೆಯ ಒಂದು ದಡದಂದ ಇನ್ನೊಂದು ದಡಕ್ಕೆ ಸಾಗಿಸಬೇಕಾಗಿದೆ.ಅವನ ದೋಣಿ ಚಿಕ್ಕದು.
ಅದು ಅಂಬಿಗನೊಂದಿಗೆ ಒಂದು ಸಲಕ್ಕೆ ಒಂದು ವಸ್ತುವನ್ನು ಮಾತ್ರ ಒಯ್ಯಬಲ್ಲದ್ದಾಗಿದೆ.ಅಂಬಿಗನ ಸಮಸ್ಯ ಏನಂದರೆ ಅವನು ಮೊದಲು ಬುಟ್ಟಿಯನ್ನು ತೆಗದುಕೊಂಡು ಹೋದರೆ ಆಗ ಕುರಿಯನ್ನು ನಾಯಿ ಕಬಳಿಸಬಹುದು.ನಾಯಿಯನ್ನು ಒಯ್ದರೆ ಕೋಸುಗಡ್ಡೆಗಳನ್ನು ಕುದಿ ತಿನ್ನಬಹುದು.ಹಾಗಾದರೆ ಅವನು ನಾಯಿ,ಕುರಿ ಮತ್ತು ಬುಟ್ಟಿಗಳನ್ನು ಹೇಗೆ ಸುರಕ್ಷಿತವಾಗಿ ಸಾಗಿಸಬಹುದು? ಈ ಸಮಸ್ಯೆಗೆ ಎರಡು ವಿಧವಾದ ಉತ್ತರಗಳಿವೆ.ಮೊದಲನೆಯದಾಗಿ ಆಂಬಿಗೆ (A) ಕುರಿಯನ್ನು (C) ಒಯ್ಯಬಹುದು.ಆಗ ಮೊದಲನೆಯ ದಡದಲ್ಲಿ A,B,C,D ಗುಂಪು BD ಆಗುವುದು.ತರುವಾಯ A ಒಬ್ಬನೇ ಮರಳಿ ಬರುತ್ತಾನೆ.ಆಗ ಮತ್ತೆ BD ಗುಂಪು A,B,D ಆಗುವುದು.ಬಳಿಕ A ತನ್ನೊಂದಿಗೆ B ಅಥವಾ D ಯನ್ನು ಒಯ್ದು B ಅಥವ D ಯನ್ನು ಎದುರು ದಡದಲ್ಲಿ ಬಿಡಬಹುದು.ಆದರೆ ಯಾವುದನ್ನು ಅಲ್ಲಿ ಬಿಟ್ಟರೊ C ಯನ್ನು ಹಿಂದಕ್ಕೆ ಸಾಗಿಸಲೇಬೇಕು.ಮರಳಿ ಬಂದಾಗ ಮೊದಲನೆಯ ದಡದ ಗುಂಪಿನಲ್ಲಿ ಎರಡು ಸಾಧ್ಯತೆಗಳಿವೆ. ಒಂದು A,C,B ಅಥವ A,C,D.ಮುಂದಿನ ಸರದಿಯಲ್ಲಿ B ಅಥವ D ಯನ್ನು A ಒಯ್ಯುತ್ತಾನೆ.A ಮರಳಿಬಂದು C ಯನ್ನು ಒಯ್ಯುತ್ತಾನೆ.ಈ ಎಲ್ಲ ಸಾಧ್ಯತೆಗಳನ್ನೊ ಚಿತ್ರದಲ್ಲಿ ಕಾಣಿಸಿದೆ.
