ചെറിയ ഒരു പട്ടണം സങ്കൽപ്പിക്കുക. അവിടെയുള്ള റോഡുകളെല്ലാം
നേർരേഖയിലാണെന്ന് കരുതുക. അപ്പോൾ സ്വാഭാവികമായും ധാരാളം കവലകൾ (junctions)
കാണുമല്ലോ? ഗതാഗത നിയന്ത്രണത്തിന് സ്വയം പ്രവർത്തിക്കുന്ന സിഗ്നലുകൾ ഉണ്ട്.
എന്നാൽ റോഡുകൾ നിരീക്ഷിക്കാൻ പോലീസുകാരെ നിയമിക്കണം. ചില സാങ്കേതിക
കാരണങ്ങളാൽ പോലീസുകാരെ കവലകളിൽ മാത്രമേ നിർത്താൻ കഴിയുകയുള്ളൂ. ഒരു കവലയിൽ
നില്ക്കുന്ന പോലീസിന് ചുറ്റുമുള്ള എല്ലാ കവലകൾ വരേയുമുള്ള റോഡുകൾ
നിരീക്ഷിക്കാൻ കഴിയും. ഒരു പട്ടണത്തിലെ റോഡുകളുടെ രൂപരേഖ താഴെ
കൊടുത്തിരിക്കുന്നു. കവലകൾ A, B, C എന്നിങ്ങനെ
അടയാളപ്പെടുത്തിയിരിക്കുന്നത് ശ്രദ്ധിക്കുമല്ലോ? AB, AJ, AG എന്നീ റോഡുകൾ
നിരീക്ഷിക്കാൻ Aയിൽ ഒരു പോലീസിനെ നിർത്തിയാൽ മതി.
ഇനി കൂട്ടുകാരോട് ഒരു ചോദ്യം: എത്ര പോലീസുകാരെ കവലകളിൽ നിർത്തിയാൽ എല്ലാ റോഡുകളും നിരീക്ഷിക്കാൻ കഴിയും? എല്ലാ കവലകളിലും ഓരോ പോലീസിനെ നിർത്തിയാൽ കാര്യം നടക്കുമല്ലോ? എന്നാൽ അത്രയും പോലീസുകാരുടെ ആവശ്യമുണ്ടോ? ഉദാഹരണത്തിന് A മുതൽ B വരെയുള്ള റോഡ് നിരീക്ഷിക്കാൻ Aയിലോ Bയിലോ ഒരു പോലീസിനെ നിർത്തിയാൽ മതിയല്ലോ? നമ്മുടെ ഗവണ്മെന്റ് ചെലവു ചുരുക്കുന്നതിൽ വളരെ പ്രാധാന്യം നൽകുന്നതിനാൽ ഏറ്റവും കുറഞ്ഞത് എത്ര പോലീസുകാർ മതി എന്നുള്ളതാണ് പ്രസക്തമായ ചോദ്യം. കൂട്ടുകാർക്ക് ഗവണ്മെന്റിനെ ഒന്നു സഹായിക്കാമോ?
ഉത്തരം കാണുന്നതിനു മുൻപ് റോഡുകളുടെ രൂപരേഖ ഒന്നു ലഘൂകരിച്ചാലോ? കവലകളെ ശീർഷങ്ങൾ കൊണ്ടും റോഡുകളെ വശങ്ങൾ കൊണ്ടും രേഖപ്പെടുത്താം. താഴെ കൊടുത്തിരിക്കുന്ന ചിത്രം കാണൂ. ഒരു ശീർഷം അതിനോട് ചേർന്ന എല്ലാ വശങ്ങളെയും ആവരണം ചെയ്യുന്നു എന്നു പറയാം. ഉദാഹരണത്തിന് ശീർഷം A, വശങ്ങളായ AB, AJ, AG എന്നിവയെ ആവരണം ചെയ്യുന്നു. മുൻപു ചോദിച്ച ചോദ്യം പരിഷ്കരിച്ചാൽ: ഏറ്റവും കുറഞ്ഞത് എത്ര ശീർഷങ്ങൾ കൊണ്ട് എല്ലാ വശങ്ങളെയും ആവരണം ചെയ്യാൻ കഴിയും?
മുന്നൂറോളം വർഷങ്ങളായി വികസിച്ചു വന്ന ആരേഖ ശാസ്ത്രം (Graph Theory) എന്ന ഗണിത ശാസ്ത്ര ശാഖയിലെ ശീർഷാവരണം (Vertex Cover) എന്ന പ്രസിദ്ധമായ ഒരു പ്രശ്നമാണ് നമ്മളിപ്പോൾ കണ്ടത്. ശീർഷങ്ങളുടെ (Vertices) ഗണവും ശീർഷങ്ങളെ ബന്ധിപ്പിക്കുന്ന വശങ്ങളുടെ (Edges) ഗണവും ചേർന്നതാണ് ഒരു ആരേഖം (Graph). 12 ശീർഷങ്ങളും 18 വശങ്ങളുമുള്ള ഒരു ആരേഖമാണ് മുകളിലുള്ളത്. കംപ്യുട്ടർ സയൻസിന്റെ അടിസ്ഥാന ആശയങ്ങൾ രൂപപ്പെടുത്തുന്നതിൽ ആരേഖ ശാസ്ത്രത്തിന്റെ പങ്ക് നിർണായകമാണ്. വളരെയധികം രസകരങ്ങളായ ഒരുപാട് സിദ്ധാന്തങ്ങളും, പ്രശ്നങ്ങളും, ഇനിയും ഉത്തരം ലഭിച്ചിട്ടില്ലാത്തതുമായ ഒരുപാട് പ്രഹേളികകളും ആരേഖ ശാസ്ത്രത്തിലുണ്ട്. അവയെക്കുറിച്ചെല്ലാം പിന്നീട്.
[ഉത്തരം: എല്ലാ വശങ്ങളെയും ആവരണം ചെയ്യാൻ കുറഞ്ഞത് 7 ശീർഷങ്ങൾ ആവശ്യമാണ്. ഒരുത്തരം ഇതാ: {B, E, F, G, I, J, K}. 7ൽ കുറവ് ശീർഷങ്ങൾ കൊണ്ട് വശങ്ങൾ മുഴുവൻ ആവരണം ചെയ്യാൻ പറ്റുമോ? 7 ശീർഷങ്ങളുള്ള വേറെ ഉത്തരമുണ്ടോ?]
കുറിപ്പ്: ഒരു ശീർഷത്തിന്റെ മാനം എന്നത് അതിൽ ചേർന്നിരിക്കുന്ന വശങ്ങളുടെ എണ്ണമാണ്. മുകളിലുള്ള ഗ്രാഫിൽ എല്ലാ ശീർഷങ്ങളുടേയും മാനം 3 ആണെന്നു കാണാം. ഇനി കൂട്ടുകാർക്ക് നേരമ്പോക്കിനായി ഒരു ചോദ്യം: ഒരു ആരേഖത്തിലെ എല്ലാ ശീർഷങ്ങളുടേയും മാനങ്ങളുടെ തുകയും ആരേഖത്തിലെ വശങ്ങളുടെ എണ്ണവും തമ്മിലെന്തെങ്കിലും ബന്ധമുണ്ടോ?
ഇനി കൂട്ടുകാരോട് ഒരു ചോദ്യം: എത്ര പോലീസുകാരെ കവലകളിൽ നിർത്തിയാൽ എല്ലാ റോഡുകളും നിരീക്ഷിക്കാൻ കഴിയും? എല്ലാ കവലകളിലും ഓരോ പോലീസിനെ നിർത്തിയാൽ കാര്യം നടക്കുമല്ലോ? എന്നാൽ അത്രയും പോലീസുകാരുടെ ആവശ്യമുണ്ടോ? ഉദാഹരണത്തിന് A മുതൽ B വരെയുള്ള റോഡ് നിരീക്ഷിക്കാൻ Aയിലോ Bയിലോ ഒരു പോലീസിനെ നിർത്തിയാൽ മതിയല്ലോ? നമ്മുടെ ഗവണ്മെന്റ് ചെലവു ചുരുക്കുന്നതിൽ വളരെ പ്രാധാന്യം നൽകുന്നതിനാൽ ഏറ്റവും കുറഞ്ഞത് എത്ര പോലീസുകാർ മതി എന്നുള്ളതാണ് പ്രസക്തമായ ചോദ്യം. കൂട്ടുകാർക്ക് ഗവണ്മെന്റിനെ ഒന്നു സഹായിക്കാമോ?
ഉത്തരം കാണുന്നതിനു മുൻപ് റോഡുകളുടെ രൂപരേഖ ഒന്നു ലഘൂകരിച്ചാലോ? കവലകളെ ശീർഷങ്ങൾ കൊണ്ടും റോഡുകളെ വശങ്ങൾ കൊണ്ടും രേഖപ്പെടുത്താം. താഴെ കൊടുത്തിരിക്കുന്ന ചിത്രം കാണൂ. ഒരു ശീർഷം അതിനോട് ചേർന്ന എല്ലാ വശങ്ങളെയും ആവരണം ചെയ്യുന്നു എന്നു പറയാം. ഉദാഹരണത്തിന് ശീർഷം A, വശങ്ങളായ AB, AJ, AG എന്നിവയെ ആവരണം ചെയ്യുന്നു. മുൻപു ചോദിച്ച ചോദ്യം പരിഷ്കരിച്ചാൽ: ഏറ്റവും കുറഞ്ഞത് എത്ര ശീർഷങ്ങൾ കൊണ്ട് എല്ലാ വശങ്ങളെയും ആവരണം ചെയ്യാൻ കഴിയും?
മുന്നൂറോളം വർഷങ്ങളായി വികസിച്ചു വന്ന ആരേഖ ശാസ്ത്രം (Graph Theory) എന്ന ഗണിത ശാസ്ത്ര ശാഖയിലെ ശീർഷാവരണം (Vertex Cover) എന്ന പ്രസിദ്ധമായ ഒരു പ്രശ്നമാണ് നമ്മളിപ്പോൾ കണ്ടത്. ശീർഷങ്ങളുടെ (Vertices) ഗണവും ശീർഷങ്ങളെ ബന്ധിപ്പിക്കുന്ന വശങ്ങളുടെ (Edges) ഗണവും ചേർന്നതാണ് ഒരു ആരേഖം (Graph). 12 ശീർഷങ്ങളും 18 വശങ്ങളുമുള്ള ഒരു ആരേഖമാണ് മുകളിലുള്ളത്. കംപ്യുട്ടർ സയൻസിന്റെ അടിസ്ഥാന ആശയങ്ങൾ രൂപപ്പെടുത്തുന്നതിൽ ആരേഖ ശാസ്ത്രത്തിന്റെ പങ്ക് നിർണായകമാണ്. വളരെയധികം രസകരങ്ങളായ ഒരുപാട് സിദ്ധാന്തങ്ങളും, പ്രശ്നങ്ങളും, ഇനിയും ഉത്തരം ലഭിച്ചിട്ടില്ലാത്തതുമായ ഒരുപാട് പ്രഹേളികകളും ആരേഖ ശാസ്ത്രത്തിലുണ്ട്. അവയെക്കുറിച്ചെല്ലാം പിന്നീട്.
[ഉത്തരം: എല്ലാ വശങ്ങളെയും ആവരണം ചെയ്യാൻ കുറഞ്ഞത് 7 ശീർഷങ്ങൾ ആവശ്യമാണ്. ഒരുത്തരം ഇതാ: {B, E, F, G, I, J, K}. 7ൽ കുറവ് ശീർഷങ്ങൾ കൊണ്ട് വശങ്ങൾ മുഴുവൻ ആവരണം ചെയ്യാൻ പറ്റുമോ? 7 ശീർഷങ്ങളുള്ള വേറെ ഉത്തരമുണ്ടോ?]
കുറിപ്പ്: ഒരു ശീർഷത്തിന്റെ മാനം എന്നത് അതിൽ ചേർന്നിരിക്കുന്ന വശങ്ങളുടെ എണ്ണമാണ്. മുകളിലുള്ള ഗ്രാഫിൽ എല്ലാ ശീർഷങ്ങളുടേയും മാനം 3 ആണെന്നു കാണാം. ഇനി കൂട്ടുകാർക്ക് നേരമ്പോക്കിനായി ഒരു ചോദ്യം: ഒരു ആരേഖത്തിലെ എല്ലാ ശീർഷങ്ങളുടേയും മാനങ്ങളുടെ തുകയും ആരേഖത്തിലെ വശങ്ങളുടെ എണ്ണവും തമ്മിലെന്തെങ്കിലും ബന്ധമുണ്ടോ?
അഭിപ്രായങ്ങളൊന്നുമില്ല:
ഒരു അഭിപ്രായം പോസ്റ്റ് ചെയ്യൂ