സുഹൃത്ബന്ധങ്ങൾ

നിങ്ങളിൽ മിക്കവരും FB അംഗങ്ങളായിരിക്കുമല്ലോ. എന്നാലൊരു ചോദ്യം. അനു, വിനു, ടിനു, മനു, സൈനു എന്നിവർ FBയിൽ അംഗങ്ങളാണ്. അവരുടെ സുഹൃത്ബന്ധങ്ങളാണ് താഴെ കൊടുത്തിരിക്കുന്നത്.

അനുവിന്റെ സുഹൃത്തുക്കളാണ് വിനുവും ടിനുവും.
വിനുവിന്റെ സുഹൃത്തുക്കളാണ് അനുവും മനുവും സൈനുവും.
ടിനുവിന് അനു മാത്രമേ സുഹൃത്തായുള്ളൂ.
മനുവിന്റെ സുഹൃത്തുക്കളാണ് വിനുവും സൈനുവും.
സൈനുവിന്റെ സുഹൃത്തുക്കളാണ് വിനുവും മനുവും.

ഒരാൾ മറ്റൊരാളുടെ സുഹൃത്താണെങ്കിൽ തിരിച്ചും അങ്ങനെയാണല്ലോ? ഈ സുഹൃത്ബന്ധങ്ങൾ എളുപ്പത്തിൽ മനസ്സിലാക്കാൻ നമുക്കൊരു ചിത്രം വരച്ചാലോ? ഓരോ കുട്ടിയേയും നമുക്കൊരു ശീർഷമാക്കി വരയ്ക്കാം. രണ്ടുപേർ തമ്മിലുള്ള സുഹൃത്ബന്ധം ഒരു വശമായും. താഴെയുള്ള ചിത്രം കാണൂ.

ഇനി നമുക്ക് ഓരോരുത്തർക്കുമുള്ള സുഹൃത്തുക്കളുടെ എണ്ണം കൂട്ടിനോക്കാം. അനുവിന് 2 സുഹൃത്തുക്കൾ. വിനുവിന് 3. ടിനുവിന് 1. മനുവിന് 2. സൈനുവിനും 2. മൊത്തം 10. ഇനി എത്ര സുഹൃത്ബന്ധങ്ങളുണ്ടെന്ന് നോക്കാം. ഒരു വശമാണല്ലോ ഒരു സുഹൃത്ബന്ധം. അതിനാൽ മൊത്തം 5 സുഹൃത്ബന്ധങ്ങളുണ്ട്. ഓരോരുത്തരുടെയും സുഹൃത്തുക്കളുടെ എണ്ണത്തിന്റെ തുകയും മൊത്തം സുഹൃത്ബന്ധങ്ങളുടെ എണ്ണവും തമ്മിലെന്തെങ്കിലും ബന്ധമുണ്ടോ? സുഹൃത്തുക്കളുടെ എണ്ണത്തിന്റെ തുക 10. മൊത്തം സുഹൃത്ബന്ധങ്ങളുടെ എണ്ണം 5. 5ന്റെ ഇരട്ടിയാണല്ലോ 10. ഇത് യാദൃശ്ചികമാണോ? നമുക്ക് നോക്കാം.

മുകളിലത്തെ ചോദ്യം ആരേഖ ശാസ്ത്രത്തിന്റെ വാക്കുകളിൽ: ഒരു ആരേഖത്തിലെ ശീർഷമാനങ്ങളുടെ തുകയും വശങ്ങളുടെ എണ്ണവും തമ്മിലെന്തെങ്കിലും ബന്ധമുണ്ടോ? ഒരു ശീർഷത്തിന്റെ മാനം എന്നത് അതിനോടു ചേർന്ന വശങ്ങളുടെ എണ്ണമാണെന്ന് കൂട്ടുകാർക്ക് ഓർമയുണ്ടല്ലോ? മുകളിൽ നമ്മൾ കണ്ടതനുസരിച്ച് ശീർഷമാനങ്ങളുടെ തുക വശങ്ങളുടെ എണ്ണത്തിന്റെ ഇരട്ടിയാണ്. ഇത് യാദൃശ്ചികമല്ല. ഈ ഒരു സിദ്ധാന്തമാണ് ആരേഖ ശാസ്ത്രത്തിലെ ഏറ്റവും ലളിതവും, പ്രസിദ്ധവും, അടിസ്ഥാനപരവുമായ 'വശ ശീർഷമാന സിദ്ധാന്തം'.

