ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ

ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಎನ್ನುವುದು ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ ಬರುವ ಒಂದು ಮುಖ್ಯ ಪರಿಕಲ್ಪನೆ. ವಿಭಿನ್ನ ಮತ್ತು ಮೇಲುನೋಟಕ್ಕೆ ಪರಸ್ಪರ ಸಾಮಾನ್ಯವಾದದ್ದು ಏನೂ ಇಲ್ಲವೆಂದು ತೋರುವಂಥ, ಅನೇಕ ಕ್ಷೇತ್ರಗಳಲ್ಲಿ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಅನ್ವಯ ಇರುವುದು ಅದರ ಆಧುನಿಕತೆಗೆ ಹೇಗೋ ಪುಟಿತತೆಗೂ ಹಾಗೇ ನಿದರ್ಶನ. ಅರ್ಥಶಾಸ್ತ್ರ, ಮನಶ್ಶಾಸ್ತ್ರ, ಜೀವವಿಜ್ಞಾನ, ಸಾಗಣೆಯ ಸಮಸ್ಯೆಗಳು, ವೈದ್ಯುತ ಸಂಪರ್ಕ ಎಂಜಿನಿಯರಿಂಗ್ ಇವೇ ಮುಂತಾದವು ಈ ವಿಭಿನ್ನ ಕ್ಷೇತ್ರಗಳು. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಮೂಲಪುರುಷ ಸ್ವಿಟ್ಜರ್ಲೆಂಡಿನ ಪ್ರಸಿದ್ಧ ಗಣಿತ ವಿಜ್ಞಾನಿ ಲಿಯೊನಾರ್ಡ್ ಆಯ್ಲರ್ (1707 - 1783). ಕ್ಯೋನಿಷ್‌ಬರ್ಗ್ ಸೇತುವೆಗಳ ಸಮಸ್ಯೆಯನ್ನು ಬಿಡಿಸುವ ಹಾದಿಯಲ್ಲಿ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಮೈದಳೆಯಿತು. (ಈ ಸಮಸ್ಯೆಯ ವಿವರವನ್ನು ಇದೇ ಲೇಖನದಲ್ಲಿ ಮುಂದೆ ಬರೆದಿದೆ.) ಇದನ್ನು ಕುರಿತ ಆತನ ಮೊದಲ ಪ್ರಬಂಧ 1736 ರಲ್ಲಿ ಪ್ರಕಟವಾಯಿತು. ಆದರೆ ಪ್ರಾರಂಭದ ದಿವಸಗಳಲ್ಲಿ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತವನ್ನು ಗಣಿತಶಾಸ್ತ್ರದ ಒಂದು ಅಂಗವೆಂದು ಯಾರೂ ಪರಿಗಣಿಸಿರಲಿಲ್ಲ. ಕಾರಣ, ಇದು ಅನೇಕ ಮನೋರಂಜಕ, ಚಮತ್ಕಾರಿಕ, ನಿಗೂಢ ಸಮಸ್ಯೆ ಹಾಗೂ ಒಗಟುಗಳನ್ನು ಬಿಡಿಸುವ ಸಾಧನವಾಗಿತ್ತು. ಆದರೆ ಈಚೆಗಿನ ವರ್ಷಗಳಲ್ಲಿ ಇತರ ಹಲವಾರು ಜ್ಞಾನವಿಭಾಗಗಳೊಡನೆ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತಕ್ಕೆ ಸಂಬಂಧವೇರ್ಪಟ್ಟು ಇದರ ಬೆಳೆವಣಿಗೆಗೆ ಅಸಾಧಾರಣವಾದ ಕುಮ್ಮಕ್ಕು ಲಭಿಸಿದೆ.

ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಬಳಸುವ ಪದ ಗ್ರಾಫ್‌ಗೂ (ಆಲೇಖ), ವಿಶ್ಲೇಷಣ ಜ್ಯಾಮಿತಿಯಲ್ಲಿ ಅರ್ಥವಿಸುವ ಅದೇ ಪದಕ್ಕೂ ಸಂಬಂಧವಿಲ್ಲ. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಗ್ರಾಫ್ ಎಂದರೆ ಕೇವಲ ಬಿಂದು ಮತ್ತು ರೇಖೆಗಳ ಸಮುದಾಯ ಹಾಗೂ ಅವುಗಳಿಂದ ಅನುಗತವಾಗುವ ಜ್ಯಾಮಿತೀಯ ಆಕೃತಿಗಳು ಮಾತ್ರ. ಹಾಗಿದ್ದರೂ ಐತಿಹಾಸಿಕ ಕಾರಣಗಳಿಂದ ಗ್ರಾಫ್ ಪದವೇ ಬಳಕೆಯಲ್ಲಿ ಉಳಿದುಕೊಂಡಿದೆ.

ಗ್ರಾಫ್ ಪದದ ಅರ್ಥವನ್ನು ಸ್ಪಷ್ಟಪಡಿಸಲು ಈ ಕೆಳಗಿನ ಉದಾಹರಣೆಯನ್ನು ಪರಿಶೀಲಿಸಬಹುದು. ಕಬಡ್ಡಿ ಆಟ ನಡೆಯುತ್ತಿದೆಯೆಂದು ಭಾವಿಸೋಣ. ಇದರಲ್ಲಿ A, B, C, D, E, F ಹಾಗೂ G ತಂಡಗಳು ಭಾಗವಹಿಸಿರಲಿ. ಪಂದ್ಯಗಳು ಪ್ರಾರಂಭವಾದ ಕೆಲವು ದಿವಸಗಳ ಬಳಿಕ ಈ ಕೆಳಗಿನ ಪರಿಸ್ಥಿತಿ ಇರಲಿ.

A ತಂಡ B ತಂಡದೊಂದಿಗೆ ಆಟವಾಡಿದೆ.

B ತಂಡ C, D, E ತಂಡಗಳೊಂದಿಗೆ ಆಟವಾಡಿದೆ.

C ತಂಡ B, D ತಂಡಗಳೊಂದಿಗೆ ಆಟವಾಡಿದೆ.

D ತಂಡ B, C, E, F ತಂಡಗಳೊಂದಿಗೆ ಆಟವಾಡಿದೆ.

E ತಂಡ A, D, F ತಂಡಗಳೊಂದಿಗೆ ಆಟವಾಡಿದೆ.

F ತಂಡ D, E ತಂಡಗಳೊಂದಿಗೆ ಆಟವಾಡಿದೆ.

G ತಂಡ ಯಾವ ತಂಡದೊಂದಿಗೂ ಆಟವಾಡಿಲ್ಲ.

ಈ ಸನ್ನಿವೇಶವನ್ನು ಚಿತ್ರದಲ್ಲಿ ಸೂಕ್ತ ರೇಖೆಗಳನ್ನು ಎಳೆದು ಕಾಣಿಸಬಹುದು.

