കളറിംഗ് ബുക്ക് റോഡ്. കാറുകൾക്കായി നേരായ റോഡ് ഡൗൺലോഡ് ചെയ്യുക

(ഗണിതശാസ്ത്രത്തിൽ അറിവുള്ളവർക്കും അനുഭാവികൾക്കും ഈ എൻട്രി താൽപ്പര്യമുള്ളതായിരിക്കാം)

കഴിഞ്ഞ ദിവസം ഗ്രാഫ് തിയറിയിൽ നിന്നുള്ള രസകരമായ ഒരു പ്രശ്നത്തെക്കുറിച്ച് ഞാൻ വായിച്ചു - റോഡ് കളറിംഗ് അനുമാനം. ഈ അനുമാനം 37 വർഷമായി തുറന്നിരിക്കുന്നു, എന്നാൽ മൂന്ന് വർഷം മുമ്പ് ഇത് ഇസ്രായേലി ഗണിതശാസ്ത്രജ്ഞൻ എബ്രഹാം ട്രാക്റ്റ്മാൻ തെളിയിച്ചു. തെളിവ് വളരെ പ്രാഥമികമായി മാറി, ചില ബുദ്ധിമുട്ടുകളോടെ (എന്റെ മസ്തിഷ്കം ക്ഷയിച്ചതിനാൽ) എനിക്ക് അത് വായിക്കാനും മനസ്സിലാക്കാനും കഴിഞ്ഞു, ഈ പോസ്റ്റിൽ അത് വിശദീകരിക്കാൻ പോലും ഞാൻ ശ്രമിക്കും.

ഇനിപ്പറയുന്ന ഉദാഹരണത്തിലൂടെ പ്രശ്നം വിശദീകരിക്കാം. ഓരോ കവലയിലും നിങ്ങൾക്ക് വടക്ക്, തെക്ക്, കിഴക്ക്, പടിഞ്ഞാറ് എന്നിങ്ങനെ നാല് ദിശകളിൽ ഒന്നിലേക്ക് പോകാൻ കഴിയുന്ന ഒരു നഗര ഭൂപടം സങ്കൽപ്പിക്കുക. കാർ ഏതെങ്കിലും കവലയിൽ നിന്ന് ആരംഭിക്കുകയും നിർദ്ദേശങ്ങളുടെ ചില ലിസ്റ്റ് പിന്തുടരുകയും ചെയ്യുന്നുവെങ്കിൽ - "വടക്ക്, വടക്ക്, കിഴക്ക്" മുതലായവ. - അപ്പോൾ അവൾ ഒടുവിൽ മറ്റേതെങ്കിലും കവലയിൽ എത്തും. മെഷീൻ എവിടെ നിന്ന് ആരംഭിച്ചാലും അതേ സ്ഥലത്തേക്ക് കൊണ്ടുപോകുന്ന ദിശകളുടെ ഒരു ലിസ്റ്റ് കണ്ടെത്താൻ കഴിയുമോ? മാപ്പ് മാൻഹട്ടൻ പോലെ കാണപ്പെടുന്നുവെങ്കിൽ - ഒരു സാധാരണ ഗ്രിഡ് - പിന്നെ ഇല്ല, പക്ഷേ അതിന് ഒരുപാട് നിർജ്ജീവങ്ങളും അപ്രതീക്ഷിത വഴിത്തിരിവുകളും ഉണ്ടാകുമോ?

അല്ലെങ്കിൽ മറ്റൊരു ഉദാഹരണം. നിങ്ങളുടെ സുഹൃത്ത് കേന്ദ്രം കണ്ടെത്തേണ്ട ഒരു ഭ്രമണപഥത്തിൽ കുടുങ്ങി, സഹായം അഭ്യർത്ഥിച്ച് അവൻ നിങ്ങളെ വിളിച്ചു. ഈ മാളിക എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് നിങ്ങൾക്കറിയാം, പക്ഷേ നിങ്ങളുടെ സുഹൃത്ത് എവിടെയാണെന്ന് നിങ്ങൾക്കറിയില്ല. നിങ്ങളുടെ സുഹൃത്ത് എവിടെയായിരുന്നാലും തീർച്ചയായും കേന്ദ്രത്തിലേക്ക് കൊണ്ടുവരുന്ന ഒരു ശ്രേണി കമാൻഡുകൾ ഉണ്ടാകുമോ?

ഈ രണ്ട് ഉദാഹരണങ്ങളിലും, ഓരോ പോയിന്റിലെയും "ദിശകൾ" നിശ്ചയിച്ചിരിക്കുന്നു, ഒരു പരിഹാരം നിലവിലുണ്ട് അല്ലെങ്കിൽ ഇല്ല. എന്നാൽ കൂടുതൽ പൊതുവായി, ഈ പ്രശ്നം ചോദിക്കുന്നു: ഉദാഹരണത്തിന്, ഓരോ കവലയിലും വ്യത്യസ്തമായി "പടിഞ്ഞാറ്, വടക്ക്, കിഴക്ക്, തെക്ക്" പോയിന്റുകൾ എവിടെയാണെന്ന് നമുക്ക് തിരഞ്ഞെടുക്കാൻ കഴിയുമെങ്കിൽ, നമുക്ക് ഒരു "സമന്വയ പദത്തിന്റെ" നിലനിൽപ്പ് ഉറപ്പാക്കാൻ കഴിയുമോ - കമാൻഡുകളുടെ ഒരു ശ്രേണി. ഏതെങ്കിലും സ്ഥലം സ്ഥിരതയിലേക്ക് നയിക്കുമോ?

പൊതുവായ സാഹചര്യത്തിൽ, ലംബങ്ങൾക്കിടയിൽ "അമ്പ്" അരികുകളുള്ള ഒരു ഡയറക്ട് ഗ്രാഫ് ജി ഉണ്ടായിരിക്കട്ടെ. ഈ ഗ്രാഫിന് ഏകീകൃത ഔട്ട്ഡിഗ്രി d ഉണ്ടായിരിക്കട്ടെ - ഇതിനർത്ഥം ഓരോ ശീർഷത്തിനും കൃത്യമായി d അരികുകൾ ഉണ്ടെന്നാണ്. ഈ സാഹചര്യത്തിൽ, ഓരോ വ്യക്തിഗത ശീർഷത്തിലും മറ്റൊരു സംഖ്യയ്ക്ക് പ്രവേശിക്കാൻ കഴിയും, അത് ആവശ്യമില്ല. നമുക്ക് ചില അക്ഷരമാലകളുടെ ഒരു കൂട്ടം ഡി അക്ഷരങ്ങൾ ഉണ്ടായിരിക്കട്ടെ, അതിനെ നമ്മൾ "നിറങ്ങൾ" എന്ന് വിളിക്കും. ഓരോ ശീർഷത്തിനും അതിന്റെ d ഔട്ട്‌ഗോയിംഗ് അരികുകൾക്കായി എല്ലാ d അക്ഷരങ്ങളും നൽകിയാണ് ഗ്രാഫിന്റെ “നിറം” നൽകുന്നത്. അതിനാൽ നമ്മൾ ഏതെങ്കിലും ശീർഷത്തിലാണെങ്കിൽ, α നിറത്തിനനുസരിച്ച് എവിടെയെങ്കിലും "പോകാൻ" ആഗ്രഹിക്കുന്നുവെങ്കിൽ, ഏത് പുതിയ ശീർഷത്തിലേക്ക് പോകണമെന്ന് കളറിംഗ് എല്ലായ്പ്പോഴും നമ്മോട് പറയും. ഒരു "വാക്ക്" എന്നത് അക്ഷരങ്ങളുടെ-വർണ്ണങ്ങളുടെ ഏതെങ്കിലും ശ്രേണിയാണ്. തുടർന്ന്, ഗ്രാഫിൽ ഒരു കളറിംഗ് നൽകിയിട്ടുണ്ടെങ്കിൽ, x എന്നത് ചില ശീർഷകവും w എന്നത് ചില പദവുമാണെങ്കിൽ, x-ൽ നിന്ന് ആരംഭിച്ച് w എന്ന വാക്കിന് ശേഷം നമ്മൾ എത്തിച്ചേരുന്ന ശീർഷത്തെ xw സൂചിപ്പിക്കുന്നു.

കളറിംഗ് ബുക്ക് എന്ന് വിളിക്കുന്നു സമന്വയിപ്പിക്കുന്നു, ഏതെങ്കിലും ശീർഷം x നെ ഒരു നിശ്ചിത ശീർഷത്തിലേക്ക് നയിക്കുന്ന w ഒരു വാക്ക് ഉണ്ടെങ്കിൽ x 0 . ഈ സാഹചര്യത്തിൽ w എന്ന് വിളിക്കുന്നു സമന്വയിപ്പിക്കുന്ന വാക്ക്. റോഡ് കളറിംഗ് പ്രശ്നം ചോദിക്കുന്ന ചോദ്യം ഇതാണ്: എല്ലായ്പ്പോഴും സമന്വയിപ്പിക്കുന്ന കളറിംഗ് ഉണ്ടോ? ഒരു ഗ്രാഫിന്റെ അരികുകൾ എല്ലാ ശീർഷകങ്ങളും ഒന്നായി ചുരുക്കാൻ കഴിയുന്ന വിധത്തിൽ എപ്പോഴും നിറം നൽകാനാകുമോ?

ഈ പ്രശ്‌നത്തിന് വിവിധ മേഖലകളിൽ ആപ്ലിക്കേഷനുകളുണ്ട്, ഉദാഹരണത്തിന് വിക്കിപീഡിയയിൽ ഇത് വായിക്കാം. കമ്പ്യൂട്ടർ സയൻസിൽ, ഓട്ടോമാറ്റ തിയറിയിൽ പറയാം. ഒരു കളറിംഗ് ഗ്രാഫിനെ ഒരു ഡിറ്റർമിനിസ്റ്റിക് ഫിനിറ്റ് ഓട്ടോമാറ്റൺ ആയി കണക്കാക്കാം, അതിൽ ലംബങ്ങൾ അവസ്ഥകളാണ്, അരികുകൾ അവയ്ക്കിടയിൽ എങ്ങനെ നീങ്ങണം എന്ന് സൂചിപ്പിക്കുന്നു. ഞങ്ങൾ ഈ മെഷീനെ ദൂരെ നിന്ന് നിയന്ത്രിച്ചു, ചില ഇൻഫർമേഷൻ ചാനലിലൂടെ കമാൻഡുകൾ അയച്ചു, ചില തകരാറുകൾ കാരണം ഈ ചാനൽ മലിനമായി, മെഷീന് ചില തെറ്റായ നിർദ്ദേശങ്ങൾ ലഭിച്ചു, ഇപ്പോൾ അത് ഏത് അവസ്ഥയിലാണെന്ന് പോലും ഞങ്ങൾക്ക് അറിയില്ല . പിന്നെ, ഒരു സമന്വയ വാക്ക് ഉണ്ടെങ്കിൽ, അത് ഇപ്പോൾ എവിടെയാണെങ്കിലും, നമുക്ക് അറിയാവുന്ന അവസ്ഥയിലേക്ക് കൊണ്ടുവരാൻ കഴിയും.

അപ്പോൾ എപ്പോഴാണ് സമന്വയ കളറിംഗ് നിലനിൽക്കുന്നത്? റോഡ് കളറിംഗ് അനുമാനം ഗ്രാഫിൽ രണ്ട് നിയന്ത്രണങ്ങൾ കൂടി ഏർപ്പെടുത്തുന്നു (ഓരോ ശീർഷകത്തിനും കൃത്യമായി d അരികുകൾ ഉണ്ട് എന്നതിന് പുറമെ). ഒന്നാമതായി, ഗ്രാഫ് ശക്തമായി ബന്ധിപ്പിച്ചിരിക്കണം - ഇതിനർത്ഥം ഏതെങ്കിലും ശീർഷത്തിൽ നിന്ന് മറ്റൊന്നിലേക്ക് ഒരു റൂട്ട് ഉണ്ടെന്നാണ്. രണ്ടാമതായി, ഗ്രാഫ് ആനുകാലികമായിരിക്കരുത്. ഗ്രാഫിന്റെ എല്ലാ ശീർഷകങ്ങളെയും V 1, V 2, ... V n എന്നിങ്ങനെ വിഭജിക്കാൻ കഴിയുമെന്ന് സങ്കൽപ്പിക്കുക, അങ്ങനെ ഗ്രാഫിന്റെ ഏതെങ്കിലും അറ്റം ചില Vi, Vi+1 അല്ലെങ്കിൽ V n, V 0 എന്നിവയിൽ നിന്നുള്ള ലംബങ്ങളെ ബന്ധിപ്പിക്കുന്നു. ഓരോ Vയിലെയും ശീർഷകങ്ങൾക്കിടയിൽ അരികുകളില്ല, അവയ്‌ക്ക് ഏതെങ്കിലും V യ്‌ക്കിടയ്‌ക്ക് “ചാടാൻ” കഴിയില്ല, ക്രമത്തിൽ മാത്രം. അത്തരമൊരു ഗ്രാഫിനെ ആനുകാലികം എന്ന് വിളിക്കുന്നു. അത്തരമൊരു ഗ്രാഫിന് സമന്വയിപ്പിക്കുന്ന കളറിംഗ് ഉണ്ടാകില്ലെന്ന് വ്യക്തമാണ്, കാരണം നിങ്ങൾ അത് എങ്ങനെ കളർ ചെയ്താലും ഏത് വാക്കുകൾ ഉപയോഗിച്ചാലും വ്യത്യസ്ത V i ലെ രണ്ട് ലംബങ്ങൾ ഒരിക്കലും ഒരുമിച്ച് വരില്ല - അവ ഒരു സൈക്കിളിൽ നടക്കുന്നത് തുടരും.

ഈ വ്യവസ്ഥകൾ മതിയെന്ന് റോഡ് കളറിംഗ് സിദ്ധാന്തം പറയുന്നു: ഓരോ ശീർഷത്തിൽ നിന്നും d അരികുകളുള്ള, ആനുകാലികമല്ലാത്ത, ശക്തമായി ബന്ധിപ്പിച്ച ഡയറക്‌റ്റ് ഗ്രാഫിന് ഒരു സമന്വയിപ്പിക്കുന്ന കളറിംഗ് ഉണ്ട്. 1970-ലാണ് ഇത് ആദ്യമായി ഒരു സിദ്ധാന്തമായി രൂപപ്പെടുത്തിയത്, അതിനുശേഷം പ്രത്യേക കേസുകൾ തെളിയിക്കുന്ന നിരവധി ഭാഗിക ഫലങ്ങൾ ഉണ്ടായിട്ടുണ്ട്, എന്നാൽ പൂർണ്ണമായ തെളിവ് 2007 വരെ പ്രത്യക്ഷപ്പെട്ടില്ല. ഇനിപ്പറയുന്നത് മിക്കവാറും മുഴുവൻ തെളിവുകളും (ഒരു സാങ്കേതിക ലെമ്മ ഒഴികെ) ഞാൻ വീണ്ടും പറയുകയാണ്.

