சுவாரஸ்யமான நிலவரைபட சிக்கல்கள்

டோனால்ட் நத் (Donald Knuth), கணிணி நிரலாக்க கலையின் நான்காவது தொகுப்பை உருவாக்கி கொண்டு இருக்கிறார். அதன் அத்தியாங்களில் மிகச் சுவாரஸ்யமான ஒன்றாக எனக்குத் தோன்றியது, பைனரி முடிவு வரைபடங்கள் மற்றும் அதன் பயன்பாடுகள்.

பல சுவாரஸ்யமான நிலவரைபட பிரச்சினைகளை பூலியன் சூத்திரங்களாக குறிப்பிட முடியும் என்றும், அதிலிருந்து பெறப்படும் பைனரி முடிவு வரைபடங்கள், அந்த பிரச்சினைகளுக்கான அனைத்து தீர்வுகளையும் கொண்டுள்ளது எனவும் நத்  குறிப்பிட்டுள்ளார். சில வகை தேர்ந்தெடுக்கும் வரைமுறைகள் இருந்தாலும், எளிய ‘மாறும் நிரலாக்க நெறிமுறை’ மூலம் பைனரி முடிவு வரைபடங்களிருந்து ‘சிறந்த’ தீர்வை பிரித்தெடுப்பது மிகவும் எளிதாகும்.

48 தொடர்ச்சியான மாநிலங்களை குறிப்பிடும் ஒரு வரைப்படத்தை கொண்டு, இங்கே சில உதாரணங்களை கொடுத்துள்ளோம். ஒவ்வொரு சந்தியும் ஒரு மாநிலத்தை குறிப்பிடுகிறது. எல்லைகளை பகிர்ந்து கொள்ளும் இரு மாநிலங்களுக்கு இடையில் ஒரு விளிம்பும் வரையப்பட்டுள்ளது. ஒவ்வொரு நிலவரைபடத்திற்கும், அதன் படத்தை நீங்கள் சொடுக்கினால், SVG வடிவமைப்பில் அதற்கான ஆதார ஆவணத்தை அடைவீர்கள்.

 

தலைநகர் சுற்றுபயணம்

ஒருவேளை, நீங்கள் 48 மாநிலத்தின் தலைநகரையும் சுற்றி பார்க்க வேண்டும். ஆனால் ஒரு மாநிலத்தை ஒரு முறைதான் கடந்து வர வேண்டும் எனக் கொள்வொம்.(வேறு வார்த்தைகளில் சொன்னால், வரைபடத்தில் நீங்கள் ஒரு ஹாமில்டானியன் பாதையை கண்டுபிடிக்க வேண்டும்). மேலே கொடுக்கப்பட்டுள்ள வரைபடத்திலிருந்தே காணலாம். மாநிலங்களின் தலைநகரங்களுக்கு இடையேயான மிகவும் நேரடியான பாதையை பின்பற்றினாலும் கூட நீங்கள் அடிக்கடி மற்றொரு மாநிலத்தை கடந்து செல்வீர்கள் அல்லது நீங்கள் மிச்சிகன் மாநிலத்தின் தலைநகரான லான்சிங்கிளிருந்து புறப்பட்டு, விஸ்கொன்சின் மாநிலத்தின் தலைநகரான மேடிசனுக்கு செல்ல மிச்சிகன் ஏரியை கடந்து செல்வீர்கள். அதற்கு பதிலாக, நீங்கள், பயணத்தின் ஒவ்வொரு பகுதியின் போதும், இரு மாநிலங்களுக்கு இடையேயான குறுகிய பயணப் பாதையை தேர்ந்தெடுக்க வேண்டும். இத்தகைய பயணப் பாதைகளைத் தான் நாம் “தலைநகர் சுற்றுபயணம்” என்று அழைக்கிறோம். மாநிலங்களுக்கு இடையேயான அனுமதிக்கக்கப்பட்ட பாதைகளின் வரைபடம் இங்கே கொடுக்கப்பட்டுள்ளது.

ஒரு எளிய பகுப்பாய்வின் அடிப்படையிலும் நத்தின் முயற்சிகளைக் கொண்டும் நாம் பின்வருமாரு கூறலாம்.

  • மேய்ன் ஒரே ஒரு அண்டை மாநிலத்தை கொண்டு இருப்பதால், அனைத்து சுற்றுலாவும் மேய்னில் தொடங்க வேண்டும் அல்லது மேய்னில் முடிய வேண்டும். நாம் மேய்னை ஆரம்ப புள்ளியாக பயன்படுத்துவோம்.
  • நியூயார்க் ஒரு இணைப்பு புள்ளியாக இருப்பதால், அனைத்து சுற்றுலாவும் நியூயார்க்குக்கு அப்பால் முடிவடையும்.
  • ஒட்டுமொத்தமாக 68,656,026 வெவ்வேறு தலைநகர் சுற்றுப்பயணங்கள் உள்ளன.