೬ ತಂಡಗಳು ಆಡಿರುವ ಪಂದ್ಯಗಳ ಗ್ರಾಫ್

ಪಕ್ಕದಲ್ಲಿರುವ ಚಿತ್ರದಲ್ಲಿ ಆರು ತಂಡಗಳು ಆಡಿದ ಪಂದ್ಯಗಳನ್ನು ಗ್ರಾಫ್‍ನಲ್ಲಿ ತೋರಿಸಲಾಗಿದೆ.

ಎರಡು ತಂಡಗಳನ್ನು ಕೂಡಿಸುವ ಒಂದು ರೇಖೆ ಅವೆರಡೂ ಪರಸ್ಪರ ಆಟವಾಡಿದೆ ಎಂಬುದನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಉದಾಹರಣೆಗೆ 1 ತಂಡ 2 ತಂಡದೊಂದಿಗೆ, 5 ತಂಡ 3, 4, 6 ತಂಡದೊಂದಿಗೆ ಆಟವಾಡಿದೆ ಎಂದೂ ಚಿತ್ರದಿಂದ ಸ್ಪಷ್ಟವಾಗಿ ತಿಳಿಯಬಹುದು.

ಇಂಥ ಆಕೃತಿಯೇ ಇಲ್ಲಿ ಬಳಸುವ ಗ್ರಾಫ್. ಇದು ಕೆಲವು ಬಿಂದುಗಳು ಮತ್ತು ಅವನ್ನು ಕೂಡಿಸುವ ರೇಖೆಗಳ ಸಮುದಾಯ ಎಂಬುದು ಸ್ಪಷ್ಟ. ಪಕ್ಕದ ಆಕೃತಿಯಲ್ಲಿ 1, 2, 3, 4, 5, 6 ಗಳಿಗೆ ಗ್ರಾಫಿನ ಶೃಂಗಗಳೆಂದೂ, 1-4, 1-2, 4-5, 2-3, 3-5, 5-6 ಗಳಿಗೆ ಗ್ರಾಫಿನ ಅಂಚುಗಳೆಂದು (edges) ಹೆಸರು. ಗ್ರಾಫಿನ ಅಂಚುಗಳು ಸರಳವಾಗಿರಬೇಕೆಂದಿಲ್ಲ. ಅವು ವಕ್ರರೇಖೆಗಳೂ ಆಗಿರಬಹುದು. ಇಲ್ಲಿ ಕಾಣುವ ವೈಶಿಷ್ಟ್ಯವೆಂದರೆ ಎರಡು ಅಂಚುಗಳು ಒಂದನ್ನೊಂದು ಒಂದು ಬಿಂದುವಿನಲ್ಲಿ ಛೇದಿಸಬಹುದು. ಆದರೆ ಅಂಥ ಛೇದಕ ಬಿಂದು ಶೃಂಗವಲ್ಲ. 1-2 ಅಂಚಿನ 1 ಮತ್ತು 2 ಬಿಂದುಗಳಿಗೆ ಆ ಅಂಚಿನ ಕೊನೆ ಶೃಂಗಗಳು (ಎಂಡ್ ವರ್ಟಿಸಸ್) ಎಂದೂ, 1-2 ಅಂಚು 1 ಬಿಂದುವಿನಲ್ಲಿ ಸಂಲಗ್ನವಾದರೆ (ಇನ್ಸಿಡೆಂಟ್) ಎಂದೂ, 1-2 ಅಂಚು 1 ಬಿಂದುವಿನಲ್ಲಿ ಸಂಲಗ್ನವಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತೇವೆ. ಒಂದು ಶೃಂಗದಲ್ಲಿ ಸಂಲಗ್ನವಾಗಿರುವ ಅಂಚುಗಳ ಸಂಖ್ಯೆಗೆ ಆ ಶೃಂಗದ ಸ್ತರ (ಡಿಗ್ರಿ) ಒಂದು ಶೃಂಗದ ಸ್ತರ ಶೂನ್ಯವಾಗಿದ್ದರೆ ಅದಕ್ಕೆ ಏಕಾಂತ (ಐಸೋಲೇಟೆಡ್) ಶೃಂಗ ಎಂದು ಹೆಸರು. ಮೇಲಿನ ಚಿತ್ರದಲ್ಲಿ ಯಾವ ಏಕಾಂತ ಶೃಂಗವೂ ಇಲ್ಲ.

ಶೂನ್ಯ ಗ್ರಾಫುಗಳು ಮತ್ತು ಪರಿಪೂರ್ಣ ಗ್ರಾಫುಗಳು (ನಲ್ ಗ್ರಾಫ್ಸ್ ಅಂಡ್ ಕಂಪ್ಲೀಟ್ ಗ್ರಾಫ್ಸ್)

ಪರಿಪೂರ್ಣ ಗ್ರಾಫ್

ಅಂಚುಗಳಿಲ್ಲದ ಗ್ರಾಫಿಗೆ ಅಂದರೆ ಗ್ರಾಫಿನ ಪ್ರತಿಯೊಂದು ಶೃಂಗವೂ ಏಕಾಂತ ಶೃಂಗವಾಗಿರುವ ಗ್ರಾಫಿಗೆ ಶೂನ್ಯ ಗ್ರಾಫ್ ಎಂದು ಹೆಸರು. ಹೀಗಲ್ಲದೆ ಪ್ರತಿ ಒಂದು ಜೊತೆ ಶೃಂಗಗಳನ್ನೂ ಕೂಡಿಸುವ ಅಂಚುಗಳಿರುವ ಗ್ರಾಫ್‌ಗೆ ಪರಿಪೂರ್ಣ ಗ್ರಾಫ್ ಎಂದು ಹೆಸರು. ಚಿತ್ರದಲ್ಲಿ 1, 2, 3, 4 ಮತ್ತು 5 ಶೃಂಗಗಳಿರುವ ಪರಿಪೂರ್ಣ ಗ್ರಾಫನ್ನು ಕಾಣಿಸಿದೆ.

ಗ್ರಾಫಿನಲ್ಲಿರುವ ಅಂಚುಗಳ ಸಂಖ್ಯೆ

V₁, V₂, ,..........., V_n ಗಳು ಒಂದು ಗ್ರಾಫಿನ ಶೃಂಗಗಳಾಗಿರಲಿ; ಮತ್ತು V_i ಬಿಂದುವಿನ ಸ್ತರ d_i ಆಗಿರಲಿ. ಇಲ್ಲಿ i = 1, 2 ........, n. ಈಗ

d₁ + d₂ + ...... + d_n ....................…(1)