ആനുകാലികത

ഒന്നാമതായി, ആനുകാലികമല്ലാത്ത അവസ്ഥയെ മറ്റൊരു തത്തുല്യമായ ഒന്ന് ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കാം. ഗ്രാഫിലെ ഏത് സൈക്കിളിന്റെയും ദൈർഘ്യം ഹരിച്ചാൽ N>1 എന്ന സംഖ്യ ഉണ്ടെങ്കിൽ മാത്രം ഗ്രാഫ് ആനുകാലികമാണ്. ആ. ഞങ്ങളുടെ നോൺ-പീരിയോഡിസിറ്റി ആവശ്യകത അത്തരത്തിലുള്ള N ഇല്ല എന്നതിന് തുല്യമാണ്, അല്ലെങ്കിൽ മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, ഗ്രാഫിലെ എല്ലാ സൈക്കിളുകളുടെയും ദൈർഘ്യത്തിന്റെ ഏറ്റവും വലിയ പൊതു വിഭജനം 1 ആണ്. ഈ അവസ്ഥയെ തൃപ്തിപ്പെടുത്തുന്ന ഏതൊരു ഗ്രാഫിനും ഒരു ഉണ്ടെന്ന് ഞങ്ങൾ തെളിയിക്കും സമന്വയിപ്പിക്കുന്ന കളറിംഗ്.

"ഏത് ചക്രത്തിന്റെയും ദൈർഘ്യം വിഭജിക്കപ്പെടുന്ന N>1 ഉണ്ട്" എന്ന അവസ്ഥയ്ക്ക് ആനുകാലികത തുല്യമാണെന്ന് തെളിയിക്കുന്നത് ഒരു ദിശയിൽ നിസ്സാരവും മറ്റേ ദിശയിൽ എളുപ്പവുമാണ്. നിങ്ങൾ ഇത് വിശ്വാസത്തിൽ എടുക്കാൻ തയ്യാറാണെങ്കിൽ, ഈ ഖണ്ഡികയുടെ ബാക്കി ഭാഗം നിങ്ങൾക്ക് എളുപ്പത്തിൽ ഒഴിവാക്കാം; ബാക്കിയുള്ള തെളിവുകൾക്ക് ഇത് പ്രശ്നമല്ല. ഗ്രാഫ് ആനുകാലികമാണെങ്കിൽ, അതായത്. ലംബങ്ങളെ V 1, V 2, ... V n സെറ്റുകളായി വിഭജിക്കാൻ കഴിയും, അങ്ങനെ അരികുകൾ അവയ്ക്കിടയിൽ ഒരു സൈക്കിളിലൂടെ പോകുന്നു, അപ്പോൾ ഏത് സൈക്കിളിന്റെയും ദൈർഘ്യം n കൊണ്ട് ഹരിക്കപ്പെടണം എന്നത് വ്യക്തമാണ്, അതായത്. പുതിയ വ്യവസ്ഥ തൃപ്തികരമാണ്. ഇതൊരു നിസ്സാരമായ ദിശയാണ്, എന്നാൽ പകരം വയ്ക്കുന്നതിന് ഞങ്ങൾക്ക് രണ്ടാമത്തെ ദിശ മാത്രമേ ആവശ്യമുള്ളൂ. ഏത് സൈക്കിളിന്റെയും ദൈർഘ്യം വിഭജിക്കപ്പെടുന്ന N>1 ഉണ്ടെന്ന് കരുതുക. r എന്ന ശീർഷകത്തിലെ റൂട്ട് ഉപയോഗിച്ച് നമുക്ക് നമ്മുടെ ഗ്രാഫിൽ കുറച്ച് ഡയറക്‌ട് സ്‌പാനിംഗ് ട്രീ നിർമ്മിക്കാം. ഏത് ശീർഷകത്തിലേക്കും x ഈ മരത്തിൽ l(x) ന്റെ വേരിൽ നിന്ന് ആരംഭിക്കുന്ന ഒരു റൂട്ട് ഉണ്ട്. ഗ്രാഫിലെ ഏത് എഡ്ജിനും p-->q എന്നത് l(q) = l(p) + 1 (mod N) എന്ന് ഞങ്ങൾ ഇപ്പോൾ അവകാശപ്പെടുന്നു. ഈ പ്രസ്താവന ശരിയാണെങ്കിൽ, നമുക്ക് എല്ലാ വെർട്ടീസുകളും l(x) mod N അനുസരിച്ച് V i സെറ്റുകളായി വിഭജിക്കാം, ഗ്രാഫ് ആനുകാലികമായിരിക്കും. എന്തുകൊണ്ടാണ് ഈ പ്രസ്താവന ശരിയാകുന്നത്? p-->q പരന്നുകിടക്കുന്ന ട്രീയുടെ ഭാഗമാണെങ്കിൽ, ഇത് വ്യക്തമാണ്, കാരണം ലളിതമായി l(q) = l(p) + 1. ഇത് അങ്ങനെയല്ലെങ്കിൽ, r എന്ന റൂട്ടിൽ നിന്ന് ഞങ്ങൾ റൂട്ടുകൾ എഴുതുന്നു. p,q എന്നീ ശീർഷകങ്ങൾ R p, Rq എന്നിങ്ങനെ. ഗ്രാഫിൽ q-ൽ നിന്ന് r-ലേക്കുള്ള ഒരു റൂട്ടിനെ R r സൂചിപ്പിക്കട്ടെ (ഗ്രാഫ് ബന്ധിപ്പിച്ചിരിക്കുന്നു, അതിനാൽ അത് നിലവിലുണ്ട്). അപ്പോൾ നമുക്ക് രണ്ട് സൈക്കിളുകൾ എഴുതാം: R p p-->q R r , R q R r . വ്യവസ്ഥ അനുസരിച്ച്, ഈ സൈക്കിളുകളുടെ ദൈർഘ്യം N കൊണ്ട് ഹരിക്കുന്നു, മൊത്തം മൂല്യങ്ങൾ കുറയ്ക്കുകയും കുറയ്ക്കുകയും ചെയ്യുന്നു, നമുക്ക് l(p)+1 = l(q) mod N ലഭിക്കും, അതാണ് തെളിയിക്കേണ്ടത്.

സുസ്ഥിരമായ സൗഹൃദവും പ്രേരണയും

ഒരു ഗ്രാഫ് G യുടെ ഒരു നിശ്ചിത കളറിംഗ് നൽകട്ടെ, രണ്ട് ശീർഷകങ്ങളെ p, q ഫ്രണ്ട്സ് എന്ന് വിളിക്കാം, ഏതെങ്കിലും വാക്ക് അവയെ ഒരേ ശീർഷത്തിലേക്ക് കൊണ്ടുവരുന്നുവെങ്കിൽ: pw = qw. “ഒരിക്കലും ഒരുമിച്ചില്ലെങ്കിൽ” നമുക്ക് p,q ശത്രുക്കളെ വിളിക്കാം. ഏതെങ്കിലും വാക്ക് എക്സിക്യൂട്ട് ചെയ്തതിന് ശേഷം അവർ സുഹൃത്തുക്കളായി തുടരുകയാണെങ്കിൽ p,q സ്ഥിര സുഹൃത്തുക്കളെ വിളിക്കാം: pw qw യുടെ അതേ ശീർഷകത്തിലേക്ക് വരില്ല, പക്ഷേ കുറച്ച് കഴിഞ്ഞ് w" അത് വരാം. സ്ഥിരതയുള്ള സുഹൃത്തുക്കൾ ഒരിക്കലും ശത്രുക്കളാകില്ല.

ലംബങ്ങൾ തമ്മിലുള്ള സ്ഥിരത ബന്ധം, ഒന്നാമതായി, തുല്യതയാണ് (ഇത് റിഫ്ലെക്‌സീവ്, സമമിതി, ട്രാൻസിറ്റീവ് ആണ്), രണ്ടാമതായി ഗ്രാഫിന്റെ ഘടനയാൽ സംരക്ഷിക്കപ്പെടുന്നു: p, q സ്ഥിരതയുള്ള സുഹൃത്തുക്കളാണെങ്കിൽ, p ഒരു അരികിൽ p, q മുതൽ q വരെ ബന്ധിപ്പിച്ചിരിക്കുന്നു. ", ഈ അരികുകൾ ഒരേ നിറം, പിന്നെ p", q" എന്നിവയും സ്ഥിരമായ സുഹൃത്തുക്കളാണ്. സുസ്ഥിരമായ സൗഹൃദം എന്നാണ് ഇതിനർത്ഥം പൊരുത്തംകൂടാതെ വിഭജിക്കാവുന്നതാണ്: ഒരു പുതിയ ഗ്രാഫ് G സൃഷ്ടിക്കുക", അതിന്റെ ലംബങ്ങൾ G-യിലെ സുസ്ഥിര സൗഹൃദങ്ങൾക്കുള്ള തുല്യതാ ക്ലാസുകളായിരിക്കും. G-യിൽ ഒരു സ്ഥിരതയുള്ള ജോഡി എങ്കിലും ഉണ്ടെങ്കിൽ, G" G-യെക്കാൾ ചെറുതായിരിക്കും. മാത്രമല്ല, ഒറിജിനൽ ഗ്രാഫിൽ ഓരോ ലംബങ്ങളിൽ നിന്നുമുള്ള G യിൽ d അരികുകൾ ഉണ്ടായിരുന്നു, അപ്പോൾ G" യിൽ ഇത് സംഭവിക്കും. ഉദാഹരണത്തിന്, P എന്നത് പുതിയ ഗ്രാഫിന്റെ ഒരു ശീർഷം ആണെങ്കിൽ, യഥാർത്ഥ ലംബങ്ങളായ p1, p2... , കൂടാതെ α എന്നത് ഏത് നിറമാണ്, പിന്നെ അരികുകൾ p1--α--> q1, p2---α-->q2, മുതലായവ. എല്ലാം q1, q2... എന്നീ ശീർഷങ്ങളിലേക്ക് നയിക്കുന്നു, അവ പരസ്പരം സുസ്ഥിരമായ സൗഹൃദത്തിലാണ്. , അതിനാൽ ഒരു പുതിയ ശീർഷം Q-ൽ കിടക്കുക, അങ്ങനെ ഈ അരികുകളെല്ലാം ഒരു പുതിയ എഡ്ജ് P --α-->Q ആയി മാറുന്നു. അങ്ങനെ ഓരോ d നിറങ്ങൾക്കും.

മാത്രമല്ല, G ആനുകാലികമല്ലായിരുന്നുവെങ്കിൽ, G" യും അങ്ങനെയാണ്. എല്ലാത്തിനുമുപരി - ആവർത്തനത്തിന്റെ ഞങ്ങളുടെ ഇതര നിർവചനം ഉപയോഗിച്ച് - G-യിലെ ഏത് സൈക്കിളും G-യിലെ ഒരു ചക്രമായി മാറുന്നു", അതിനാൽ G-യിലെ എല്ലാ സൈക്കിളുകളുടെ നീളവും n > 1 കൊണ്ട് ഹരിച്ചാൽ, G-യിലെ എല്ലാ ചക്രങ്ങൾക്കും ഇതുതന്നെയാണ് ശരി. അതിനാൽ G" യുടെ ആവർത്തനത G യുടെ ആവർത്തനത്തെ സൂചിപ്പിക്കുന്നു.

G-യിൽ ഒരു സമന്വയിപ്പിക്കുന്ന കളറിംഗ് കണ്ടെത്താൻ ഞങ്ങൾക്ക് കഴിഞ്ഞു എന്ന് കരുതുക. ഞങ്ങൾ ആരംഭിച്ച കളറിംഗിന് പകരം ഇത് ഇപ്പോൾ G-യിൽ ഉപയോഗിക്കാം: P-->q എന്ന എഡ്ജ് P- യുടെ പുതിയ വർണ്ണത്തിനനുസരിച്ച് ഏത് അരികിലും ഒരു പുതിയ നിറം ലഭിക്കും. -->Q. ഇത് കുറച്ചുകൂടി കൃത്യമായിരിക്കണം: ഗ്രാഫ് G യുടെ ഓരോ ശീർഷകത്തിലും P എല്ലാ നിറങ്ങളുടെയും ചില ക്രമപ്പെടുത്തലിലൂടെ ഒരു പുതിയ കളറിംഗ് നൽകുന്നു π P: α നിറമുള്ള ഒരു അരികിൽ ഒരു പുതിയ നിറം π ലഭിക്കുന്നു പി (α). യഥാർത്ഥ ഗ്രാഫ് ജിയിൽ, സ്റ്റെബിലിറ്റി ക്ലാസ് പിയിൽ നിന്നുള്ള ഓരോ ശീർഷം p ലും അതിന്റെ അരികുകൾ വീണ്ടും വർണ്ണിക്കാൻ നമ്മൾ അതേ പെർമ്യൂട്ടേഷൻ π P ഉപയോഗിക്കുന്നു. പൊതുവായി പറഞ്ഞാൽ, ഗ്രാഫ് ജിയുടെ ഒരു പുതിയ കളറിംഗ് "സൗഹൃദം", "ശത്രു", "സ്ഥിരത" എന്നിവയുടെ ചില പുതിയ ആശയങ്ങളെ നിർവചിക്കുന്നു, അവ യഥാർത്ഥമായവയ്ക്ക് സമാനമല്ല. എന്നിരുന്നാലും, പഴയ കളറിംഗിൽ p, q എന്നീ രണ്ട് ശീർഷകങ്ങൾ സ്ഥിരമായ സുഹൃത്തുക്കളായിരുന്നുവെങ്കിൽ - അവർ ഒരേ ക്ലാസിൽ പെട്ടവരായിരുന്നു - അവർ പുതിയതിൽ സ്ഥിരമായ സുഹൃത്തുക്കളായി തുടരും. കാരണം, p,q ഒരു ശീർഷത്തിലേക്ക് കൊണ്ടുവരുന്ന ഏത് ശ്രേണിയും പഴയ കളറിംഗിൽ നിന്ന് പുതിയതിലേക്കോ തിരിച്ചും "വിവർത്തനം" ചെയ്യാവുന്നതാണ്. പഴയ കളറിംഗിൽ p,q സ്ഥിരതയുള്ളതിനാൽ "എല്ലാ വഴികളിലും" തുടരുന്നതിനാൽ, p,q മുതൽ സാധാരണ ശീർഷം വരെയുള്ള റോഡിലെ ഓരോ ഇന്റർമീഡിയറ്റ് ജോഡി ശീർഷകങ്ങളും p n , q n എന്നിവ സ്ഥിരമായിരിക്കും, അതായത്. P n എന്ന ഒരു ശീർഷത്തിനുള്ളിൽ കിടക്കുക, അതിനാൽ അതേ ക്രമമാറ്റം π P n സ്വീകരിക്കുക.