மொத்தம் 11,698 மைல்கள் கொண்ட குறுகிய தலைநகர் சுற்றுபயணம் இங்கே கொடுக்கப்பட்டுள்ளது.

 

மொத்தம் 18,040 மைல்கள் கொண்ட மிக நீண்ட தலைநகர் சுற்றுபயணம்  இங்கே கொடுக்கப்பட்டுள்ளது.

வரைபட வண்ணமிடுதல்

இன்னொரு சுவாரஸ்யமான சிக்கல் நிலவரைபடத்திற்கு வண்ணமிடுதல். இதற்கான விதி,  இரண்டு அண்டை மாநிலங்களும் ஒரே நிறத்தில் இருக்க கூடாது. பிரபலமான ‘நான்கு நிறத் தேற்ற’மானது, அடுத்தடுத்துள்ள இரண்டு பகுதிகள், ஒரே நிறத்தை கொண்டிராதவாறு நிறந்தீட்டுவதற்கு நான்கு நிறங்களே போதுமானது என்று கூறுகிறது.

ஒரு பைனரி முடிவு வரைபடம், ஒரு பூலியன் சூத்திரத்திற்கு சாத்தியமான எல்லா தீர்வுகளையும் குறிப்பிடுவதால், எத்தனை தீர்வுகள் உள்ளன என்பதை நாம் எளிதாக கணக்கிட முடியும்.

தொடர்ச்சியான 48 மாநிலங்களை வண்ணமிடுவதற்கு, 533,816,322,048 சாத்தியமான நிறங்கள் உள்ளன. (இது நத் கூறியதில் ½ மட்டுமே. அவருடைய நில வரைபடமானது 49 வது மாநிலமாக வாஷிங்டனை (கொலம்பியாவின் மாவட்டம்) கொண்டுள்ளது மற்றும் இதற்கு மேரிலாண்ட் மற்றும் விர்ஜினியாவில் பயன்படுத்தப்படாத இரண்டு வண்ணங்களில் ஒன்று ஒதுக்கப்படலாம்). இங்கே சில சுவாரஸ்யமான சிறப்பு வண்ணமிடுதலுக்கான உதாரணங்கள் கொடுக்கப்பட்டுள்ளது.

  • இது ஒரு சீரான வண்ணமிடுதல், இதில் ஒவ்வொரு நிறமும் சரியாக 12 மாநிலங்களுக்கு பயன்படுத்தப்படுகிறது. இது போன்று 12,554,677,864 முறை வண்ணமிடலாம், வியத்தக்க வகையில் இது அனைத்து சாத்தியமான வண்ணமிடுதலை விட 2.4% அதிகமாகும்.

  • இது ஒரு சீரற்ற வண்ணமிடுதல், இதில் ஏதேனும் ஒரு நிறம் (பச்சை) முடிந்தவரை குறைவாக பயன்படுத்தப்படுகிறது (2 மாநிலங்கள்).ஒரே வண்ணம் இருமுறை பயன்படுத்தப்படுவதால் வரைபடத்தை வண்ணமாக்க 288 வழிகள் உள்ளன.

  • இது ஒரு சீரற்ற வண்ணமிடுதல், இதில் ஏதேனும் ஒரு நிறம் (மஞ்சள்) முடிந்தவரை அதிகமாக பயன்படுத்தப்படுகிறது (18 மாநிலங்கள்). ஒரு வண்ணம் 18 முறை பயன்படுத்தப்படுத்தபடுவதால் வரைபடத்தை வண்ணமாக்க 71,002,368 வழிகள் உள்ளன.

  • இரண்டயும் இணைத்து, நிறங்களைக் கொண்டு 2, 13,15 மற்றும் 18 முறைகள் வண்ணமிடலாம்.இந்த வரிசை 1) இடமிருந்து வலம், அடுத்தடுத்து ஒவ்வொரு நிறத்தையும் குறைந்த எண்ணிக்கை முறையில் பயன்படுத்துகிறது மற்றும் 2) வலமிருந்து இடம், அடுத்தடுத்து ஒவ்வொரு நிறத்தையும் அதிக எண்ணிக்கை முறையில் பயன்படுத்துகிறது. இது போன்று 24 தீர்வுகள் உள்ளன.

வரைபட வண்ணமிடுதலின் கண்ணோட்டத்தில், அமெரிக்காவின் 48 மாநிலங்களின் நிலவரைபடம் மிகவும் எளிமையானது. இன்னும் சவாலான நிலவரைபடத்திற்கு, McGregor Graph வலைப்பக்கத்தைப் பார்க்கவும்.