ಮೊತ್ತವನ್ನು ಪರಿಶೀಲಿಸೋಣ. ಇದರಲ್ಲಿ ಗ್ರಾಫಿನ ಪ್ರತಿಯೊಂದು ಅಂಚಿನ ಎಣಿಕೆ ಎರಡು ಸಲವಾಗಿರುತ್ತದೆ. (ಆ ಅಂಚಿನ ಪ್ರತಿಯೊಂದು ಕೊನೆ ಶೃಂಗದಲ್ಲಿ ಒಂದೊಂದು ಸಲ). ಹೀಗೆ ಪ್ರತಿಯೊಂದು ಅಂಚು ಕೂಡ ಎರಡು ಸಲ ಎಣಿಕೆಗೆ ಬರುವುದರಿಂದ

d₁ + d₂ + ...... + d_n = 2q .....................…(2)

ಆಗುತ್ತದೆ. ಇಲ್ಲಿ q ಗ್ರಾಫಿನಲ್ಲಿರುವ ಅಂಚುಗಳು ಒಟ್ಟು ಸಂಖ್ಯೆ.

ಪ್ರಮೇಯಗಳು

ಈ ಕೆಳಗಿನದು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಮೊದಲನೆಯ ಪ್ರಮೇಯ.

ಪ್ರಮೇಯ 1: ಒಂದು ಗ್ರಾಫಿನ ಎಲ್ಲ ಶೃಂಗಗಳ ಸ್ತರಗಳ ಮೊತ್ತ ಆ ಗ್ರಾಫಿನಲ್ಲಿರುವ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯ ಎರಡರಷ್ಟು.

ಈಗ ಸಮೀಕರಣ (2) ರ ಎಡದಲ್ಲಿರುವ ಎಲ್ಲ ಸಮ (ಈವನ್) ಸ್ತರಗಳನ್ನು ತೆಗೆದರೆ ಉಳಿಯುವ ಎಲ್ಲ ವಿಷಮ ಸ್ತರಗಳ ಮೊತ್ತ ಸಮ ಸಂಖ್ಯೆ ಆಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ (2) ರಲ್ಲಿ ವಿಷಮ ಸ್ತರಗಳ ಸಂಖ್ಯೆ ಒಂದು ಸಮ ಸಂಖ್ಯೆಯಾಗಿರುತ್ತದೆ.

ಪ್ರಮೇಯ 2: ಒಂದು ಗ್ರಾಫಿನಲ್ಲಿ ವಿಷಮ ಸ್ತರದ ಶೃಂಗಗಳ ಸಂಖ್ಯೆ ಸಮ.

ಸಂಯೋಜಿತ ಗ್ರಾಫುಗಳು (ಕನೆಕ್ಟಡ್ ಗ್ರಾಫ್ಸ್)

ಒಂದು ಗ್ರಾಫಿನ ಶೃಂಗಗಳು V₁, V₂, ..........., V_n ಆಗಿರಲಿ. ಪ್ರತಿಯೊಂದು i = 1, 2 ........, n -1 ಸಂಖ್ಯೆಗೂ V_i-V_{i +1} ಒಂದು ಅಂಚು ಆಗಿರಲಿ. ಆಗ V₁, V₂, ..........., V_n ಗೆ V₁ - V_n ನಡೆ (ವಾಕ್) ಎಂದು ಹೆಸರು. ಇಂಥ ಒಂದು ನಡೆಯಲ್ಲಿ ಕೆಲವೊಂದು ಬಿಂದುಗಳು ಮತ್ತು ಅಂಚುಗಳು ಒಂದೇ ಆಗಿರಬಹುದು.

ಚಿತ್ರ ೪

ಒಂದು ನಡೆಯಲ್ಲಿ ಎಲ್ಲ ಅಂಚುಗಳು ಭಿನ್ನವಾಗಿದ್ದರೆ ಅದಕ್ಕೆ ತುಣುಕು ನಡೆ (ಟ್ರೇಲ್) ಎಂದು ಹೆಸರು. ಒಂದು ನಡೆಯಲ್ಲಿ ಎಲ್ಲ ಬಿಂದುಗಳೂ, ಅಂಚುಗಳೂ ಭಿನ್ನವಾಗಿದ್ದರೆ ಅದಕ್ಕೆ ದಾರಿ (ಪಾತ್) ಎಂದು ಹೆಸರು. V₁, V₂, ..........., V_n ದಾರಿಯಲ್ಲಿ V₁ = V_n ಆಗಿದ್ದರೆ ಅದಕ್ಕೆ ಒಂದು ಚಕ್ರ (ಸೈಕಲ್) ಎಂದು ಹೆಸರು. ಉದಾಹರಣೆಗೆ ಪಕ್ಕದ ಚಿತ್ರದಲ್ಲಿ A, B, C, B, E ಒಂದು A - E ನಡೆ. ಇದು ತುಣುಕು ನಡೆ ಅಲ್ಲ. A, B, E ಆದರೂ A - E ತುಣುಕು ನಡೆ; ಇದು ಒಂದು ದಾರಿ ಕೂಡ ಆಗಿದೆ. ಈಗ A, B, E, F ಎಂಬುದು A - F ದಾರಿ ಮತ್ತು ಚಿತ್ರ ೪ ರಲ್ಲಿ A, B, D, G, H, A ಒಂದು ಚಕ್ರ. ಈಗ A, B, D, F, E, C ಎಂಬುದು A - C ದಾರಿ ಮತ್ತು A, B, C, E, F, G, H, A ಒಂದು ಚಕ್ರ.

ಒಂದು ಗ್ರಾಫಿನಲ್ಲಿ ಪ್ರತಿ ಒಂದು ಜೊತೆ ಶೃಂಗಗಳಿಗೂ, ಅವನ್ನು ಸೇರಿಸುವ ಒಂದು ದಾರಿ ಇದ್ದರೆ ಆ ಗ್ರಾಫಿಗೆ ಸಂಯೋಜಿತ ಗ್ರಾಫ್ ಎಂದು ಹೆಸರು.

ಕ್ಯೋನಿಷ್‌ಬರ್ಗ್ ಸೇತುವೆಗಳ ಸಮಸ್ಯೆ

ಚಿತ್ರ ೪ ಬಿ

ಚಿತ್ರ ೫