പുതിയ കളറിംഗ് G" യ്‌ക്കായി സമന്വയിപ്പിക്കുന്നു, അതായത് ചില സീക്വൻസ് w എല്ലാ ലംബങ്ങളെയും ഒരു ശീർഷം P ലേക്ക് കൊണ്ടുവരുന്നു. നമ്മൾ ഇപ്പോൾ G-യിലെ പുതിയ കളറിംഗിൽ w പ്രയോഗിക്കുകയാണെങ്കിൽ, എല്ലാ ശീർഷങ്ങളും "P ഉള്ളിൽ" എവിടെയെങ്കിലും ഒത്തുചേരും. മുകളിൽ പറഞ്ഞതുപോലെ, P ക്ലാസിലെ എല്ലാ ലംബങ്ങളും പുതിയ കളറിംഗിൽ സ്ഥിരമായി നിലകൊള്ളുന്നു, അതിനർത്ഥം നമുക്ക് ഇപ്പോൾ w തുടരാം, എല്ലാം ഒരു ശീർഷകം G ആയി സംയോജിക്കുന്നത് വരെ ശേഷിക്കുന്ന പ്രത്യേക ജോഡി ലംബങ്ങളെ വീണ്ടും വീണ്ടും ഒരുമിച്ച് കൊണ്ടുവരാം. അങ്ങനെ, പുതിയ കളറിംഗ് സമന്വയിപ്പിക്കുന്നു ജി.

ഇതിൽ നിന്നെല്ലാം, സിദ്ധാന്തം തെളിയിക്കാൻ, വ്യവസ്ഥകൾ പാലിക്കുന്ന ഏതൊരു ഗ്രാഫിലും സ്ഥിരതയുള്ള ഒരു ജോടി സുഹൃത്തുക്കളുള്ള ഒരു കളറിംഗ് ഉണ്ടെന്ന് തെളിയിക്കാൻ ഇത് മതിയാകും. കാരണം ഗ്രാഫ് ജിയിൽ നിന്ന് നമുക്ക് ചെറിയ വലിപ്പത്തിലുള്ള ഗ്രാഫ് ജിയിലേക്ക് പോകാം, കൂടാതെ ഇത് എല്ലാ വ്യവസ്ഥകളും പാലിക്കുന്നു. ഒരു ഇൻഡക്റ്റീവ് ആർഗ്യുമെന്റ് ഉപയോഗിച്ച്, ചെറിയ വലുപ്പത്തിലുള്ള ഗ്രാഫുകൾക്ക് പ്രശ്നം ഇതിനകം പരിഹരിച്ചുവെന്ന് നമുക്ക് അനുമാനിക്കാം, തുടർന്ന് സമന്വയിപ്പിക്കുന്ന കളറിംഗ് ജിക്ക്" എന്നതും ജിക്ക് വേണ്ടി സമന്വയിപ്പിക്കും.

ക്ലിക്കുകളും പരമാവധി സെറ്റുകളും

ഒരു ഗ്രാഫിലെയും w എന്ന വാക്കിലെയും ലംബങ്ങളുടെ ഏതെങ്കിലും ഉപഗണത്തിന്, A യുടെ എല്ലാ ശീർഷകങ്ങളിൽ നിന്നും ആരംഭിച്ച് w എന്ന വാക്കിന് ശേഷം നമ്മൾ എത്തിച്ചേരുന്ന ലംബങ്ങളുടെ കൂട്ടത്തെ Aw സൂചിപ്പിക്കുന്നു. ഗ്രാഫിന്റെ എല്ലാ ശീർഷകങ്ങളിൽ നിന്നും ഞങ്ങൾ ആരംഭിക്കുകയാണെങ്കിൽ, ഞങ്ങൾ ഇത് Gw കൊണ്ട് സൂചിപ്പിക്കുന്നു. ഈ നൊട്ടേഷനിൽ, ഒരു സിൻക്രൊണൈസിംഗ് കളറിംഗ് അർത്ഥമാക്കുന്നത്, Gw എന്നത് ഒരു മൂലകത്തിന്റെ ഒരു കൂട്ടമാണ്.

A എന്ന ശീർഷകങ്ങളുടെ ഗണത്തിന് ചില w എന്നതിന് Gw എന്ന രൂപമുണ്ടെങ്കിൽ, കൂടാതെ, A-യിലെ ഏതെങ്കിലും രണ്ട് ലംബങ്ങൾ ശത്രുക്കളാണ്, അതായത്. ഒരിക്കലും ഒത്തുചേരില്ല, നമുക്ക് എ എന്ന് വിളിക്കാം കൂട്ടം. ക്ലിക്കുകൾ നിലവിലുണ്ട്, കാരണം നമുക്ക് എല്ലായ്‌പ്പോഴും മുഴുവൻ ജിയിൽ നിന്ന് ആരംഭിക്കാനും ഒരു ജോടി ഫ്രണ്ട് വെർട്ടിസുകൾ എടുക്കാനും അവയെ ബന്ധിപ്പിക്കുന്ന w യിലൂടെ സഞ്ചരിക്കാനും ലംബങ്ങളുടെ എണ്ണം ഒന്നായി കുറയ്ക്കാനും കഴിയും; ശത്രുക്കൾ മാത്രം നിലനിൽക്കുന്നതുവരെ അല്ലെങ്കിൽ ഒരു ശീർഷകം മാത്രം അവശേഷിക്കുന്നത് വരെ ഈ രീതിയിൽ തുടരുക - ഈ സാഹചര്യത്തിൽ ഒരു കൂട്ടം, നിസ്സാരം.

A ഒരു കൂട്ടം ആണെങ്കിൽ, ഏത് വാക്കിനും w Aw എന്നത് ഒരു കൂട്ടമാണ്; ശത്രുക്കൾ ശത്രുക്കളായി തുടരുന്നതിനാൽ ഇത് വ്യക്തമാണ്. x എന്നത് ഗ്രാഫിന്റെ ഏതെങ്കിലും ശീർഷകമാണെങ്കിൽ, x ഉൾപ്പെടെ ഒരു ക്ലിക് ഉണ്ട്. ചില തരത്തിലുള്ള ക്ലിക് എ ഉണ്ടെന്ന വസ്തുതയിൽ നിന്ന് ഇത് പിന്തുടരുന്നു (മുമ്പത്തെ ഖണ്ഡിക കാണുക); p എന്നത് അതിൽ ഒരു ശീർഷകമാണെങ്കിൽ, p-ൽ നിന്ന് x-ലേക്ക് നയിക്കുന്ന ഒരു വാക്ക് w ഉണ്ട്, കാരണം ബന്ധിപ്പിച്ച ഗ്രാഫ്; അപ്പോൾ Aw എന്നത് x ഉൾപ്പെടെയുള്ള ഒരു സംഘമാണ്.

സ്ഥിരതയുള്ള സുഹൃത്തുക്കളുമായി ഒരു കളറിംഗ് ഉണ്ടെന്ന് തെളിയിക്കാൻ ക്ലിക്കുകൾ ഞങ്ങളെ സഹായിക്കും - മുമ്പത്തെ വിഭാഗം അനുസരിച്ച്, സിദ്ധാന്തം തെളിയിക്കാൻ ഇത് മതിയാകും. ഈ വിഭാഗത്തിലുടനീളം, A, B എന്നീ രണ്ട് ക്ലിക്കുകൾ ഉണ്ടെങ്കിൽ, അവയിലെ എല്ലാ ശീർഷകങ്ങളും A യിലെ ഒന്ന്, B യിൽ ഒന്ന് ഒഴികെ പൊതുവായതാണ്, ഈ രണ്ട് ശീർഷങ്ങളും സ്ഥിരമായ സുഹൃത്തുക്കളാണെന്ന് ഞങ്ങൾ തെളിയിക്കും. അങ്ങനെ, ക്ലിക്കുകൾ എ, ബി എന്നിവ അടങ്ങിയ കളറിംഗ് കണ്ടെത്തുന്നതിലേക്ക് പ്രശ്നം കുറയുന്നു.

ക്ലിക്കുകൾ എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് നന്നായി മനസിലാക്കാൻ, ഗ്രാഫിലെ വെർട്ടീസുകൾക്ക് ഭാരം നൽകുന്നത് ഉപയോഗപ്രദമാണ്. ഓരോ ശീർഷം x നും ഒരു പോസിറ്റീവ് ഭാരം w(x) നൽകാനുള്ള ഒരു മാർഗം നമുക്കുണ്ടെന്ന് കാണിക്കാം, ഏതെങ്കിലും ശീർഷം x ആണെങ്കിൽ x-ൽ അരികുകളുള്ള എല്ലാ ലംബങ്ങളുടെയും ഭാരങ്ങൾ സംഗ്രഹിക്കുക, അപ്പോൾ നമുക്ക് d*w(x) ലഭിക്കുന്നു, ഇവിടെ d എന്നത് ഓരോ ശീർഷത്തിൽ നിന്നുമുള്ള അരികുകളുടെ എണ്ണമാണ്. ഇത് ലീനിയർ ബീജഗണിതത്തിൽ നിന്നാണ് പിന്തുടരുന്നത്, നിങ്ങൾക്ക് ഈജൻവാല്യൂ എന്താണെന്ന് അറിയില്ലെങ്കിൽ, ഈ ഖണ്ഡികയുടെ ബാക്കി ഭാഗം ഒഴിവാക്കി അത്തരം w(x) ന്റെ അസ്തിത്വം നിസ്സാരമായി കണക്കാക്കുക. M എന്നത് ഒരു ഗ്രാഫ് G യുടെ മാട്രിക്സ് ആണെങ്കിൽ (സെൽ (i,j) ഒരു എഡ്ജ് ഉണ്ടെങ്കിൽ 1 ആണ്, i-->j ഉണ്ടെങ്കിൽ 0 ആണ്, അങ്ങനെ ഒരു എഡ്ജ് ഇല്ലെങ്കിൽ 0), പിന്നെ w(x), ഞാൻ വിവരിച്ചത് പോലെ, ഈജൻ വെക്‌ടറിന്റെ മൂലകങ്ങളാണ് ഇടത്തെഈ മാട്രിക്‌സിന് ഈജൻവാല്യൂ d ഉണ്ട്. d ഒരു ഈജൻവാല്യൂ ആയതിനാൽ അത്തരമൊരു വെക്റ്റർ ഉണ്ടെന്ന് നമുക്കറിയാം: അതിന് നിസ്സാരമായ ഒരു ഈജൻ വെക്റ്റർ ഉണ്ട് വലതുവശത്ത്(1,1,....1) - ഓരോ ശീർഷകത്തിൽ നിന്നും കൃത്യമായി d അരികുകൾ വരുന്നു എന്ന വസ്തുതയിൽ നിന്ന് ഇത് ഉടനടി പിന്തുടരുന്നു.

A എന്നത് ഏതെങ്കിലും ശീർഷകങ്ങളാണെങ്കിൽ, w(A) എന്നത് A യിൽ നിന്നുള്ള എല്ലാ ശീർഷകങ്ങളുടെയും ഭാരങ്ങളുടെ ആകെത്തുകയെ സൂചിപ്പിക്കുന്നു; ഒപ്പം w(G) എന്നത് ഗ്രാഫിലെ എല്ലാ ലംബങ്ങളുടെയും ഭാരങ്ങളുടെ ആകെത്തുകയാണ്. കൂടാതെ, s എന്നത് ഏതെങ്കിലും പദമാണെങ്കിൽ, നിങ്ങൾ "എതിർ ദിശയിലേക്ക്" പോകുകയാണെങ്കിൽ, ഓരോ ഘട്ടത്തിലും ഓരോ ശീർഷകവും ആ ശീർഷകങ്ങൾ ഉപയോഗിച്ച് (എന്തെങ്കിലും ഉണ്ടെങ്കിൽ) നിങ്ങൾ എയിൽ നിന്ന് വരുന്ന ശീർഷകങ്ങളുടെ ഗണത്തെ As -1 സൂചിപ്പിക്കട്ടെ. ഉചിതമായ നിറത്തിൽ അവളുടെ അടുത്തേക്ക് പോകുക.

നമുക്ക് ഇപ്പോൾ ഒരു ബിന്ദുവിലേക്ക് കൊണ്ടുവരാൻ കഴിയുന്ന എല്ലാ സെറ്റ് ലംബങ്ങളും പരിഗണിക്കാം, അതായത്. ചിലർക്ക് w Aw-ൽ ഒരു ശീർഷകം മാത്രമേ ഉള്ളൂ. അത്തരത്തിലുള്ള എല്ലാ സെറ്റുകളിലും പരമാവധി ഭാരം w(A) ഉള്ള സെറ്റുകളെ മാക്സിമൽ സെറ്റുകൾ എന്ന് വിളിക്കും. കളറിംഗ് സമന്വയിപ്പിക്കുകയാണെങ്കിൽ, മുഴുവൻ ഗ്രാഫ് ജിയും ഒരു പരമാവധി സെറ്റാണ് (അതുല്യം), അല്ലാത്തപക്ഷം അത് അങ്ങനെയല്ല.

A എന്നത് ഏതെങ്കിലും ശീർഷകങ്ങളാണെങ്കിൽ, എല്ലാ d വർണ്ണങ്ങളിലും α പ്രവർത്തിക്കുന്ന എല്ലാ w (Aα -1) യുടെയും ആകെത്തുക d*w(A) ന് തുല്യമാണ് - ഇത് കേവലം ഭാരത്തിന്റെ പ്രധാന ഗുണത്തിന്റെ സാമാന്യവൽക്കരണമാണ്. ഒരു ശീർഷകം A ലംബങ്ങളുടെ ഗണത്തിലേക്ക്. കൂടാതെ, ഈ സാഹചര്യത്തിൽ A ഒരു പരമാവധി ഗണമാണെങ്കിൽ, w(Aα -1) ഓരോന്നും w(A) എന്നതിനേക്കാൾ വലുതായിരിക്കരുത്, കാരണം ഈ ഗണങ്ങളും ഒരു ശീർഷത്തിലേക്ക് ചുരുക്കിയിരിക്കുന്നു. . ഈ ഭാരങ്ങളുടെ ആകെത്തുക d*w(A) ന് തുല്യമായതിനാൽ, അവ ഓരോന്നും w (A) ന് തുല്യമാണെന്നും ഈ ഗണങ്ങളെല്ലാം പരമാവധി ആണെന്നും മാറുന്നു. അത് ഉടനടി പിന്തുടരുന്നു, എ പരമാവധി ആണെങ്കിൽ, ഏത് പദത്തിനും w -1 ആണ് പരമാവധി.