വശ ശീർഷമാന സിദ്ധാന്തം (Handshaking Lemma): ഒരു ആരേഖത്തിലെ ശീർഷമാനങ്ങളുടെ തുക വശങ്ങളുടെ എണ്ണത്തിന്റെ ഇരട്ടിയായിരിക്കും.

വശ ശീർഷമാന സിദ്ധാന്തം എങ്ങനെ തെളിയിക്കാം? നമുക്ക് ഒരു ആരേഖത്തിലെ ശീർഷമാനങ്ങളുടെ തുക കണ്ടു പിടിക്കാം. Aയും Bയും രണ്ടു ശീർഷങ്ങളും അവ തമ്മിൽ ഒരു വശവുമുണ്ടെങ്കിൽ ആ വശം Aയുടെ ശീർഷമാനത്തിലും Bയുടെ ശീർഷമാനത്തിലും ഓരോന്നുവീതം സംഭാവന ചെയ്യുന്നുണ്ടല്ലോ? അതായത് ഓരോ വശവും ശീർഷമാനങ്ങളുടെ എണ്ണത്തിന്റെ തുകയിൽ 2 സംഭാവന ചെയ്യുന്നു. അതുകൊണ്ട് ശീർഷമാനങ്ങളുടെ തുക വശങ്ങളുടെ എണ്ണത്തിന്റെ ഇരട്ടിയായിരിക്കും.

കുറിപ്പ്: വശ ശീർഷമാന സിദ്ധാന്തത്തിന് Handshaking Lemma എന്ന പേര് എങ്ങനെ വന്നെന്ന് കൂട്ടുകാർ ചിന്തിക്കുന്നുണ്ടാകും. വശ ശീർഷമാന സിദ്ധാന്തം മറ്റൊരു രീതിയിലും പ്രസ്താവിക്കാം. ഒരു ചടങ്ങിൽ പങ്കെടുക്കുന്നവരെ അവർ എത്ര പേർക്ക് കൈ കൊടുക്കുന്നു എന്നതിനെ അടിസ്ഥാനമാക്കി രണ്ടായ് തരം തിരിക്കാം - ഒറ്റയും ഇരട്ടയും. അതായത്, ഒരാൾ കൈ കൊടുത്തവരുടെ എണ്ണം ഒറ്റ സംഖ്യ ആണെങ്കിൽ ആദ്യത്തെ കൂട്ടത്തിലും ഇരട്ട സംഖ്യയാണെങ്കിൽ രണ്ടാമത്തെ കൂട്ടത്തിലും. ഇതിൽ രണ്ടാമത്തെ കൂട്ടത്തിലുള്ള ആളുകളുടെ എണ്ണം ഇരട്ട സംഖ്യയായിരിക്കുമെന്നതാണ് വശ ശീർഷമാന സിദ്ധാന്തത്തിന്റെ മറ്റൊരു രീതിയിലുള്ള പ്രസ്താവന. അതെങ്ങനെ ശരിയാകുമെന്ന് ചിന്തിച്ചു നോക്കൂ.

റോഡുകളും കവലകളും

ചെറിയ ഒരു പട്ടണം സങ്കൽപ്പിക്കുക. അവിടെയുള്ള റോഡുകളെല്ലാം നേർരേഖയിലാണെന്ന് കരുതുക. അപ്പോൾ സ്വാഭാവികമായും ധാരാളം കവലകൾ (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 ആണെന്നു കാണാം. ഇനി കൂട്ടുകാർക്ക് നേരമ്പോക്കിനായി ഒരു ചോദ്യം: ഒരു ആരേഖത്തിലെ എല്ലാ ശീർഷങ്ങളുടേയും മാനങ്ങളുടെ തുകയും ആരേഖത്തിലെ വശങ്ങളുടെ എണ്ണവും തമ്മിലെന്തെങ്കിലും ബന്ധമുണ്ടോ?