ಪ್ರಸ್ತುತ ಕ್ಯಾಲಿನಿನ್‌ಗ್ರ್ಯಾಡ್ ಎಂದು ಹೆಸರಿರುವ ಕ್ಯೋನಿಷಬರ್ಗ್ ಪೂರ್ವ ಪ್ರಷ್ಯದಲ್ಲಿನ ಒಂದು ನಗರ. ಇದು ನಡುಗಡ್ಡೆಗಳನ್ನೊಳಗೊಂಡಿರುವ ಪ್ರೆಗಲ್ ಎಂಬ ಹೆಸರಿನ ನದಿಯ ದಂಡೆಯಲ್ಲಿದೆ. ಈ ಪಟ್ಟಣದ ನಡುಗಡ್ಡೆಗಳನ್ನೂ, ಉಳಿದ ಭಾಗಗಳನ್ನೂ ಪಕ್ಕದ ಚಿತ್ರದಲ್ಲಿ ತೋರಿಸಿರುವಂತೆ P, Q, R, S, T, U, V ಎಂಬ ಏಳು ಸೇತುವೆಗಳಿಂದ ಜೋಡಿಸಲಾಗದೆ. ಕ್ಯೋನಿಷ್‌ಬರ್ಗ್ ಸೇತುವೆಗಳ ಸಮಸ್ಯೆಯ ನಿರೂಪಣೆ ಹೀಗಿದೆ:

ಯಾವುದಾದರೊಂದು ಸ್ಥಳದಿಂದ ಹೊರಟು ಏಳು ಸೇತವೆಗಳನ್ನೂ, ಪ್ರತಿಯೊಂದನ್ನೂ ಒಮ್ಮೆ ಮಾತ್ರ, ದಾಟಿ ಮತ್ತೆ ಅದೇ ಸ್ಥಳಕ್ಕೆ ತಿರುಬರುವ ಕ್ರಮ ಏನು? ಹಿಂದೆ ಹೇಳಿರುವಂತೆ ಆಯ್ಲರ್‌ನ 1736 ರ ಸುಪ್ರಸಿದ್ಧ ನಾಂದೀ ಪ್ರಬಂಧ ಈ ಸಮಸ್ಯೆಯ ಪರಿಹಾರ. ಆಯ್ಲರನ ಉತ್ತರ ಬಲು ಸ್ವಾರಸ್ಯಕರವಾಗಿದೆ. ಇದನ್ನು ಚಿತ್ರ ೫ ರಲ್ಲಿ ಗ್ರಾಫ್ ರೂಪದಲ್ಲಿ ಬಿಡಿಸಿ ತೋರಿಸಿದೆ.

ಪಟ್ಟಣದ ನಾಲ್ಕು ಭಾಗಗಳನ್ನು A, B, C, D ಶೃಂಗಗಳಿಂದ ಗುರುತಿಸಬಹುದು; ಪಟ್ಟಣದ ಏಳು ಸೇತುವೆಗಳನ್ನು ಈ ಗ್ರಾಫಿನ ಏಳು ಅಂಚುಗಳಿಂದ ಗುರುತಿಸಬಹುದು. ಅಂದರೆ ಚಿತ್ರ ೪ ಬಿ ಯಲ್ಲಿನ ಸಮಸ್ಯೆಯನ್ನು ಚಿತ್ರ ೫ ರಲ್ಲಿರುವ ಗ್ರಾಫ್ ಪ್ರತೀಕೀಕರಿಸುತ್ತದೆ. ಈ ಮೇಲಿನ ಸಮಸ್ಯೆಯನ್ನು ಚಿತ್ರ ೫ ರಲ್ಲಿರುವ ಒಂದು ಗ್ರಾಫಿನ ಸಮಸ್ಯೆಯಾಗಿ ಹೀಗೆ ಹೇಳಬಹುದು. ಈ ಗ್ರಾಫಿನಲ್ಲಿ ಯಾವುದಾದರೂ ಒಂದು ಶೃಂಗದಿಂದ ಪ್ರಾರಂಭ ಮಾಡಿ, ಎಲ್ಲ ಅಂಚುಗಳನ್ನು ಒಮ್ಮೆ ಮಾತ್ರ ಹಾಯ್ದು ಮತ್ತೆ ಅದೇ ಶೃಂಗಕ್ಕೆ ಮರಳಿ ಬರುವುದು ಸಾಧ್ಯವೇ? ಇದು ಅಸಾಧ್ಯ ಎಂದು ಆಯ್ಲರ್ ಸಾಧಿಸಿದ್ದಾನೆ. ಈ ಸಾಧನೆಯ ವಿವರಣೆಯನ್ನು ಈಗ ನೋಡೋಣ.

ಆಯ್ಲರ್‌ನ ಗ್ರಾಫುಗಳು

ಯಾವ ಗ್ರಾಫಿನಲ್ಲಿ ಯಾವುದೇ ಒಂದು ಶೃಂಗದಿಂದ ಹೊರಟು ಎಲ್ಲ ಅಂಚುಗಳನ್ನೂ ಒಮ್ಮೆ ಮಾತ್ರ ಹಾಯ್ದು ಮತ್ತೆ ಅದೇ ಶೃಂಗಕ್ಕೆ ಮರಳಿ ಬರುವುದು ಸಾಧ್ಯವೋ ಅಂಥ ಗ್ರಾಫಿಗೆ ಆಯ್ಲರನ ಗ್ರಾಫ್ ಎಂದು ಹೆಸರು. ಒಂದು ಗ್ರಾಫ್ ಆಯ್ಲರನ ಗ್ರಾಫ್ ಆಗಿರಬೇಕಾದರೆ ಬೇಕಾದ ಮತ್ತು ಸಾಕಾದ (ನೆಸಸರಿ ಅಂಡ್ ಸಫಿಶಿಯಂಟ್) ನಿರ್ಬಂಧಗಳನ್ನು ಆಯ್ಲರ್ ಈ ಕೆಳಗಿನ ಪ್ರಮೇಯದಲ್ಲಿ ಹೇಳಿದ್ದಾನೆ.

ಪ್ರಮೇಯ 3: ಒಂದು ಸಂಯೋಜಕ ಗ್ರಾಫಿನ ಪ್ರತಿಯೊಂದು ಶೃಂಗದ ಸ್ತರ ಒಂದು ಸಮಸಂಖ್ಯೆ ಆಗಿದ್ದರೆ ಮತ್ತು ಆಗಿದ್ದರೆ ಮಾತ್ರ ಆ ಗ್ರಾಫ್ ಆಯ್ಲರನ ಗ್ರಾಫ್ ಆಗುತ್ತದೆ.

ಈ ಪ್ರಮೇಯದ ಮೂಲಕ ಚಿತ್ರ ೫ ರಲ್ಲಿರುವ ಗ್ರಾಫ್ ಒಂದು ಆಯ್ಲರ್‌ನ ಗ್ರಾಫ್ ಅಲ್ಲ ಎಂದು ತಿಳಿದುಬರುತ್ತದೆ; ಮತ್ತು ಈ ಮೇಲಿನ ಸಮಸ್ಯೆಗೆ ಪರಿಹಾರ ದೊರೆಯುತ್ತದೆ.