മാക്‌സിമൽ സെറ്റുകൾ ഉപയോഗപ്രദമാണ്, കാരണം അവയുടെ വ്യതിരിക്ത സംഭവങ്ങൾ ഗ്രാഫിനെ മുഴുവൻ ഉൾക്കൊള്ളാൻ കഴിയും. നമുക്ക് തെളിയിക്കാം.

നമുക്ക് A 1 ...A n , ജോഡികളായി വിഭജിച്ച്, ഒരേ പദത്താൽ a 1 ...a n എന്ന ഒറ്റ ശീർഷങ്ങളായി ചുരുക്കിയ ഒരു കൂട്ടം A 1 ...A n ഉണ്ടാകട്ടെ (പ്രാരംഭ സന്ദർഭത്തിൽ n=1 ഉം ഒരെണ്ണവും മാത്രമേ ഉണ്ടാകൂ. സജ്ജമാക്കുക, അങ്ങനെ അത് ആരംഭിക്കാൻ എളുപ്പമാണ്). എല്ലാ a 1 ...a n ഉം പരസ്പരം വ്യത്യസ്‌തമാണെന്ന് വ്യക്തമാണ്, അല്ലാത്തപക്ഷം ഒരേ അന്തിമ ശീർഷമുള്ള മറ്റൊന്നിന്റെ മൂലകങ്ങൾ കാരണം പരമാവധി സെറ്റ് കൂടുതൽ വികസിപ്പിക്കാൻ കഴിയും. എല്ലാ A iയും ചേർന്ന് G യുടെ എല്ലാ ശീർഷകങ്ങളും ഇതുവരെ തീർന്നിട്ടില്ലെന്ന് കരുതുക, കൂടാതെ x എല്ലാ A i യുടെയും പുറത്തുള്ള ഒരു ശീർഷകം ആയിരിക്കട്ടെ. ഗ്രാഫ് ബന്ധിപ്പിച്ചിരിക്കുന്നതിനാൽ, 1 മുതൽ x വരെയുള്ള ചില റൂട്ട് h ഉണ്ട്. തുടർന്ന് n മാക്സിമൽ സെറ്റുകൾ A i h -1 w -1 whw എന്ന വാക്ക് അനുസരിച്ച് അന്തിമ ശീർഷങ്ങൾ a 1 ...a n ലേക്ക് പോകുന്നു, കൂടാതെ A 1 എന്ന മാക്സിമൽ സെറ്റ് ചില ശീർഷകങ്ങളിലേക്ക് പോകുന്നു Awhw = (Aw)hw = (a 1 h) w = xw. ഈ ശീർഷം xw എല്ലാ a 1 ...a n എന്നതിൽ നിന്നും വ്യത്യസ്തമായിരിക്കണം, കാരണം അല്ലാത്തപക്ഷം പരമാവധി സെറ്റ് A i ഒരു മൂലകം x ഉപയോഗിച്ച് ചേർക്കാം. ഈ n+1 സെറ്റുകളെല്ലാം - എല്ലാം A i h -1 w -1 പ്ലസ് A 1 - വ്യത്യസ്ത ശീർഷകങ്ങളിലേക്ക് whw യ്‌ക്കൊപ്പം പോകുന്നതിനാൽ, അവയെല്ലാം ജോടിയായി വിഭജിച്ചിരിക്കുന്നു. സെറ്റിന് പുറത്ത് ലംബങ്ങളൊന്നും അവശേഷിക്കുന്നില്ല വരെ ഞങ്ങൾ ഈ വിപുലീകരണം തുടരും.

അതിനാൽ നമുക്ക് മുഴുവൻ ഗ്രാഫ് ജിയും ഡിസ്ജോയിന്റ് മാക്സിമൽ സെറ്റുകൾ ഉപയോഗിച്ച് കവർ ചെയ്യാം. അവ പരമാവധി ആയതിനാൽ, അവയ്‌ക്കെല്ലാം ഒരേ മുഴുവൻ w max ഉണ്ട്, അതിനാൽ കവറേജിലെ അവയുടെ നമ്പർ N max = w(G)/w max ആണ്.

ഇപ്പോൾ ജോഡിവൈസ് ശത്രുക്കൾ അടങ്ങുന്ന ഏതെങ്കിലും സെറ്റ് എ പരിഗണിക്കുക. ഉദാഹരണത്തിന്, ഒരു കൂട്ടം അത്തരമൊരു സെറ്റിന്റെ ഒരു ഉദാഹരണമാണ് (കൂടാതെ Gw എന്ന രൂപവുമുണ്ട്). ഒരു പരമാവധി സെറ്റിൽ ഒരു ജോടി ശത്രുക്കളെ ഉൾക്കൊള്ളാൻ കഴിയില്ല, കാരണം അതിന് ഒത്തുചേരാൻ കഴിഞ്ഞില്ല. ഇതിനർത്ഥം N max maximal സെറ്റുകളുടെ ഒരു കവറിംഗിൽ, ഓരോന്നിലും പരമാവധി ഒരു അംഗം A അടങ്ങിയിരിക്കുന്നു, അതിനാൽ A യുടെ വലുപ്പം N max ആണ്. പ്രത്യേകിച്ചും, ഇത് ഏതൊരു സംഘത്തിന്റെയും വലുപ്പത്തിലുള്ള ഉയർന്ന പരിധിയാണ്.

A എന്നത് Gw എന്ന രൂപത്തിന്റെ ഒരു കൂട്ടം ആയിരിക്കട്ടെ, ഇവിടെ w എന്നത് ചില വാക്കാണ്. അപ്പോൾ G = Aw -1, അതനുസരിച്ച് w(G) എന്നത് w(aw -1) എന്ന തുകയ്ക്ക് തുല്യമാണ്, ഇവിടെ A യുടെ എല്ലാ ശീർഷകങ്ങളിലൂടെയും ഓടുന്നു. മുമ്പത്തെ ഖണ്ഡിക പ്രകാരം പദങ്ങളുടെ എണ്ണം, അതിൽ കൂടുതലല്ല. N max, കൂടാതെ ഓരോ സെറ്റ് aw -1 ഉം ഒരു പോയിന്റായി കുറയ്ക്കാൻ കഴിയും (ഒരു പോയിന്റിൽ w എന്ന വാക്കിനൊപ്പം), അതിനാൽ അതിന്റെ ഭാരം പരമാവധി w max-നേക്കാൾ കൂടുതലല്ല. മുഴുവൻ തുകയും w(G) = N max *w max ന് തുല്യമായതിനാൽ, പദങ്ങളുടെ എണ്ണം N max ന് തുല്യമാണെന്നും ഓരോ പദവും w max ന് കൃത്യമായും തുല്യമാണെന്നും ഞങ്ങൾ നിഗമനം ചെയ്യുന്നു. എല്ലാ ക്ലിക്കുകൾക്കും ഒരേ വലുപ്പമുണ്ടെന്ന് ഞങ്ങൾ തെളിയിച്ചിട്ടുണ്ട്: കൃത്യമായി N max ഘടകങ്ങൾ.

A, B എന്നീ രണ്ട് ക്ലിക്കുകൾ ഉണ്ടാകട്ടെ, A ഉള്ളിൽ ഒന്നൊഴികെ എല്ലാ ഘടകങ്ങളും B-യ്‌ക്ക് സാധാരണമാണ്: |A| - |A∩B| = 1.

എയും ബിയും ഒരേ വലുപ്പമായതിനാൽ, നമുക്കും |B| - |A∩B| = 1, അതായത്. A-യിലെ p എന്ന ശീർഷകം ഒഴികെ A, B എന്നിവയ്ക്ക് പൊതുവായ എല്ലാ ഘടകങ്ങളും ഉണ്ട്, B-യിലെ ഒരു ശീർഷകം q ഒഴികെ. ഇത് അങ്ങനെയല്ലെങ്കിൽ, w ചില വാക്ക് അവരെ ശത്രുക്കളാക്കുന്നു, അതായത്. pw, qw എന്നിവ ശത്രുക്കളാണ്. മുകളിൽ കാണിച്ചിരിക്കുന്നതുപോലെ, Aw, Bw എന്നിവയും ക്ലിക്കുകളാണ്, ശത്രുക്കളായ pw, qw എന്നിവ ഒഴികെ അവയ്ക്ക് വീണ്ടും എല്ലാ ഘടകങ്ങളും പൊതുവായി ഉണ്ടെന്ന് വ്യക്തമാണ്. അപ്പോൾ Aw ∪ Bw എന്നത് ജോഡിവൈസ് ശത്രുക്കളുടെ ഗണമാണ്. തീർച്ചയായും, അതിൽ Aw യുടെ എല്ലാ ഘടകങ്ങളും ജോടിയായി ശത്രുക്കളാണ്, കാരണം അത് ഒരു കൂട്ടമാണ്; Bw മൂലകങ്ങളുടെ കാര്യത്തിലും ഇതുതന്നെ സത്യമാണ്; പിന്നെ pw,qw എന്ന ജോഡി മാത്രം അവശേഷിച്ചു - ശത്രുക്കളും. എന്നാൽ ഈ സെറ്റിന് N max +1 ഘടകങ്ങളുണ്ട്, കൂടാതെ ഏത് ജോഡിവൈസ് ശത്രുക്കൾക്കും N max മൂലകങ്ങളേക്കാൾ കൂടുതൽ ഉണ്ടായിരിക്കാൻ കഴിയില്ലെന്ന് ഞങ്ങൾ മുകളിൽ കാണിച്ചു. ഇതൊരു വൈരുദ്ധ്യമാണ്, അതിനാൽ pw, qw എന്നിവ ഏതെങ്കിലും w യുടെ ശത്രുക്കളാകാൻ കഴിയില്ല. മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ, p, q എന്നിവ സ്ഥിരമായ സുഹൃത്തുക്കളാണ്.

സ്‌പാൻ ചെയ്യുന്ന ഗ്രാഫുകളും ക്ലിക്കുകളും

തന്നിരിക്കുന്ന ഗ്രാഫ് G-യിൽ നിന്ന് നമുക്ക് എല്ലാ ശീർഷകങ്ങളും എടുത്ത് ഓരോ ശീർഷത്തിൽ നിന്നും ഒരു ഔട്ട്‌ഗോയിംഗ് എഡ്ജ് മാത്രം തിരഞ്ഞെടുക്കുക. ഈ ചോയ്സ് ഒരു സബ്ഗ്രാഫ് നിർണ്ണയിക്കുന്നു, അതിനെ ഞങ്ങൾ വിളിക്കുന്നു പരന്നുകിടക്കുന്ന ഗ്രാഫ്(വിശാലമായ ഗ്രാഫ്). വ്യത്യസ്‌ത സ്‌പാനിംഗ് ഗ്രാഫുകൾ ധാരാളം ഉണ്ടാകാം, എന്നാൽ അവ എങ്ങനെയിരിക്കും എന്നതിനെക്കുറിച്ച് നമുക്ക് അൽപ്പം ചിന്തിക്കാം. ഒരു നിശ്ചിത സ്പാനിംഗ് ഗ്രാഫ് R ഉണ്ടായിരിക്കട്ടെ. അതിൽ ഏതെങ്കിലും ശീർഷം x എടുത്ത് അതിന്റെ അരികുകൾ പിന്തുടരാൻ തുടങ്ങിയാൽ, ഓരോ തവണയും നമുക്ക് ഒരൊറ്റ ചോയ്‌സ് ഉണ്ടായിരിക്കും, കാരണം R ൽ ഓരോ ശീർഷത്തിൽ നിന്നും ഒരു അഗ്രം മാത്രമേ പുറത്തുവരൂ, എത്രയും വേഗം അല്ലെങ്കിൽ പിന്നീട് ഞങ്ങൾ സൈക്കിൾ അടയ്ക്കും. ഒരുപക്ഷേ ഈ ചക്രം x-ൽ അടയ്ക്കില്ല, പക്ഷേ എവിടെയെങ്കിലും "കൂടുതൽ" അടയ്ക്കും - ഉദാഹരണത്തിന്, x-->y-->z-->s-->y. അപ്പോൾ ഈ ചക്രത്തിലേക്കുള്ള "വാൽ" x ൽ നിന്ന് നയിക്കും. നമ്മൾ മറ്റേതെങ്കിലും ശീർഷത്തിൽ നിന്ന് ആരംഭിക്കുകയാണെങ്കിൽ, തീർച്ചയായും നാമും ഒരു ചക്രത്തിൽ അവസാനിക്കും - ഇത് അല്ലെങ്കിൽ മറ്റേതെങ്കിലും. ഏതെങ്കിലും ശീർഷകം R ഒന്നുകിൽ ഒരു ചക്രത്തിൽ കിടക്കുന്നു (അതിൽ പലതും ഉണ്ടാകാം), അല്ലെങ്കിൽ ഒരു ചക്രത്തിലേക്ക് നയിക്കുന്ന "വാലിന്റെ" ഭാഗമാണ്. ഇതിനർത്ഥം R ഇതുപോലെ കാണപ്പെടുന്നു: ഒരു നിശ്ചിത എണ്ണം സൈക്കിളുകളും ഒരു നിശ്ചിത എണ്ണം "വിപരീത" മരങ്ങളും അവയിൽ നിർമ്മിച്ചിരിക്കുന്നു: ഓരോ മരവും ആരംഭിക്കുന്നില്ല, പക്ഷേ സൈക്കിളുകളിലൊന്നിൽ കിടക്കുന്ന "റൂട്ടിൽ" അവസാനിക്കുന്നു.

ഗ്രാഫിന്റെ ഓരോ ശീർഷകത്തിലേക്കും നമുക്ക് അസൈൻ ചെയ്യാം നില, തന്നിരിക്കുന്ന പരന്ന ഗ്രാഫിലെ സൈക്കിളിലേക്കുള്ള അതിന്റെ ദൂരത്തിന് അനുസൃതമായി R. സൈക്കിളിൽ കിടക്കുന്ന ലംബങ്ങൾക്ക് ലെവൽ 0 ഉണ്ട്, സൈക്കിളിൽ ഘടിപ്പിച്ചിരിക്കുന്ന മരത്തിൽ കിടക്കുന്ന ശീർഷങ്ങൾക്ക് അവയുടെ മരത്തിലെ “വേരിലേക്കുള്ള ദൂരത്തിന് തുല്യമായ ലെവൽ ലഭിക്കും. ” സൈക്കിളിൽ കിടക്കുന്നു. ഞങ്ങളുടെ ഗ്രാഫിന്റെ ചില ലംബങ്ങൾക്ക് പരമാവധി ലെവൽ L ഉണ്ട്. ഒരുപക്ഷേ അത് 0-ന് തുല്യമായിരിക്കാം - അതായത്. അവിടെ മരങ്ങളില്ല, സൈക്കിളുകൾ മാത്രം. ഒരുപക്ഷേ ഇത് പൂജ്യത്തേക്കാൾ വലുതായിരിക്കാം, ഈ പരമാവധി ലെവലിന്റെ ശീർഷങ്ങൾ എല്ലാത്തരം വ്യത്യസ്‌ത വൃക്ഷങ്ങളിലും, വ്യത്യസ്ത സൈക്കിളുകളുമായോ ഒന്നിലേക്കോ ബന്ധിപ്പിച്ചിരിക്കുന്നു.

അത്തരത്തിലുള്ള ഒരു സ്പാനിംഗ് ഗ്രാഫ് R തിരഞ്ഞെടുക്കാൻ ഞങ്ങൾ ആഗ്രഹിക്കുന്നു പരമാവധി ലെവലിന്റെ എല്ലാ ശീർഷകങ്ങളും ഒരേ മരത്തിൽ കിടക്കുന്നു. അവബോധപൂർവ്വം, ഇത് ചെയ്യാൻ കഴിയുമെന്ന് ഒരാൾക്ക് വിശ്വസിക്കാൻ കഴിയും, കാരണം ഇത് അങ്ങനെയല്ലെങ്കിൽ - ഉദാഹരണത്തിന്, അവ വ്യത്യസ്ത മരങ്ങളിൽ ചിതറിക്കിടക്കുന്നു - അപ്പോൾ ഒരാൾക്ക് അത്തരം പരമാവധി ശീർഷങ്ങളിൽ ഒന്ന് തിരഞ്ഞെടുത്ത് x അതിന്റെ അരികുകൾ R ലേക്ക് ഘടിപ്പിച്ച് അതിന്റെ ലെവൽ വർദ്ധിപ്പിക്കാൻ കഴിയും. x ലേക്ക്. അപ്പോൾ മറ്റേതെങ്കിലും വാരിയെല്ല് വലിച്ചെറിയേണ്ടിവരും, ഇത് മറ്റൊന്നിനും ദോഷം ചെയ്യില്ല എന്നത് ഒരു വസ്തുതയല്ല ... എന്നാൽ ഇതൊരു സാങ്കേതിക പ്രശ്നമാണ്, അത് പിന്നീട് ചർച്ചചെയ്യും. അവബോധപൂർവ്വം ഇത് വളരെ സങ്കീർണ്ണമായി തോന്നുന്നില്ലെന്ന് പറയാൻ ഞാൻ ശ്രമിക്കുന്നു.

തൽക്കാലം, നമുക്ക് R തിരഞ്ഞെടുക്കാം, അങ്ങനെ പരമാവധി ലെവലിന്റെ എല്ലാ ശീർഷകങ്ങളും ഒരേ മരത്തിൽ കിടക്കും. ഈ വൃക്ഷം നിസ്സാരമല്ലാത്തതാണെന്ന് കരുതപ്പെടുന്നു, അതായത്. പരമാവധി ലെവൽ L > 0. ഈ അനുമാനത്തെ അടിസ്ഥാനമാക്കി, ഞങ്ങൾ ഒരു കളറിംഗ് നിർമ്മിക്കും, അതിൽ മുൻ വിഭാഗത്തിന്റെ വ്യവസ്ഥകൾ പാലിക്കുന്ന A, B ക്ലിക്കുകൾ ഉണ്ട്, ഈ കളറിംഗിൽ സ്ഥിരതയുള്ള ഒരു ജോഡി ഉണ്ടെന്ന് ഇത് തെളിയിക്കും. സുഹൃത്തുക്കൾ.

കളറിംഗ് ഇപ്രകാരമായിരിക്കും: കുറച്ച് കളർ α തിരഞ്ഞെടുക്കുക, കൂടാതെ ഗ്രാഫിലെ എല്ലാ അരികുകളും ഈ നിറം ഉപയോഗിച്ച് കളർ ചെയ്യുക, കൂടാതെ ഗ്രാഫ് ജിയിലെ മറ്റെല്ലാ അരികുകളും മറ്റ് ചില നിറങ്ങൾ ഉപയോഗിച്ച് ഏതെങ്കിലും വിധത്തിൽ (ഒരു കളർ മാത്രമേ ഉള്ളൂവെങ്കിൽ, R ജിയുമായി യോജിക്കുന്നു, അതിനാൽ ഒരു പ്രശ്നവുമില്ല). അങ്ങനെ, α നിറം അടങ്ങിയ വാക്കുകൾ അവയുടെ മരങ്ങൾക്കൊപ്പം R ന്റെ ശീർഷകങ്ങളെ സൈക്കിളുകളിലേക്ക് "തള്ളുക", തുടർന്ന് അവയെ ചക്രങ്ങളിലൂടെ നയിക്കുക. ഈ വാക്കുകൾ മാത്രമേ നമുക്ക് ആവശ്യമുള്ളൂ.

x എന്നത് R-ലെ പരമാവധി ലെവൽ L ന്റെ ഏതെങ്കിലും ശീർഷകമായിരിക്കട്ടെ, കൂടാതെ K എന്നത് x ഉൾപ്പെടെയുള്ള ഏതെങ്കിലും ക്ലിക്കായിരിക്കട്ടെ; അങ്ങനെയൊരു സംഘം ഉണ്ടെന്ന് ഞങ്ങൾക്കറിയാം. പരമാവധി ലെവൽ L ന്റെ മറ്റേതെങ്കിലും ശീർഷകം K ന് ഉൾപ്പെടുത്താമോ? ഞങ്ങളുടെ അനുമാനമനുസരിച്ച്, അത്തരം എല്ലാ ശീർഷകങ്ങളും x ന്റെ അതേ മരത്തിലാണ്, അതായത് α L എന്ന വാക്ക് അവയെ x-ന്റെ അതേ സ്ഥലത്തേക്ക് കൊണ്ടുപോകുന്നു - അതായത്, സൈക്കിളിൽ കിടക്കുന്ന ഈ വൃക്ഷത്തിന്റെ വേരിലേക്ക്. ഇതിനർത്ഥം, അത്തരം എല്ലാ ശീർഷകങ്ങളും x ന്റെ സുഹൃത്തുക്കളാണെന്നും അതിനാൽ അതേ ഗ്രൂപ്പിൽ കിടക്കാൻ കഴിയില്ലെന്നും ആണ്. അതിനാൽ, x കൂടാതെ, K ന് താഴ്ന്ന നിലയിലുള്ള ശീർഷകങ്ങൾ മാത്രമേ ഉൾപ്പെടുത്താൻ കഴിയൂ.

A = Kα L-1 എന്ന സെറ്റ് നോക്കാം. ഇതും ഒരു കൂട്ടമാണ്, അതിൽ x ഒഴികെയുള്ള എല്ലാ ശീർഷകങ്ങളും R-ൽ ഒരുതരം സൈക്കിളിൽ എത്തിയിരിക്കുന്നു, കാരണം x ഒഴികെ A യുടെ എല്ലാ ശീർഷകങ്ങളും L-നേക്കാൾ കുറവാണ്. സൈക്കിളിന് പുറത്ത് x മാത്രമേ അവശേഷിക്കുന്നുള്ളൂ. സൈക്കിളിൽ അതിന്റെ റൂട്ടിലേക്ക് കൃത്യമായി 1 ദൂരം. ഇനി R-ലെ എല്ലാ സൈക്കിൾ ദൈർഘ്യങ്ങളുടെയും ഗുണിതമായ m എന്ന സംഖ്യ എടുക്കാം - ഉദാഹരണത്തിന്, എല്ലാ സൈക്കിൾ ദൈർഘ്യങ്ങളുടെയും ഉൽപ്പന്നം. m ന് അത്തരമൊരു സവിശേഷതയുണ്ട്, ശീർഷകം y R-ൽ ഒരു ചക്രത്തിലാണെങ്കിൽ, α m എന്ന വാക്ക് അതിനെ അതിന്റെ സ്ഥാനത്തേക്ക് തിരികെ നൽകുന്നു: yα m = y. നമുക്ക് B = Aα m എന്ന ക്ലിക്കിലേക്ക് നോക്കാം. x ഒഴികെയുള്ള A യുടെ എല്ലാ ശീർഷകങ്ങളും സൈക്കിളുകളിൽ കിടക്കുന്നു, അതിനാൽ B-യിൽ അവശേഷിച്ചു; x മാത്രം ഒടുവിൽ അതിന്റെ ചക്രത്തിൽ പ്രവേശിച്ച് അവിടെ എവിടെയോ സ്ഥിരതാമസമാക്കി. ഇതിനർത്ഥം A, B എന്നിവയുടെ കവലയിൽ A യുടെ എല്ലാ ശീർഷകങ്ങളും ഒന്നൊഴികെ: |A| - |A∩B| = 1. എന്നാൽ ഇത് അർത്ഥമാക്കുന്നത്, മുമ്പത്തെ വിഭാഗം അനുസരിച്ച്, ഞങ്ങളുടെ കളറിംഗിന് സ്ഥിരതയുള്ള ഒരു ജോഡി ഉണ്ടെന്നാണ്, അതാണ് ഞങ്ങൾ തെളിയിക്കേണ്ടത്.

പരമാവധി ലെവൽ നിർമ്മിക്കുന്നു.

ഒരു സ്പാനിംഗ് ഗ്രാഫ് R തിരഞ്ഞെടുക്കുന്നത് എല്ലായ്‌പ്പോഴും സാധ്യമാണെന്ന് തെളിയിക്കാൻ ഇത് ശേഷിക്കുന്നു, അതായത് അതിന് നിസ്സാരമായ പരമാവധി ലെവൽ L > 0 ഉണ്ട്, ഈ ലെവലിന്റെ എല്ലാ ശീർഷകങ്ങളും ഒരേ മരത്തിൽ കിടക്കുന്നു.

ഈ തെളിവിന്റെ ഒരു ഭാഗം തികച്ചും വിരസവും സാങ്കേതികവുമായ ലെമ്മയാണ്, അത് ഞാൻ വായിക്കുകയും പരിശോധിക്കുകയും ചെയ്തു, പക്ഷേ ഞാൻ അത് ആവർത്തിക്കില്ല, താൽപ്പര്യമുള്ളവർക്കായി ഇത് ലേഖനത്തിൽ എവിടെയാണെന്ന് ഞാൻ പറയാം. എന്നാൽ ഈ ലെമ്മയിൽ എങ്ങനെ എത്തിച്ചേരാമെന്ന് ഞാൻ നിങ്ങളോട് പറയും.

നമുക്ക് ഗ്രാഫ് G-യിൽ ചുമത്താൻ കഴിയുന്ന രണ്ട് നിയന്ത്രണങ്ങൾ ആവശ്യമാണ്. ആദ്യം, G-ന് ലൂപ്പുകളില്ലെന്ന് പറയാം, അതായത്. ഒരു ശീർഷത്തിൽ നിന്ന് അതേ ശീർഷത്തിലേക്കുള്ള അരികുകൾ. ഗ്രാഫിൽ ഒരു ലൂപ്പ് ഉണ്ടെങ്കിൽ, മറ്റൊരു രീതിയിൽ സമന്വയിപ്പിക്കുന്ന കളറിംഗ് കണ്ടെത്തുന്നത് വളരെ എളുപ്പമാണ് എന്നതാണ് കാര്യം. നമുക്ക് ഈ ലൂപ്പിന് കുറച്ച് കളർ α നൽകാം, തുടർന്ന്, ഈ ശീർഷത്തിൽ നിന്ന് "അമ്പുകൾക്ക് എതിരായി" വിപരീത ദിശയിലേക്ക് പോയി, അരികുകൾക്ക് നിറം നൽകുക, അങ്ങനെ നിറം α എല്ലായ്പ്പോഴും ഈ ശീർഷത്തിലേക്ക് നയിക്കുന്നു. ഗ്രാഫ് ബന്ധിപ്പിച്ചിരിക്കുന്നതിനാൽ, ഇത് ക്രമീകരിക്കാൻ എളുപ്പമാണ്, തുടർന്ന് ചില ഡിഗ്രി α ഗ്രാഫിനെ ഈ ശീർഷത്തിലേക്ക് കുറയ്ക്കുമെന്ന് ലൂപ്പ് ഉറപ്പാക്കുന്നു.

അടുത്തതായി, ഏതെങ്കിലുമൊരു ശീർഷത്തിൽ നിന്ന് എല്ലാ d അരികുകളും ഒരേ ശീർഷം q ലേക്ക് നയിക്കുന്നുവെന്ന് ഒരു നിമിഷം കരുതുക. ഇത് വ്യവസ്ഥകളാൽ അനുവദനീയമാണ്, എന്നാൽ ഈ സാഹചര്യത്തിൽ ഞങ്ങൾ ഈ സെറ്റ് അരികുകൾ എന്ന് വിളിക്കും കുല. ഞങ്ങളുടെ രണ്ടാമത്തെ പരിമിതി ഇതാണ്: വ്യത്യസ്ത ശീർഷകങ്ങളിൽ നിന്നുള്ള p, q എന്നിവയിൽ നിന്നുള്ള രണ്ട് ലിങ്കുകൾ നയിക്കുന്ന ഒരു ശീർഷകം r ഇല്ല. എന്തുകൊണ്ടാണ് നമുക്ക് അത് അടിച്ചേൽപ്പിക്കാൻ കഴിയുക? കാരണം കണക്റ്റീവുകൾ p, q എന്നിവയിൽ നിന്ന് r ലേക്ക് പോകുകയാണെങ്കിൽ, ഏത് കളറിംഗിനും p, q ആദ്യ നിറത്തിന് ശേഷം r എന്ന ശീർഷത്തിൽ ഒത്തുചേരും, അതിനാൽ അവർ സ്ഥിരമായ സുഹൃത്തുക്കളാണ്. അതിനാൽ ഈ സാഹചര്യത്തിൽ പരന്നുകിടക്കുന്ന ഗ്രാഫുകളുടെയും ക്ലിക്കുകളുടെയും എല്ലാ നിർമ്മാണവും ഞങ്ങൾക്ക് ആവശ്യമില്ല, ഞങ്ങൾക്ക് ഉടനടി സ്ഥിരതയുള്ള സുഹൃത്തുക്കളെ ലഭിക്കും. അതിനാൽ ഇത് അങ്ങനെയല്ലെന്ന് നമുക്ക് അനുമാനിക്കാം.