ಹ್ಯಾಮಿಲ್ಟನ್ ಗ್ರಾಫುಗಳು

ಸುಪ್ರಸಿದ್ಧ ಐರಿಷ್ ಗಣಿತಶಾಸ್ತ್ರಜ್ಞ ವಿಲಿಯಮ್ ಹ್ಯಾಮಿಲ್ಟನ್ (1805-1865) ಒಂದು ವಿಶೇಷವಾದ ಒಗಟನ್ನು 1859 ರಲ್ಲಿ ಬಹಿರಂಗಪಡಿಸಿದ. ಚಿತ್ರದಲ್ಲಿನ ಗ್ರಾಫಿನಲ್ಲಿ 20 ಶೃಂಗಗಳಿವೆ. ಪ್ರತಿಯೊಂದು ಶೃಂಗವೂ ಪ್ರಪಂಚದ ಒಂದು ದೊಡ್ಡ ಪಟ್ಟಣವನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಈಗ ಸಮಸ್ಯೆ ಹೀಗಿವೆ: ಈ ಗ್ರಾಫಿನಲ್ಲಿ ಯಾವುದಾದರೂ ಒಂದು ಶೃಂಗದಿಂದ ಪ್ರಾರಂಭಮಾಡಿ ಪ್ರತಿಯೊಂದು ಶೃಂಗವನ್ನೂ ಒಂದೇ ಒಂದು ಸಲ ಹಾದು ಹೋಗುವ ಒಂದು ಚಕ್ರೀಯ ದಾರಿಯನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು. ಇಂಥ ಒಂದು ಚಕ್ರೀಯ ದಾರಿ ಇದ್ದರೆ ಅದಕ್ಕೆ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಗ್ರಾಫ್ ಎಂಬ ಹೆಸರುಂಟು. ಚಿತ್ರದಲ್ಲಿರುವ ಗ್ರಾಫ್ ಒಂದ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಗ್ರಾಫ್ ಕಾರಣ 1, 2, 3, ..... 20, 1 ಇದರಲ್ಲಿ ಒಂದು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಚಕ್ರ. ಸಾಮಾನ್ಯವಾಗಿ ಒಂದು ದತ್ತ ಗ್ರಾಫ್ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಗ್ರಾಫ್ ಹೌದೇ ಅಲ್ಲವೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ಅಷ್ಟು ಸುಲಭವಲ್ಲ.

ಒಗಟುಗಳು ಮತ್ತು ಗ್ರಾಫುಗಳು

ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಆರಂಭದ ದಿವಸಗಳಲ್ಲಿ ಒಗಟುಗಳು ಒಡಪು ಈ ಸಿದ್ಧಾಂತದ ಒಂದು ಪ್ರಧಾನ ಅಂಗವೇ ಆಗಿತ್ತು. ಇಂದಿಗೂ ಒಗಟುಗಳ ಪರಿಶೀಲನೆ ಈ ಸಿದ್ಧಾಂತದ ಮೂಲಕ ನಡೆದಿದೆ. ಕೆಲವನ್ನು ಇಲ್ಲಿ ಬರೆದಿದೆ.

ಅಂಬಿಗನ ಒಗಟು

ನಾಯಿ, ಕುರಿ, ಮತ್ತು ಕೋಸುಗಡ್ಡೆ

ಒಬ್ಬ ಅಂಬಿಗ (A) ತನ್ನೊಂದಿಗಿರುವ ಒಂದು ನಾಯಿ (B), ಒಂದು ಕುರಿ (C) ಮತ್ತು ಕೋಸುಗಡ್ಡೆ (D) ಇವನ್ನು ಹೊಳೆಯ ಒಂದು ದಡದಿಂದ ಇನ್ನೊಂದು ದಡಕ್ಕೆ ಸಾಗಿಸಬೇಕಾಗಿದೆ. ಅವನ ದೋಣಿ ಚಿಕ್ಕದು.

ಆದ್ದರಿಂದ ಅಂಬಿಗನು ಒಂದು ಸಲಕ್ಕೆ ಒಂದು ವಸ್ತುವನ್ನು ಮಾತ್ರ ಒಯ್ಯಬಲ್ಲದ್ದಾಗಿದೆ. ಅಂಬಿಗನ ಸಮಸ್ಯೆ ಏನೆಂದರೆ ಅವನು ಮೊದಲು ಬುಟ್ಟಿಯನ್ನು ತೆಗೆದುಕೊಂಡು ಹೋದರೆ ಆಗ ಕುರಿಯನ್ನು ನಾಯಿ ಕಬಳಿಸಬಹುದು. ನಾಯಿಯನ್ನು ಒಯ್ದರೆ ಕೋಸುಗಡ್ಡೆಗಳನ್ನು ಕುರಿ ತಿನ್ನಬಹುದು. ಹಾಗಾದರೆ ಅವನು ನಾಯಿ, ಕುರಿ ಮತ್ತು ಬುಟ್ಟಿಗಳನ್ನು ಹೇಗೆ ಸುರಕ್ಷಿತವಾಗಿ ಸಾಗಿಸಬಹುದು. ಈ ಸಮಸ್ಯೆಗೆ ಎರಡು ವಿಧವಾದ ಉತ್ತರಗಳಿವೆ. ಮೊದಲನೆಯದಾಗಿ ಅಂಬಿಗ (A) ಕುರಿಯನ್ನು (C) ಒಯ್ಯಬಹುದು. ಆಗ ಮೊದಲನೆಯ ದಡದಲ್ಲಿ A, B, C, D ಗುಂಪು B, D ಆಗುವುದು. ತರುವಾಯ A ಒಬ್ಬನೇ ಮರಳಿ ಬರುತ್ತಾನೆ. ಆಗ ಮತ್ತೆ B, D ಗುಂಪು A, B, D ಆಗುವುದು. ಬಳಿಕ A, ತನ್ನೊಂದಿಗೆ B ಅಥವಾ D ಯನ್ನು ಒಯ್ದು B ಅಥವಾ D ಯನ್ನು ಎದುರು ದಡದಲ್ಲಿ ಬಿಡಬಹುದು. ಆದರೆ ಯಾವುದನ್ನು ಅಲ್ಲಿ ಬಿಟ್ಟರೂ C ಯನ್ನು ಹಿಂದಕ್ಕೆ ಸಾಗಿಸಲೇಬೇಕು. ಮರಳಿ ಬಂದಾಗ ಮೊದಲನೆಯ ದಡದ ಗುಂಪಿನಲ್ಲಿ ಎರಡು ಸಾಧ್ಯತೆಗಳಿವೆ. ಒಂದು A, C, B ಅಥವಾ A, C, D. ಮುಂದಿನ ಸರದಿಯಲ್ಲಿ B ಅಥವಾ D ಯನ್ನು A ಒಯ್ಯುತ್ತಾನೆ. A ಮರಳಿಬಂದು C ಯನ್ನು ಒಯ್ಯುತ್ತಾನೆ. ಈ ಎಲ್ಲ ಸಾಧ್ಯತೆಗಳನ್ನೂ ಚಿತ್ರದಲ್ಲಿ ಕಾಣಿಸಬಹುದು.