അവസാനമായി, എല്ലാ ശീർഷകങ്ങളും സൈക്കിളുകളിലല്ല, എന്നാൽ നിസ്സാരമല്ലാത്ത ചില മരങ്ങൾ ഉള്ള ഒരു ഗ്രാഫ് R എല്ലായ്‌പ്പോഴും നിലവിലുണ്ടെന്ന് ഞങ്ങൾ തെളിയിക്കുന്നു. നമുക്ക് കുറച്ച് R തിരഞ്ഞെടുത്ത് അതിന്റെ എല്ലാ ശീർഷകങ്ങളും സൈക്കിളുകളിലാണെന്ന് അനുമാനിക്കാം. ഗ്രാഫ് ജിയിലെ എല്ലാ അരികുകളും ബന്ധിപ്പിച്ചിട്ടുണ്ടെങ്കിൽ, അതായത്. എല്ലായ്‌പ്പോഴും ഒരേ ശീർഷം വിടുന്ന എല്ലാ d അരികുകളും ഒരേ ശീർഷത്തിലേക്ക് നയിക്കുന്നു - അപ്പോൾ R ന്റെ തിരഞ്ഞെടുപ്പിൽ ഓരോ ലിങ്കിൽ നിന്നും ഒരു എഡ്ജ് തിരഞ്ഞെടുക്കുന്നത് ഉൾപ്പെടുന്നു. ഈ സാഹചര്യത്തിൽ, R-ൽ ഒരു സൈക്കിൾ മാത്രമേ ഉണ്ടാകൂ (എല്ലാത്തിനുമുപരി, R-ലെ നിരവധി സൈക്കിളുകൾ പരസ്പരം ബന്ധിപ്പിച്ചിരിക്കുന്ന ഗ്രാഫ് G-ൽ പരസ്പരം ബന്ധിപ്പിക്കാൻ കഴിയില്ല - G യുടെ എല്ലാ അരികുകളും R ന്റെ അരികുകളുടെ അതേ ലംബങ്ങളെ മാത്രമേ ബന്ധിപ്പിക്കൂ, കാരണം ഇവ കണക്റ്റീവുകളാണ് - കൂടാതെ G കണക്റ്റുചെയ്‌തിരിക്കുന്നതിനാൽ ഇത് അസാധ്യമാണ്), കൂടാതെ G-യിലെ ഏത് സൈക്കിളും ഈ സൈക്കിളിന്റെ കണക്ഷനുകളിൽ നിന്ന് മറ്റ് അരികുകൾ തിരഞ്ഞെടുക്കുന്നു, എന്നാൽ സാരാംശത്തിൽ ഇത് ഒരേ ചക്രം, ഒരേ നീളം. എന്നാൽ G-യിലെ എല്ലാ സൈക്കിളുകളുടെയും ദൈർഘ്യം ഈ നീളം കൊണ്ട് ഹരിക്കാനാകുമെന്നാണ് ഇതിനർത്ഥം, ഇത് G-യുടെ ആനുകാലികതയ്ക്ക് വിരുദ്ധമാണ്. അതിനാൽ, G-യിലെ എല്ലാ അരികുകളും ലിങ്കുകളിൽ കിടക്കുന്നു, അതായത് രണ്ട് അരികുകൾ ഉണ്ടെന്ന് അർത്ഥമാക്കുന്നത്. p-- >R-ൽ q, കൂടാതെ p-->കൾ R-ന് പുറത്ത് (p-യിൽ നിന്നുള്ള ചില അഗ്രങ്ങൾ സ്‌പാനിംഗ് ഗ്രാഫിൽ കിടക്കുന്നില്ലെന്ന് മാത്രമല്ല, മറ്റൊരു ശീർഷം s-ലേക്ക് നയിക്കുകയും ചെയ്യുന്നു എന്ന് തെളിയിക്കാൻ ഞങ്ങൾക്ക് കണക്റ്റീവുകളെ കുറിച്ച് ഒരു നീണ്ട വാദം ആവശ്യമായിരുന്നു). തുടർന്ന് നമ്മൾ p-->q എന്നത് p-->s ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കുന്നു, ഇത് സൈക്കിളിനെ "തകരും", അതിൽ ഒരുതരം നിസ്സാരമല്ലാത്ത വാൽ സൃഷ്ടിക്കും. ഈ വാൽ നമുക്ക് പുതിയ ഗ്രാഫിൽ നിസ്സാരമല്ലാത്ത ഒരു വൃക്ഷം നൽകും.

ഇപ്പോൾ നമുക്ക് എല്ലാ സ്പാനിംഗ് ഗ്രാഫുകളിൽ നിന്നും R തിരഞ്ഞെടുക്കാം, അതിൽ ട്രിവിയൽ മരങ്ങൾ അടങ്ങിയിരിക്കുന്നു, അത് സൈക്കിളുകളിൽ പരമാവധി എണ്ണം ശീർഷകങ്ങളുള്ള R ആണ്. അതാണ് ഇതിന് സൈക്കിളുകളിൽ ഇല്ലാത്ത ലംബങ്ങളുണ്ട്, എന്നാൽ ഈ പരിമിതി കൂടാതെ, സൈക്കിളുകളിലെ ലംബങ്ങളുടെ എണ്ണം പരമാവധിയാക്കുന്നു. ഈ ഗ്രാഫിൽ പരമാവധി ലെവൽ L ന്റെ ചില ലംബങ്ങൾ ഉണ്ട്, അവ വ്യത്യസ്ത വേരുകളിലേക്ക് നയിക്കുന്ന മരങ്ങളിലാണെന്ന് നമുക്ക് അനുമാനിക്കാം, അല്ലാത്തപക്ഷം നമുക്ക് ആവശ്യമുള്ളത് ഞങ്ങൾ ഇതിനകം നേടിയിട്ടുണ്ട്. നമുക്ക് അത്തരത്തിലുള്ള ഒരു ശീർഷകം x തിരഞ്ഞെടുക്കാം. ഗ്രാഫ് മാറ്റാൻ ഞങ്ങൾ ആഗ്രഹിക്കുന്നു, അങ്ങനെ ഈ ശീർഷകം ട്രീയിലെ ദൈർഘ്യമേറിയ റൂട്ടിന്റെ ഭാഗമാകും, എൽ എന്നതിനേക്കാൾ ദൈർഘ്യമേറിയതാണ്, മറ്റ് മരങ്ങൾ മാറില്ല, തുടർന്ന് പരമാവധി ലെവൽ ഒരു മരത്തിൽ മാത്രമായിരിക്കും, അതാണ് നമുക്ക് വേണ്ടത്. നിങ്ങൾക്ക് മൂന്ന് തരത്തിൽ ഗ്രാഫ് മാറ്റാൻ കഴിയും:

a) കുറച്ച് എഡ്ജ് y-->x എടുത്ത് R-ലേക്ക് ചേർക്കുക, നിലവിലുള്ള എഡ്ജ് y-->z ഉപേക്ഷിക്കുക;
b) b-->r എന്ന എഡ്ജ് എടുക്കുക, അത് x-ൽ നിന്ന് അതിന്റെ സൈക്കിളിലേക്കുള്ള പാതയിലെ അവസാനത്തേതാണ് (r സൈക്കിളിൽ), അത് വലിച്ചെറിയുക, മറ്റ് ചില b-->z ചേർക്കുക.
c) സൈക്കിളിന്റെ ഭാഗമായ c-->r എന്ന എഡ്ജ് എടുത്ത് അത് ഉപേക്ഷിച്ച് മറ്റ് ചില c-->z ചേർക്കുക.

ഈ മാറ്റങ്ങളിൽ ഒന്ന് (അല്ലെങ്കിൽ ചില സന്ദർഭങ്ങളിൽ രണ്ടെണ്ണം) ആവശ്യമുള്ള ഫലത്തിലേക്ക് നയിക്കുമെന്ന് ട്രാക്ക്മാന്റെ പേപ്പറിലെ ലെമ്മ 7 വിശദമായി തെളിയിക്കുന്നു. പ്രക്രിയ R ന്റെ പരമാവധി രണ്ടും ഉപയോഗിക്കുന്നു (ചില മാറ്റങ്ങൾ R-നേക്കാൾ കൂടുതൽ ചക്രങ്ങളുള്ള ഒരു ഗ്രാഫിലേക്ക് നയിക്കുകയാണെങ്കിൽ, ഇത് അതിന്റെ മാക്സിമലിറ്റിക്ക് വിരുദ്ധമാണ്), കൂടാതെ രണ്ട് ലിങ്കുകൾ നയിക്കുന്ന ശീർഷകം ഇല്ലെന്ന് മുകളിൽ നിർവചിച്ചിരിക്കുന്ന അവസ്ഥ. തൽഫലമായി, ഏത് സാഹചര്യത്തിലും, നമുക്ക് ഒരു ഗ്രാഫ് R ലഭിക്കും, അതിൽ പരമാവധി ലെവലിന്റെ എല്ലാ ശീർഷകങ്ങളും ഒരു നിസ്സാരമല്ലാത്ത മരത്തിൽ കിടക്കുന്നു.

അപ്‌ഡേറ്റ്, ഒരാഴ്ചയ്ക്ക് ശേഷം:എന്നിരുന്നാലും, ഈ എൻട്രി പൂർണ്ണമായും സ്വയംപര്യാപ്തമാക്കാൻ ഞാൻ തീരുമാനിച്ചു, കൂടാതെ മുൻ ഖണ്ഡികയിൽ ഞാൻ പരാമർശിച്ച ലെമ്മയുടെ തെളിവ് വീണ്ടും പറയുകയും ചെയ്തു. ഒരു ഡയഗ്രം ഉപയോഗിച്ച് ഇത് ചെയ്യുന്നതാണ് നല്ലത്, പക്ഷേ അത് വരയ്ക്കാനോ ലേഖനത്തിൽ നിന്ന് കീറാനോ ഞാൻ ആഗ്രഹിക്കുന്നില്ല, അതിനാൽ ഞാൻ വാക്കുകൾ ഉപയോഗിച്ച് ശ്രമിക്കും. അതിനാൽ, നമുക്ക് വിശാലമായ ഒരു ഗ്രാഫ് R ഉണ്ടെന്ന് സങ്കൽപ്പിക്കുക, അതിൽ നിസ്സാരമല്ലാത്ത മരങ്ങളുണ്ട്, അതിൽ അത്തരം എല്ലാ ഗ്രാഫുകളിലും പരമാവധി എണ്ണം ചക്രങ്ങളിൽ കിടക്കുന്നു. R നെ ഒരു പരന്ന ഗ്രാഫാക്കി മാറ്റാൻ ഞങ്ങൾ ലക്ഷ്യമിടുന്നു, അതിൽ പരമാവധി ലെവലിന്റെ എല്ലാ ലംബങ്ങളും ഒരേ മരത്തിൽ കിടക്കുന്നു; ശ്രമിക്കുന്നതിനിടയിൽ അത്തരമൊരു ഗ്രാഫ് ലഭിച്ചാലുടൻ, ഞങ്ങൾ ഉടനടി പൂർത്തിയാക്കും (ചക്രങ്ങളിലെ ശീർഷകങ്ങളുടെ എണ്ണത്തിന്റെ അടിസ്ഥാനത്തിൽ ഗ്രാഫിന്റെ മാക്സിമലിറ്റി നഷ്ടപ്പെടുമെന്നത് ഞങ്ങൾ കാര്യമാക്കുന്നില്ല, ഇത് ഞങ്ങൾക്ക് പ്രധാനമല്ല. സ്വയം, ഞങ്ങൾ അത് പ്രക്രിയയിൽ മാത്രമേ ഉപയോഗിക്കുന്നുള്ളൂ). x എന്നത് പരമാവധി ലെവലായ L ന്റെ ശീർഷകമായിരിക്കട്ടെ, T അത് കിടക്കുന്ന വൃക്ഷം, r, T അവസാനിക്കുന്ന C സൈക്കിളിലെ ശീർഷകം, b-->r x-ൽ നിന്ന് C സൈക്കിളിലേക്കുള്ള പാതയിൽ r-ന് മുമ്പുള്ള അവസാന അറ്റം. നമുക്ക് ഊഹിക്കാം , ഈ ചക്രത്തിൽ ചേരുന്ന മറ്റ് ചില മരങ്ങൾ അല്ലെങ്കിൽ ലെവൽ L ന്റെ ശീർഷകങ്ങളുള്ള മറ്റു ചിലത് - അല്ലാത്തപക്ഷം എല്ലാം ഇതിനകം ചെയ്തുകഴിഞ്ഞു. L-നേക്കാൾ വലിയ അളവിലുള്ള ഒരു ഘടകമുള്ള ഒരു വൃക്ഷം T-യിൽ നിന്ന് നമുക്ക് ലഭിക്കുകയും ഈ മറ്റ് മരങ്ങൾ നീട്ടാതിരിക്കുകയും ചെയ്‌താൽ, ഞങ്ങൾ പൂർത്തിയാക്കി.

ആദ്യം, നമുക്ക് ഓപ്പറേഷൻ a) മുകളിൽ ചെയ്യാൻ ശ്രമിക്കാം: G-യിൽ കുറച്ച് എഡ്ജ് y-->x എടുക്കുക - അത് നിലവിലുണ്ട്, കാരണം ഗ്രാഫ് ബന്ധിപ്പിച്ചിരിക്കുന്നു, ലൂപ്പുകളില്ലാതെ, R ൽ കിടക്കുന്നില്ല, കാരണം x പരമാവധി ലെവൽ. നമുക്ക് അത് R-ലേക്ക് ചേർക്കുക, മുമ്പ് ഉണ്ടായിരുന്ന കുറച്ച് y-->z എറിയുക. y ഒരു മരത്തിൽ T യിൽ കിടക്കുകയാണെങ്കിൽ, y-->x ഒരു പുതിയ ചക്രം അടയ്ക്കുന്നു, പുതിയ ഗ്രാഫിൽ കൂടുതൽ ലംബങ്ങൾ സൈക്കിളുകളിൽ കിടക്കുന്നു, കൂടാതെ നിസ്സാരമല്ലാത്ത മരങ്ങൾ ഇപ്പോഴും ഉണ്ട് (കുറഞ്ഞത് R-ൽ ഉള്ളവയെങ്കിലും), അവ R ന്റെ മാക്സിമലിറ്റിക്ക് വിരുദ്ധമാണ്. T യിൽ y കിടക്കുന്നില്ലെങ്കിൽ y-->z ഒരു സൈക്കിൾ C യുടെ ഭാഗമല്ലെങ്കിൽ, y-->z നീക്കം ചെയ്യുന്നത് ഈ ചക്രം തകർക്കില്ല, എന്നാൽ y-->x ചേർക്കുന്നത് പരമാവധി വർദ്ധിപ്പിക്കുന്നു T മരത്തിന്റെ നിലവാരം കുറഞ്ഞത് ഒന്നെങ്കിലും, മറ്റുള്ളവ മരങ്ങൾ നീളം കൂട്ടുന്നില്ല, അതിനാൽ ഞങ്ങൾ പൂർത്തിയാക്കി. y-->z സൈക്കിൾ C-യിൽ കിടക്കുമ്പോൾ, അത് ഇപ്പോൾ തകർന്നിരിക്കുന്നു, കൂടാതെ ഒരു പുതിയ ചക്രം രൂപപ്പെടുകയും ചെയ്യുമ്പോൾ ശേഷിക്കുന്ന ഓപ്ഷൻ: r മുതൽ y ലേക്ക്, തുടർന്ന് y-->x, തുടർന്ന് x-ൽ നിന്ന് r-ൽ നിന്ന് r വരെ. ഈ ചക്രത്തിന്റെ ദൈർഘ്യം l(ry)+1+L ആണ്, പഴയ സൈക്കിൾ C യുടെ നീളം l(ry)+1+l(zr) ആയിരുന്നു. പുതിയ ചക്രം പഴയതിനേക്കാൾ ദൈർഘ്യമേറിയതായിരിക്കരുത്, ഇത് R ന്റെ പരമാവധി വിരുദ്ധമാണ്, അതിനാൽ L ≤ l(zr), അതായത്. പഴയ ലൂപ്പിലെ z മുതൽ r വരെയുള്ള റൂട്ടിന്റെ ദൈർഘ്യം. മറുവശത്ത്, പുതിയ ഗ്രാഫിൽ, വെർട്ടെക്സ് z ന് ഇപ്പോൾ കുറഞ്ഞത് l(zr) ലെവൽ ഉണ്ട്, ഇത് L-നേക്കാൾ വലുതാണെങ്കിൽ, ഞങ്ങൾ പൂർത്തിയാക്കി. അതിനാൽ നമുക്ക് l(zr)=L എന്ന് അനുമാനിക്കാം. ചുരുക്കത്തിൽ: a) പ്രവർത്തിക്കുന്നില്ല എന്ന് ഞങ്ങൾ അനുമാനിക്കുന്നു, തുടർന്ന് C, l(zr) = L എന്ന സൈക്കിളിലാണ് y-->z കിടക്കുന്നതെന്ന് ഞങ്ങൾക്കറിയാം.

ഇനി നമുക്ക് ഓപ്പറേഷൻ ബി പരീക്ഷിക്കാം: എഡ്ജ് b-->r മാറ്റി മറ്റൊരു എഡ്ജ് b-->d. പുതിയ വെർട്ടെക്സ് ഡി എവിടെയാണെന്ന് നോക്കാം. T മരത്തിലാണെങ്കിൽ, മുമ്പത്തേത് തകർക്കാതെ ഞങ്ങൾ ഒരു പുതിയ സൈക്കിൾ സൃഷ്‌ടിക്കുകയും R-ന്റെ മാക്സിമലിറ്റി നിരാകരിക്കുകയും ചെയ്തു. മറ്റൊരു മരത്തിലാണെങ്കിൽ, x ഉൾപ്പെടെയുള്ള T യുടെ പരമാവധി ലംബങ്ങൾക്ക് ഇപ്പോൾ L-നേക്കാൾ വലിയ ലെവൽ ഉണ്ടായിരിക്കും, കൂടാതെ മറ്റ് മരങ്ങൾ ചെയ്യില്ല, ഞങ്ങൾ തീർന്നു. മറ്റൊരു സൈക്കിളിലാണെങ്കിൽ, C അല്ല, ഞങ്ങൾ ഇപ്പോൾ ചെയ്യും, ഒപ്പം b) a) കൂടി: y-->z C-ൽ കിടക്കുന്നു എന്ന് ഞങ്ങൾക്കറിയാവുന്നതിനാൽ, ഈ പ്രവർത്തനം C വിഭജിക്കും, പക്ഷേ അതിലേക്കുള്ള പുതിയ ചക്രം അല്ല ഇപ്പോൾ ട്രീ T യുമായി ബന്ധിപ്പിച്ചിരിക്കുന്നു, ഈ മരത്തിൽ ഇപ്പോൾ L-നേക്കാൾ വലിയ ലെവലിന്റെ ലംബങ്ങൾ ഉണ്ടാകും, ഞങ്ങൾ വീണ്ടും പൂർത്തിയാക്കി.

b-->d എന്നത് സൈക്കിൾ C യുമായി ബന്ധിപ്പിക്കുമ്പോൾ, r അല്ലാതെ മറ്റെവിടെയെങ്കിലും അല്ലെങ്കിൽ അതേ സ്ഥലത്തും തുടർന്ന് d=r എന്നതുമാണ് ശേഷിക്കുന്ന ഓപ്ഷൻ. ഞങ്ങൾ b-->r എന്നത് b-->d ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിച്ചതിന് ശേഷം, ഞങ്ങൾക്ക് തുടക്കത്തിൽ ഉണ്ടായിരുന്ന അതേ സാഹചര്യം ലഭിച്ചു - ട്രീ T, ലെവലിന്റെ x x ലെവൽ മുതലായവ. - ശീർഷകം d വഴി ചക്രം മാത്രമേ ഇപ്പോൾ ചക്രവുമായി ബന്ധിപ്പിച്ചിട്ടുള്ളൂ. ഇപ്പോൾ ഓപ്പറേഷൻ a പരിഗണിക്കുമ്പോൾ, l(zd) = L എന്ന് ഞങ്ങൾ നിഗമനം ചെയ്യുന്നു (അത് പ്രവർത്തിക്കുന്നില്ല എന്ന് കരുതുക), ഞങ്ങൾ മുമ്പ് l(zr) = L എന്ന് നിഗമനം ചെയ്തതുപോലെ, എന്നാൽ l(zd) = l(zr), അതായത്. z മുതൽ d, r വരെയുള്ള സൈക്കിളിലെ ദൂരം തുല്യമാണ്, തുടർന്ന് ഇത് ഒരേ ശീർഷകമാണ്: d=r. അതിനാൽ, b) പ്രവർത്തിക്കുന്നില്ലെങ്കിൽ, b-ൽ നിന്നുള്ള ഏതെങ്കിലും എഡ്ജ് r-ലേക്ക് നയിക്കണം, അതായത്. ബിയിൽ നിന്നുള്ള അറ്റങ്ങൾ ഒരു ലിങ്ക് ഉണ്ടാക്കുന്നു.

അവസാനമായി, C സൈക്കിളിൽ കിടക്കുന്ന c-->r എന്ന എഡ്ജ് പരിഗണിക്കുക. b യിൽ നിന്നുള്ള എല്ലാ അറ്റങ്ങളും r ലേക്ക് നയിക്കുന്ന ലിങ്കിലാണ് കിടക്കുന്നതെന്ന് നമുക്ക് അനുമാനിക്കാം എന്നതിനാൽ, രണ്ട് ലിങ്കുകൾ ഉണ്ടാകാൻ പാടില്ല എന്ന നിയന്ത്രണവും നമുക്ക് ചുമത്താം. ഒരു ശീർഷകം, എല്ലാ അറ്റങ്ങളും c-ൽ നിന്ന് r-ലേയ്‌ക്ക് നയിക്കുന്നില്ല, പക്ഷേ ചില അരികുകൾ c-->e ഉണ്ട്. നമുക്ക് c-->r പകരം c-->e എന്ന് പറയാം. ശീർഷകം എവിടെ കിടക്കും? T ട്രീയിലല്ല, കാരണം അത് R ന്റെ പരമാവധി വ്യത്യസ്‌തമായി C സൈക്കിളിനെ "നീട്ടും". അതിനാൽ e മറ്റൊരു മരത്തിലോ മറ്റൊരു ചക്രത്തിലോ അല്ലെങ്കിൽ അതേ സൈക്കിളിലോ പോലും C കിടക്കുന്നു, പക്ഷേ r ശീർഷത്തിലല്ല. അപ്പോൾ T വൃക്ഷം, ലൂപ്പിൽ ചേരുന്നതിന് മുമ്പ്, ഇപ്പോൾ r-ൽ നിന്ന് പുറപ്പെടുന്ന ഒരു അറ്റത്തെങ്കിലും ഒരു അരികിലൂടെ വിപുലീകരിക്കപ്പെടുന്നു, ഒരുപക്ഷേ കൂടുതൽ (r ന് തൊട്ടുപിന്നാലെ e കിടക്കുന്നുവെങ്കിൽ, c-->e ലൂപ്പ് C വീണ്ടും അടച്ചാൽ ഒന്ന് മാത്രം, അതിൽ നിന്ന് r മാത്രം ഉരുത്തിരിഞ്ഞു). ഇതിനർത്ഥം വെർട്ടെക്സ് x, മറ്റ് മാക്സിമൽ വെർട്ടിസുകൾ ടി എന്നിവയ്ക്ക് ഇപ്പോൾ L+1-ൽ കുറയാത്ത ലെവൽ ഉണ്ട്, മറ്റ് മരങ്ങൾ നീളം കൂടിയിട്ടില്ല, വീണ്ടും നമുക്ക് ആവശ്യമുള്ളത് ലഭിച്ചു.

ഡിസ്നിക്കും പിക്സറിനും നന്ദി, 2006 ജൂണിൽ ലോകം മുഴുവൻ കാറുകൾ മാത്രം നായകന്മാരായ ഒരു കാർട്ടൂൺ കണ്ടു.

കാർട്ടൂണിലെ കാറുകൾ ഒരു സാധാരണ ജീവിതം നയിക്കുന്നു - ഒരാൾ ടയർ സ്റ്റോർ നടത്തുന്നു, മറ്റൊന്ന് ട്യൂണിംഗ് സ്റ്റുഡിയോ നടത്തുന്നു, ചിലർ ഹിപ്പി ഫിൽമോറെ (ഫോക്സ്‌വാഗൺ ടി 1) അല്ലെങ്കിൽ അവന്റെ സുഹൃത്തായ രണ്ടാം ലോക മഹായുദ്ധ സേനാനിയെപ്പോലെ സ്വന്തം സന്തോഷത്തിനായി ജീവിക്കുന്നു. സെർജ് (വില്ലിസ്). "മിന്നൽ" എന്ന് വിളിപ്പേരുള്ള മക്ക്വീൻ എന്ന ചിത്രത്തിലെ പ്രധാന കഥാപാത്രം റേസിംഗും വിജയങ്ങളും മഹത്വവും മാത്രം സ്വപ്നം കാണുന്നു. പ്രസിദ്ധമായ അമേരിക്കൻ ഹൈവേ 66 ലെ റേഡിയേറ്റർ ഡിസ്ട്രിക്റ്റിൽ ഒരിക്കൽ, ഇപ്പോഴും "പച്ച" മക്ക്വീൻ ഉടൻ തന്നെ എല്ലാവരോടും അവൻ എത്ര വേഗമേറിയതും തണുപ്പുള്ളതുമാണെന്ന് പറയുന്നു. എന്നിരുന്നാലും, ഒരു NASCAR ഓട്ടത്തിലെ അവന്റെ ആദ്യ തുടക്കം അവന്റെ മിഥ്യാധാരണകളെ ഇല്ലാതാക്കുന്നു. നഷ്ടത്തെ അതിജീവിക്കാൻ സുഹൃത്തുക്കൾ നായകനെ സഹായിക്കുന്നു - പഴയ ടോ ട്രക്ക് മേറ്റർ (ജിഎംസി പിക്ക്-അപ്പ്), ഉപദേശകൻ ഡോക് ഹഡ്‌സൺ (ഹഡ്‌സൺ ഹോർനെറ്റ്), യഥാർത്ഥ ഫെരാരിയെ കാണാൻ സ്വപ്നം കാണുന്ന ചെറിയ ലൂയിജി (ഫിയറ്റ് 600).

ശരി, റൊമാന്റിക് ബ്യൂട്ടി സാലി (മനോഹരമായ 911 ടാറ്റൂ ഉള്ള പോർഷെ) ഇല്ലാതെ നമ്മൾ എവിടെയായിരിക്കും! അവർക്ക് നന്ദി, ചിക്കോയുടെ പ്രധാന എതിരാളിയെ (പ്ലൈമൗത്ത് ഹെമി കുഡ) പരാജയപ്പെടുത്തി മക്വീൻ ഇപ്പോഴും മത്സരത്തിൽ വിജയിക്കും. ലൂയിഗിയുടെ സ്വപ്നവും സാക്ഷാത്കരിക്കും - ഒരു ദിവസം "മരാനെല്ലോയിൽ നിന്നുള്ള ഒരു സ്റ്റാലിയൻ", "റെഡ് ബാരൺ" തന്നെ ശബ്ദമുയർത്തി, മൈക്കൽ ഷൂമാക്കർ ടയറുകൾ മാറ്റാൻ അവന്റെ കടയിൽ വരും.

സിനിമയുടെ സ്രഷ്‌ടാക്കളും ശബ്ദം നൽകിയവരും കാറുമായി ബന്ധപ്പെട്ടവരാണ് എന്നത് ശ്രദ്ധേയമാണ്. ഉദാഹരണത്തിന്, സംവിധായകൻ ജോ ലാസെറ്റർ തന്റെ കുട്ടിക്കാലം മുഴുവൻ ഷെവർലെ പ്ലാന്റിൽ ചെലവഴിച്ചു, അവിടെ അദ്ദേഹത്തിന്റെ പിതാവ് മുഖ്യ ഡിസൈനർമാരിൽ ഒരാളായിരുന്നു. ഫോർഡിന്റെ മുൻനിര ഡിസൈനർ ജെയ് മെയ്‌സ് കൺസൾട്ടന്റായി പ്രവർത്തിച്ചു. ഇതിനകം സൂചിപ്പിച്ച ഏഴ് തവണ ഫോർമുല 1 ലോക ചാമ്പ്യൻ മൈക്കൽ ഷൂമാക്കറെ കൂടാതെ, NASCAR താരങ്ങളായ റിച്ചാർഡ് പെറ്റിയും പോൾ ന്യൂമാനും അതുപോലെ ഇതിഹാസ റേസർ മൈക്കൽ ആൻഡ്രെറ്റിയും കഥാപാത്രങ്ങൾക്ക് ശബ്ദം നൽകുന്നതിൽ പങ്കെടുത്തു.

കാറുകളുടെ യഥാർത്ഥ ശബ്ദം മാത്രമേ ഉപയോഗിച്ചിട്ടുള്ളൂ - ഉദാഹരണത്തിന്, പ്രത്യേകിച്ച് റേസിംഗ് എപ്പിസോഡുകൾക്കായി, നാസ്കർ മത്സരങ്ങളിൽ അമേരിക്കൻ ഓവലുകളിൽ നിരവധി ആഴ്ചകളോളം ശബ്ദം റെക്കോർഡുചെയ്‌തു. ചിത്രം നിർമ്മിക്കാൻ രണ്ട് വർഷത്തിലേറെ സമയമെടുത്തു, അതിന്റെ ബഡ്ജറ്റ് 70 ദശലക്ഷം USD ആയിരുന്നു. ഈ സമയത്ത്, കാറുകളുടെ 43 ആയിരം വ്യത്യസ്ത സ്കെച്ചുകൾ സൃഷ്ടിച്ചു, ഓരോ ഡ്രോയിംഗും 17 മണിക്കൂറിലധികം എടുത്തു. സിനിമയിൽ ആകെ 120 കാർ കഥാപാത്രങ്ങളുണ്ട് - പുതിയ പോർഷെസും ഫെരാരിയും മുതൽ പുരാതന ഫോർഡ് ടി വരെ.