ಮೂವರು ಹೊಟ್ಟೆಕಿಚ್ಚಿನ ಗಂಡಂದಿರ ಪೇಚು

ಮೂರು ಗಂಡ ಹೆಂಡಂದಿರ ಜೋಡಿಗಳು ತಮ್ಮ ಪ್ರವಾಸದಲ್ಲಿ ಒಂದು ನದಿಯನ್ನು ದಾಟುವ ಪ್ರಸಂಗ ಬರುತ್ತದೆ. ಅಲ್ಲಿ ಇದ್ದ ಸಣ್ಣ ನಾವೆ ಒಂದು ಸಲಕ್ಕೆ ಇಬ್ಬರನ್ನು ಮಾತ್ರ ಒಯ್ಯಬಲ್ಲದು. ಪ್ರತಿಯೊಂದು ವ್ಯಕ್ತಿಗೂ ದೋಣಿ ನಡೆಸಲು ಬರುತ್ತದೆ. ಎಲ್ಲ ಗಂಡಂದಿರೂ ಬಲು ಹೊಟ್ಟೆಕಿಚ್ಚಿನವರು ಮತ್ತು ಸಂಶಯಪ್ರಕೃತಿಯವರು. ತಾವಿಲ್ಲದಿರುವಾಗ ತಮ್ಮ ಹೆಂಡಂದಿರನ್ನು ಪರಪುರುಷ ಇರುವಲ್ಲಿ ಬಿಡಲು ಒಲ್ಲದವರು. ಹಾಗಾದರೆ ಆ ದಂಪತಿಗಳು ನದಿಯನ್ನು ಹೇಗೆ ದಾಟುತ್ತಾರೆ? ಈ ಸಮಸ್ಯೆಗೆ ಯುಕ್ತ ಪರಿಹಾರವನ್ನು ಗ್ರಾಫಿನ ಮೂಲಕ ಪಡೆಯಬಹುದು.

ಆಟಗಳು ಮತ್ತು ಗ್ರಾಫುಗಳು

ಈ ಮೊದಲೇ ಹೇಳಿರುವಂತೆ ಗ್ರಾಫುಗಳನ್ನು ಆಟಗಳಿಗೂ ಸಂಯೋಜಿಸಲಾಗಿದೆ; ಹೀಗೆ ಮಾಡುವಾಗ ಸಾಮಾನ್ಯವಾಗಿ ಗ್ರಾಫಿನ ಶೃಂಗಗಳು ಆಟದಲ್ಲಿಯ ಸ್ಥಾನಗಳನ್ನು ಗುರುತಿಸುತ್ತವೆ; ಮತ್ತು ಅಂಚುಗಳು ಆಟದಲ್ಲಿಯ ನಿಯಮಗಳಿಗೆ ಅನುಸಾರವಾದ ಚಲನಗಳನ್ನು ಗುರುತಿಸುತ್ತದೆ. ಒಂದು ಸ್ಥಾನದಿಂದ ಮತ್ತೊಂದು ನಿರ್ದಿಷ್ಟ ಸ್ಥಾನಕ್ಕೆ ಹೋಗಲು ಸಾಧ್ಯವೇ ಎಂಬುದು ಆಟಗಳಲ್ಲಿನ ಒಂದು ಸಾಮಾನ್ಯ ಸಮಸ್ಯೆ. ಈ ಸಮಸ್ಯೆಯನ್ನು ಗ್ರಾಫಿನ ಭಾಷೆಯಲ್ಲಿ ಹೀಗೆನ್ನಬಹುದು; ಆಟವನ್ನು ಗ್ರಾಫಿನ ಮೂಲಕ ನಿರೂಪಿಸಿದಾಗ ಎರಡು ದತ್ತ ಶೃಂಗಗಳು ಗ್ರಾಫಿನ ಒಂದೇ ಸಂಯೋಜಿತ ಫಟಕದಲ್ಲಿ (ಕನೆಕ್ಟೆಡ್ ಕಾಂಪೊನೆಂಟ್) ಇರುತ್ತವೆಯೊ ಅಥವಾ ಇಲ್ಲವೊ ಎಂಬುದನ್ನು ಕಂಡುಹಿಡಿಯುವಿಕೆ. ಉದಾಹರಣೆಗಾಗಿ ಚದುರಂಗದ ಆಟವನ್ನು ತೆಗೆದುಕೊಳ್ಳೋಣ. ಇದರಲ್ಲಿರುವ 64 ಚೌಕಗಳನ್ನು 64 ಶೃಂಗಗಳಿಂದ ಗುರುತಿಸೋಣ. ಈ ಆಟದಲ್ಲಿ ಮಂತ್ರಿಯ ನಡೆಯನ್ನು ಗಮನಿಸೋಣ. ಇದು ಅಷ್ಟೊಂದು ಕಠಿಣವಾಗಲಾರದು. ಕಾರಣ ಮಂತ್ರಿ ಒಂದು ಚೌಕದಿಂದ ಮತ್ತೊಂದು ಯಾವ ಚೌಕಕ್ಕಾದರೂ ಹೋಗಬಲ್ಲವನಾಗಿದ್ದಾನೆ. ಈ 64 ಶೃಂಗಗಳ ಮೇಲೆ ಮಂತ್ರಿಯ ನಡೆಯನ್ನು ನಿರೂಪಿಸುವ ಗ್ರಾಫನ್ನು ಎಳೆಯೋಣ. ಗ್ರಾಫಿನಲ್ಲಿ ಮಂತ್ರಿ ಒಂದು ಶೃಂಗದಿಂದ ಮತ್ತೊಂದು ಶೃಂಗಕ್ಕೆ ಒಂದು ನಡೆಯಲ್ಲಿ ಹೋಗುವುದಕ್ಕಾದರೆ ಅವೆರಡು ಬಿಂದುಗಳನ್ನು ಒಂದು ಅಂಚಿನಿಂದ ಸೇರಿಸುತ್ತೇವೆ. ಮಂತ್ರಿ ಒಂದು ಚೌಕದಿಂದ ಹೊರಟು ಪ್ರತಿಯೊಂದು ಚೌಕಕ್ಕೂ ಒಮ್ಮೆ ಮಾತ್ರ ಹೋಗಿ 64 ಚೌಕಗಳನ್ನೂ ಸುತ್ತಿ ತನ್ನ ಮೊದಲಿನ ಸ್ಥಾನಕ್ಕೆ ಬರಬಹುದೇ ಎಂಬುದು ಇಲ್ಲಿನ ಒಂದು ಸುಪ್ರಸಿದ್ಧ ಸಮಸ್ಯೆ. ಇದನ್ನೇ ಗ್ರಾಫಿನ ಒಂದು ಸಮಸ್ಯೆಯನ್ನಾಗಿ ಹೀಗೆ ಹೇಳಬಹುದು: ಈ ಆಟದ ಒಂದು ಗ್ರಾಫಿನಲ್ಲಿ ಹ್ಯಾಮಿಲ್ಟನ್ನಿನ ಒಂದು ಚಕ್ರವಿದೆಯೇ? ಇದಕ್ಕೆ ಅನೇಕ ಉತ್ತರಗಳಿವೆ.

63 22 15 40 1 42 58 18

14 39 64 21 60 17 2 43

37 62 23 16 41 4 19 58

24 13 36 61 20 57 44 3

11 36 25 52 29 46 5 56

26 51 12 33 8 55 30 45

35 10 49 28 53 32 47 6

50 27 34 9 48 7 54 31

ಚಿತ್ರ ೯

ವೃಕ್ಷ: ಚಕ್ರಗಳಿಲ್ಲದ ಸಂಯೋಜಕ ಗ್ರಾಫಿಗೆ ವೃಕ್ಷ (ಟ್ರೀ) ಎಂದು ಹೆಸರು. ಉದಾಹರಣೆಗೆ ಚಿತ್ರ ೯ ನ್ನು ನೋಡಬಹುದು. ಇಂಥ ಒಂದು ವೃಕ್ಷದಲ್ಲಿ v ಶೃಂಗಗಳೂ e ಅಂಚುಗಳೂ ಇದ್ದರೆ ಅವುಗಳ ನಡುವೆ v = e + 1 ಎಂಬ ಸುಲಭ ಸಂಬಂಧವಿರುವುದು ಕಾಣುತ್ತದೆ.

ಸಾಮ್ಯಗಳು (ಮ್ಯಾಚಿಂಗ್ಸ್), ಉದ್ಯೋಗಾವಕಾಶಗಳು ಮತ್ತು ಅಭ್ಯರ್ಥಿಗಳು: ಒಂದು ಕಾರ್ಖಾನೆಯಲ್ಲಿ ಕೆಲವು ಖಾಲಿ ಹುದ್ದೆಗಳು ಮತ್ತು ಅವಕ್ಕೆ ಕೆಲವು ಅಭ್ಯರ್ಥಿಗಳು ಇರಲಿ. ಆಗ ಈ ಕೆಳಗಿನ ಸಮಸ್ಯೆ ಉದ್ಭವಿಸುತ್ತದೆ: ಪ್ರತಿಯೊಂದು ಅಭ್ಯರ್ಥಿಗೂ ಅವನ ಅರ್ಹತೆಗೆ ಸರಿಯಾದ ಒಂದು ಹುದ್ದೆಯನ್ನು ಕೊಡಲು ಸಾಧ್ಯವೇ? ಈ ಸಂದರ್ಭವನ್ನು ಒಂದು ಗ್ರಾಫಿನ ಮೂಲಕ ವಿವರಿಸಬಹುದು. ಉದಾಹರಣೆಗಾಗಿ ಚಿತ್ರದಲ್ಲಿ ನೋಡಬಹುದು. ಇದರಲ್ಲಿ M ಹುದ್ದೆಗಳ ಗುಂಪನ್ನೂ, P ಅಭ್ಯರ್ಥಿಗಳ ಗುಂಪನ್ನೂ ಗುರುತಿಸಲಿ. m₁, m₂, m₃, m₄ ಬೇರೆ ಬೇರೆ ಖಾಲಿ ಹುದ್ದೆಗಳನ್ನೂ, p₁, p₂, p₃, p₄, p₅ ಈ ಹುದ್ದೆಗಳಿಗೆ ಅಭ್ಯರ್ಥಿಗಳನ್ನೂ ಸೂಚಿಸಲಿ. ಈ ಶೃಂಗಗಳ ಮೇಲೆ ಒಂದು ಗ್ರಾಫನ್ನು ಹೀಗೆ ರಚಿಸಬಹುದು.

p ಅಭ್ಯರ್ಥಿ m ಹುದ್ದೆಗೆ ಅರ್ಹನಾಗಿದ್ದರೆ PM ಅಂಚನ್ನು ಎಳೆಯುತ್ತೇವೆ. ಉದಾಹರಣೆಗಾಗಿ p₁ ಅಭ್ಯರ್ಥಿ m₂ ಮತ್ತು m₃ ಹುದ್ದೆಗಳಿಗೆ ಅರ್ಹ ಎಂದು ಚಿತ್ರದಲ್ಲಿ ತೋರಿಸಬಹುದು. ಇಲ್ಲಿ ಗಮನಿಸಬೇಕಾದ ವಿಷಯವೆಂದರೆ ಅಭ್ಯರ್ಥಿಗಳ ಗುಂಪಿನಲ್ಲಿ ಅಭ್ಯರ್ಥಿಗಳನ್ನು ಕೂಡಿಸುವ ಅಂಚುಗಳು ಹಾಗೂ ಹುದ್ದೆಗಳ ಗುಂಪಿನಲ್ಲಿ ಹುದ್ದೆಗಳನ್ನು ಕೂಡಿಸುವ ಅಂಚುಗಳು ಇಲ್ಲ. ಅಂದರೆ ಒಂದೇ ಗಣದಲ್ಲಿರುವ (ಸೆಟ್) ಬಿಂದುಗಳನ್ನು ಸೇರಿಸುವ ಅಂಚುಗಳು ಇಲ್ಲ. ಇಂಥ ಒಂದು ಗ್ರಾಫಿನ ಶೃಂಗಗಣವನ್ನು 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

ನಕ್ಷೆಗಳಿಗೆ ಬಣ್ಣ ಬಳಿಯುವಿಕೆ