റോഡിലെ നിയമങ്ങളെക്കുറിച്ചുള്ള കുട്ടിയുടെ അറിവ് തെരുവിലെ അവന്റെ സുരക്ഷയുടെ പ്രധാന വ്യവസ്ഥകളിലൊന്നാണ്. പ്രായപൂർത്തിയായവർ ഉൾപ്പെടെയുള്ള പല കാൽനടയാത്രക്കാരും ഈ നിയമങ്ങൾ വളരെ നിസ്സാരമായി കാണുന്നു, ഇത് പലപ്പോഴും വ്യത്യസ്ത തീവ്രതയുള്ള ട്രാഫിക് അപകടങ്ങൾക്ക് കാരണമാകുന്നു. ജനസാന്ദ്രതയുള്ള ഒരു പ്രദേശത്ത് തെരുവിലായിരിക്കുമ്പോൾ, റോഡ് ട്രാഫിക്കിൽ അവർ പൂർണ്ണമായും പങ്കാളികളാണെന്ന് കുട്ടികൾ വ്യക്തമായി മനസ്സിലാക്കണം, അതിനാൽ ട്രാഫിക് നിയമങ്ങൾ പാലിക്കുന്നത് അവരുടെ ഉത്തരവാദിത്തമാണ്.

കളറിംഗ് പേജുകൾ കുട്ടികൾക്കുള്ള ട്രാഫിക് നിയമങ്ങൾ.

തെരുവിലെ പെരുമാറ്റ നിയമങ്ങൾ (റോഡുകൾ, നടപ്പാതകൾ, നഗര ഗതാഗതം) ഒരു കുട്ടിയെ പഠിപ്പിക്കുന്നത് വളരെ ചെറുപ്പത്തിൽ തന്നെ ആരംഭിക്കണം, അവൻ സ്വന്തമായി നടക്കാനും ഓടാനും പഠിക്കുന്നതിനുമുമ്പ്. കുട്ടി തെരുവിലായ മാതാപിതാക്കളുടെയും മറ്റ് മുതിർന്നവരുടെയും ഉദാഹരണം ഇവിടെ വളരെ പ്രധാനമാണ്. നിങ്ങളുടെ കുട്ടിയോട് റോഡിന്റെ നിയമങ്ങൾ പറയുകയും വിശദീകരിക്കുകയും ചെയ്യുക മാത്രമല്ല, അവ സ്വയം കർശനമായി നിരീക്ഷിക്കുകയും വേണം. ഈ പേജിൽ അവതരിപ്പിച്ചിരിക്കുന്ന ട്രാഫിക് റൂൾസ് കളറിംഗ് പേജുകൾ പ്രാഥമികമായി പ്രീസ്‌കൂൾ കുട്ടികളെ ഉദ്ദേശിച്ചുള്ളതാണ്, മാത്രമല്ല റോഡിലും അതിനടുത്തും ഉള്ള പെരുമാറ്റത്തിന്റെ അടിസ്ഥാന പോയിന്റുകൾ പഠിക്കാൻ കുട്ടികളെ സഹായിക്കും.

1. കളറിംഗ് പേജ് ട്രാഫിക് ലൈറ്റ്.

സുരക്ഷിതമായി റോഡ് മുറിച്ചുകടക്കാനുള്ള ഏറ്റവും നല്ല സ്ഥലം ട്രാഫിക് ലൈറ്റ് ഘടിപ്പിച്ച കാൽനട ക്രോസിംഗാണ്. ട്രാഫിക് ലൈറ്റുകളുടെ ചിത്രങ്ങളുള്ള കളറിംഗ് പേജുകളിൽ ചെറിയ റൈമുകളും അടങ്ങിയിരിക്കുന്നു, അവ ഉപയോഗിക്കുന്നതിനുള്ള നിയമങ്ങൾ കൂടുതൽ എളുപ്പത്തിൽ ഓർമ്മിക്കാൻ കുട്ടികളെ സഹായിക്കുന്നു.

• എപ്പോഴും ട്രാഫിക്ക് ലൈറ്റ് പച്ചയായിരിക്കുമ്പോൾ മാത്രം ഡ്രൈവിംഗ് ആരംഭിക്കുക.
• ട്രാഫിക് സിഗ്നലുകൾ ചുവപ്പും മഞ്ഞയും ഉള്ളപ്പോൾ ഒരിക്കലും റോഡ് മുറിച്ചുകടക്കരുത്, സമീപത്ത് വാഹനങ്ങൾ ഇല്ലെങ്കിലും.
• പച്ച ലൈറ്റിലേക്ക് തിരിയുമ്പോൾ, നിങ്ങളുടെ സുരക്ഷ ഉറപ്പാക്കുക - ഇടത്തോട്ടും പിന്നീട് വലത്തോട്ടും നോക്കുക.

2. കളറിംഗ് പേജ് കാൽനട ക്രോസിംഗ്.

കാൽനട ക്രോസിംഗിൽ മാത്രം റോഡ് മുറിച്ചുകടക്കാൻ നിങ്ങളുടെ കുട്ടിയെ പഠിപ്പിക്കുക. കാൽനട ക്രോസിംഗുകളുടെ കളർ പേജുകൾ റോഡ് എങ്ങനെ ശരിയായി മുറിച്ചുകടക്കാമെന്ന് കുട്ടികളെ പഠിപ്പിക്കും. ട്രാഫിക് ലൈറ്റ് ഇല്ലാത്ത ഒരു ക്രോസിംഗിനെ അനിയന്ത്രിതമായ എന്ന് വിളിക്കുന്നു.

• കാൽനട ക്രോസിംഗ് റോഡിന്റെ ഉപരിതലത്തിൽ സീബ്രാ ക്രോസിംഗ് ഉപയോഗിച്ച് അടയാളപ്പെടുത്തിയിരിക്കുന്നു.
• റോഡ് മുറിച്ചുകടക്കുന്നതിന് മുമ്പ്, അത് ശ്രദ്ധാപൂർവ്വം പരിശോധിക്കുകയും സമീപത്ത് ട്രാഫിക് ഇല്ലെന്ന് ഉറപ്പാക്കുകയും ചെയ്യുക.
• റോഡ് മുറിച്ചുകടക്കുക, അതിന് കുറുകെ ഓടരുത്.
• തെരുവ് ഡയഗണലായി കടക്കരുത്.
• നിങ്ങളുടെ കാഴ്ചയെ തടയുന്ന നിശ്ചലമായ വാഹനങ്ങൾ പ്രത്യേകം ശ്രദ്ധിക്കുക.
• കാൽനട ക്രോസിംഗിലൂടെ നീങ്ങുമ്പോൾ, ഫോണിൽ സംസാരിക്കുന്നത് നിർത്തുക.
• സമീപത്ത് ഭൂഗർഭപാതകളോ ഓവർപാസുകളോ ഉണ്ടെങ്കിൽ, അവ ഉപയോഗിക്കുന്നത് ഉറപ്പാക്കുക; അത്തരം സ്ഥലങ്ങളിൽ ട്രാഫിക് പ്രത്യേകിച്ചും തീവ്രമാണ്.

3. നടപ്പാതകൾ.

കാൽനടയാത്രയ്ക്ക് വേണ്ടിയുള്ളതാണ് നടപ്പാത. നടപ്പാതകളിൽ, പ്രത്യേകിച്ച് ഗതാഗതക്കുരുക്ക് കൂടുതലുള്ള സ്ഥലങ്ങളിൽ കൃത്യമായി പെരുമാറാൻ കുട്ടികളെ പഠിപ്പിക്കുക.

• റോഡിലൂടെയുള്ള നടപ്പാതയിലൂടെ വാഹനമോടിക്കുമ്പോൾ അതിനോട് അധികം അടുക്കരുത്.
• മുറ്റവും ഇടവഴികളും വിട്ടുപോകുന്ന സാധ്യമായ വാഹനങ്ങൾ ശ്രദ്ധാപൂർവ്വം നിരീക്ഷിക്കുക.
• നടപ്പാതയിൽ പന്ത് കളിക്കുകയോ ഓടുകയോ ചെയ്യരുത്.

4. നഗര പൊതുഗതാഗതത്തിലും ബസ് സ്റ്റോപ്പുകളിലും കുട്ടികൾക്കുള്ള പെരുമാറ്റ നിയമങ്ങളുള്ള പേജുകൾ കളറിംഗ് ചെയ്യുക.

പൊതുഗതാഗതം എങ്ങനെ സുരക്ഷിതമായി ഉപയോഗിക്കാമെന്ന് ഈ കളറിംഗ് പേജുകൾ കുട്ടികളെ പഠിപ്പിക്കും.

• റോഡിന്റെ മോശം കാഴ്ചയും ഒരു വലിയ ജനക്കൂട്ടവും ഒരു കുട്ടിയെ നടപ്പാതയിൽ നിന്ന് അബദ്ധത്തിൽ റോഡിലേക്ക് തള്ളാൻ കഴിയുന്നതിനാൽ ഒരു പൊതു ഗതാഗത സ്റ്റോപ്പ് അപകടകരമായ സ്ഥലമാണ്. ഇവിടെ നിങ്ങൾ പ്രത്യേകം ശ്രദ്ധിക്കേണ്ടതുണ്ട്.
• വാഹനം പൂർണ്ണമായി നിർത്തിയതിനു ശേഷം മാത്രമേ വാഹനത്തിന്റെ വാതിലുകളെ സമീപിക്കൂ.
• വാഹനത്തിൽ നിന്ന് ഇറങ്ങിയ ശേഷം സ്റ്റോപ്പ് വിട്ടതിന് ശേഷം മാത്രമേ റോഡ് മുറിച്ചു കടക്കാൻ പോകാവൂ.

ഈ അടിസ്ഥാന ട്രാഫിക് നിയമങ്ങൾ കൂടാതെ, കുട്ടികൾ റോഡ് അടയാളങ്ങൾ കളറിംഗ് ചെയ്യാൻ താൽപ്പര്യപ്പെടും. അവതരിപ്പിച്ച ട്രാഫിക് നിയമങ്ങൾ കളറിംഗ് പേജുകൾ പിഞ്ചുകുട്ടികൾക്കും പ്രീസ്‌കൂൾ കുട്ടികൾക്കും പ്രൈമറി സ്കൂൾ വിദ്യാർത്ഥികൾക്കും അതുപോലെ കിന്റർഗാർട്ടനുകളിലും പ്രൈമറി സ്കൂൾ പാഠങ്ങളിലും ഉപയോഗിക്കുന്നതിന് അനുയോജ്യമാണ്. ട്രാഫിക് നിയമങ്ങളുള്ള എല്ലാ ചിത്രങ്ങളും പൂർണ്ണമായും സൗജന്യമാണ് - നിങ്ങൾക്ക് അവ ഡൗൺലോഡ് ചെയ്ത് പ്രിന്റ് ചെയ്യാം.

സാൻഡ്‌ബോക്‌സിൽ കാറുകൾ ഉപയോഗിച്ച് കളിക്കാൻ നിങ്ങൾ ആൺകുട്ടികളെ ക്ഷണിച്ചാൽ നിങ്ങൾക്ക് ദീർഘനേരം അവരെ തിരക്കിലാക്കാനാകും. എന്നാൽ പുറത്ത് തണുപ്പ് അനുഭവപ്പെടുകയും കുട്ടിക്ക് ബോറടിക്കുകയും ചെയ്താൽ എന്തുചെയ്യും. ഈ സാഹചര്യത്തിൽ, നിങ്ങൾക്ക് കാറുകൾക്കായി ഇനിപ്പറയുന്ന റോഡ് ടെംപ്ലേറ്റുകൾ ഡൗൺലോഡ് ചെയ്ത് പ്രിന്റ് ചെയ്യാം. എല്ലാ വളയങ്ങളും തിരിവുകളും നേരായ റോഡുകളും വെട്ടിക്കളഞ്ഞുകൊണ്ടാണ് തമാശ ആരംഭിക്കുന്നത്. ഈ ടെംപ്ലേറ്റുകളിൽ നിന്ന്, ഒരു കുട്ടിക്ക് ഏത് ആകൃതിയിലും ഒരു റോഡ് നിർമ്മിക്കാൻ കഴിയും; ആവശ്യമായ A4 ഷീറ്റുകളുടെ എണ്ണം പ്രിന്റ് ചെയ്തിട്ടുണ്ടെന്ന് ഉറപ്പാക്കുക.

കാറുകൾക്കായി നേരായ റോഡ് ഡൗൺലോഡ് ചെയ്യുക

നിങ്ങൾക്ക് ഈ ഷീറ്റുകളിൽ ഏറ്റവും കൂടുതൽ ആവശ്യമായി വരും. ഒരു A4 ഷീറ്റ് പേപ്പറിൽ ഞങ്ങൾ 3 റോഡുകൾ സ്ഥാപിച്ചിട്ടുണ്ട്, അത് അച്ചടിച്ച് മുറിക്കേണ്ടതുണ്ട്. വലത് കോണിൽ റോഡ് മുറിക്കുന്നത് എങ്ങനെയെന്ന് നിങ്ങളുടെ കുട്ടിക്ക് കാണിച്ചുകൊടുക്കുക.

കാറുകൾക്കുള്ള റോഡ്: വളയം

റോഡുകൾ ബന്ധിപ്പിക്കുന്നതിന് നിങ്ങൾക്ക് ഒരു റിംഗ് ആവശ്യമാണ്, അതിന്റെ ടെംപ്ലേറ്റ് മുകളിൽ അവതരിപ്പിച്ചിരിക്കുന്നു, അവിടെ നിന്ന് നിങ്ങളുടെ ഇൻഫ്രാസ്ട്രക്ചർ നിർമ്മിക്കാൻ ആരംഭിക്കുക.

കാറുകൾക്കുള്ള റോഡ്: നേരെ തിരിയുക

അവതരിപ്പിച്ച തിരിവുകൾ ആൺകുട്ടിക്ക് ആവശ്യമുള്ള ദിശയിലേക്ക് 90 ഡിഗ്രിയിൽ റോഡ് തിരിക്കാൻ അനുവദിക്കും.

കാറുകൾക്കുള്ള റോഡിൽ മൂർച്ചയുള്ള തിരിവില്ല

താഴെ കൊടുത്തിരിക്കുന്ന A4 ടെംപ്ലേറ്റ് ഏത് ദൂരത്തിലും റോഡ് തിരിക്കാൻ നിങ്ങളെ സഹായിക്കും.