ಒಂದು ದೇಶದ ನಕ್ಷೆಯಲ್ಲಿರುವ (ಮ್ಯಾಪ್) ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿಗೆ ರಾಜ್ಯಗಳಿಗೆ ಉಭಯ ಸಾಮಾನ್ಯವಾದ ಒಂದು ಸರಹದ್ದು ಇದ್ದರೆ ಅವುಗಳಿಗೆ ಅಕ್ಕಪಕ್ಕದ ರಾಜ್ಯಗಳು ಎಂದು ಹೆಸರು. ಒಂದು ನಕ್ಷೆಗೆ ಬಣ್ಣ ಬಳಿಯುವಿಕೆ ಎಂದರೆ ಅಕ್ಕಪಕ್ಕದ ರಾಜ್ಯಗಳಿಗೆ ಒಂದೇ ಬಣ್ಣ ಇಲ್ಲದ ಹಾಗೆ ಬಣ್ಣ ಬಳಿಯುವುದು ಎಂದರ್ಥ. ಸಾಕಷ್ಟು ಬಣ್ಣಗಳಿದ್ದಾಗ ಒಂದು ನಕ್ಷೆಗೆ ಬಣ್ಣ ಬಳಿಯುವುದು ಸುಲಭದ ಕೆಲಸ. ಆದರೆ ಕಡಿಮೆ ಬಣ್ಣಗಳಿದ್ದಾಗ ಇದು ಅಷ್ಟು ಸುಲಭವಲ್ಲ.

ನಾಲ್ಕು ಬಣ್ಣಗಳ ಊಹೆ: ನಾಲ್ಕು ಬಣ್ಣಗಳಿಂದ ಯಾವ ನಕ್ಷೆಗೆ ಬೇಕಾದರೂ ಬಣ್ಣ ಬಳಿಯಬಹುದು. ಅಂದರೆ ಒಂದು ನಕ್ಷೆಯಲ್ಲಿನ ರಾಜ್ಯಗಳ ಸಂಖ್ಯೆ ಎಷ್ಟೇ ಇದ್ದರೂ ಮೇಲೆ ಹೇಳಿದ ಷರತ್ತಿನ ಅನುಸಾರ ಬಣ್ಣ ಬಳಿಯಲು ಕೇವಲ ನಾಲ್ಕು ಭಿನ್ನ ಬಣ್ಣಗಳಿದ್ದರೆ ಸಾಕು. ಕೆಲವೊಂದು ನಕ್ಷೆಗಳಿಗೆ ಬಣ್ಣ ಬಳಿಯಲು ನಾಲ್ಕು ಬಣ್ಣಗಳು ಬೇಕೇ ಬೇಕು.

ಉದಾಹರಣೆಗೆ ಚಿತ್ರದಲ್ಲಿ ನೀಲಿ, ಕೆಂಪು, ಹಸಿರು, ಹಳದಿ ಬಣ್ಣಗಳನ್ನು ಬಳಸಿರುವುದನ್ನು ಚಿತ್ರದಲ್ಲಿ ತೋರಿಸಬಹುದು. ಚಿತ್ರದಲ್ಲಿ ಖಾಲಿ ಇರುವ 5 ನೆಯ ರಾಜ್ಯಕ್ಕೆ ನೀಲಿ ಬಣ್ಣವನ್ನೂ, 7ನೆಯ ರಾಜ್ಯಕ್ಕೆ ಹಸಿರು ಬಣ್ಣವನ್ನೂ ಬಳಿಯಬಹುದು; ಆಗ ಷರತ್ತು ಪೂರೈಕೆ ಆಗುತ್ತದೆ ಎಂಬುದು ಸ್ಪಷ್ಟ. ಬ್ರಿಟಿಷ್ ಭೌತವಿಜ್ಞಾನಿ ಫ್ರಾನ್ಸಿಸ್ ಗುಥ್ರಿ ಈ ಊಹೆಯನ್ನು 1852ರಲ್ಲಿ ಮಂಡಿಸಿದ. 1973ರ ವರೆಗೂ ಇದಕ್ಕೆ ಪರಿಹಾರ ಸಿಕ್ಕಿರಲಿಲ್ಲ ಮತ್ತು ಗಣಿತಶಾಸ್ತ್ರದ ಅತ್ಯಂತ ಕಠಿಣ ಹಾಗೂ ಪ್ರಖ್ಯಾತವಾದ ಸಮಸ್ಯೆಯಾಗಿ ಉಳಿದಿತ್ತು. ಇದನ್ನು ೧೯೭೬ ರಲ್ಲಿ ಇದಕ್ಕೆ ಪರಿಹಾರ ಕಂಡುಹಿಡಿಯಲಾಯಿತು. ಪ್ರಾರಂಭದಲ್ಲಿ ಇದಕ್ಕೆ ಅಷ್ಟೊಂದು ಮಹತ್ತ್ವ ಕೊಟ್ಟಿರಲಿಲ್ಲ. ಕಾರಣ, ಗಣಿತಶಾಸ್ತ್ರಜ್ಞರು ಈ ಊಹೆಯನ್ನು ಸಾಕಷ್ಟು ತಪ್ಪು ಸಾಧನೆಗಳು ಪ್ರಕಟಿತವಾದುವು. ಈ ಊಹೆಯ ವೈಶಿಷ್ಟ್ಯವೇನೆಂದರೆ ಇದು ಅಷ್ಟು ಕಠಿಣವಾಗಿದ್ದರೂ ಒಬ್ಬ ಸಾಮಾನ್ಯ ಮನುಷ್ಯನಿಗೂ ಅರ್ಥವಾಗುತ್ತದೆ. ಈ ಊಹೆ ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದ ಬೆಳೆವಣಿಗೆಗೆ ಮುಖ್ಯ ಕಾರಣವಾಗಿದೆ. ಇದೇ ಸಾಧಿತವಾಗದಿದ್ದರೂ ಈ ಕೆಳಗಿನ ಪ್ರಮೇಯವನ್ನು ಸಾಧಿಸಲಾಗಿದೆ. ಯಾವ ನಕ್ಷೆಗೆ ಬಣ್ಣ ಬಳಿಯ ಬೇಕಾದರೂ ಐದಕ್ಕಿಂತ ಜಾಸ್ತಿ ಬಣ್ಣಗಳು ಬೇಕಾಗಿಲ್ಲ.

ಗ್ರಂಥಸೂಚಿ

• Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability.

ಹೊರಗಿನ ಕೊಂಡಿಗಳು

• "Graph theory", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Graph theory tutorial Archived 2012-01-16 ವೇಬ್ಯಾಕ್ ಮೆಷಿನ್ ನಲ್ಲಿ.
• A searchable database of small connected graphs
• House of Graphs — searchable database of graphs with a drawing-based search feature.
• Image gallery: graphs ವೇಬ್ಯಾಕ್ ಮೆಷಿನ್ ನಲ್ಲಿ (archived February 6, 2006)
• Concise, annotated list of graph theory resources for researchers^[Usurped!]
• rocs — a graph theory IDE
• The Social Life of Routers — non-technical paper discussing graphs of people and computers
• Graph Theory Software — tools to teach and learn graph theory
• Online books, and library resources in your library and in other libraries about graph theory
• A list of graph algorithms Archived 2019-07-13 ವೇಬ್ಯಾಕ್ ಮೆಷಿನ್ ನಲ್ಲಿ. with references and links to graph library implementations