Graph canonization
கிராஃப் கோட்பாட்டில், கணிதத்தின் ஒரு கிளை, கிராஃப் கேனோனைசேஷன் என்பது கொடுக்கப்பட்ட கிராஃப் G இன் நியதி வடிவத்தைக் கண்டுபிடிப்பதில் உள்ள சிக்கலாகும். ஒரு நியதி வடிவம் என்பது G க்கு ஐசோமார்பிக் என்று பெயரிடப்பட்ட கிராஃப் கேனான் (G) ஆகும், இது G க்கு ஐசோமார்பிக் ஆகும், அதாவது G க்கு ஐசோமார்பிக் இருக்கும் ஒவ்வொரு கிராஃப்பும் G ஐப் போலவே நியதி வடிவத்தைக் கொண்டுள்ளது. எனவே, கிராஃப் கேனோனைசேஷன் சிக்கலுக்கான தீர்விலிருந்து, கிராஃப் ஐசோமார்பிசத்தின் சிக்கலையும் ஒருவர் தீர்க்க முடியும்ஃ G மற்றும் H ஆகிய இரண்டு கிராஃப்கள் ஐசோமார்பிக் என்பதைச் சோதிக்க, அவற்றின் நியதி வடிவங்கள் கேனான் (G) மற்றும் கேனான் (H) ஐக் கணக்கிடுங்கள், மேலும் இந்த இரண்டு நியதி வடிவங்களும் ஒரே மாதிரியானவையா என்பதைச் சோதிக்கவும். ஒரு வரைபடத்தின் நியதி வடிவம் ஒரு முழுமையான வரைபட மாறிலிக்கு ஒரு எடுத்துக்காட்டுஃ ஒவ்வொரு இரண்டு ஐசோமார்பிக் வரைபடங்களும் ஒரே நியதி வடிவத்தைக் கொண்டுள்ளன, மேலும் ஒவ்வொரு இரண்டு ஐசோமார்பிக் அல்லாத வரைபடங்களும் வெவ்வேறு நியதி வடிவங்களைக் கொண்டுள்ளன. மாறாக, வரைபடங்களின் ஒவ்வொரு முழுமையான மாறுபாடும் ஒரு நியம வடிவத்தை உருவாக்க பயன்படுத்தப்படலாம். ஒரு n-வெர்டெக்ஸ் வரைபடத்தின் உச்சி தொகுப்பு 1 முதல் n வரையிலான முழு எண்களுடன் அடையாளம் காணப்படலாம், மேலும் அத்தகைய அடையாளத்தைப் பயன்படுத்தி ஒரு வரைபடத்தின் நியதி வடிவத்தை அதன் உச்சிகளின் வரிசைமாற்றமாகவும் விவரிக்கலாம். ஒரு வரைபடத்தின் நியமன வடிவங்கள் நியமன முத்திரைகள் என்றும் அழைக்கப்படுகின்றன, மேலும் வரைபட நியமனம் சில நேரங்களில் வரைபட நியமனம் என்றும் அழைக்கப்படுகிறது. கணக்கீட்டு சிக்கலானது, கிராஃப் கேனோனைசேஷன் சிக்கல் குறைந்தபட்சம் கிராஃப் ஐசோமார்பிசம் சிக்கலைப் போலவே கணக்கீட்டு ரீதியாக கடினமானது. உண்மையில், கிராஃப் ஐசோமார்பிசம் கிராஃப் கனோனைசேஷனுக்கு AC0-குறைக்கப்படக்கூடியது. இருப்பினும், இரண்டு சிக்கல்களும் பல்லுறுப்புக்கோவை நேரத்திற்கு சமமானவையா என்பது இன்னும் ஒரு திறந்த கேள்வியாக உள்ளது. வரைபட ஐசோமார்பிசத்திற்கான (தீர்மானகரமான) பல்லுறுப்புக்கோவை வழிமுறைகள் இருப்பது இன்னும் கணக்கீட்டு சிக்கலான கோட்பாட்டில் ஒரு திறந்த சிக்கலாக இருந்தாலும், 1977 ஆம் ஆண்டில் லாஸ்லோ பாபாய் குறைந்தது 1-எக்ஸ்ப் (-ஓ (என்)) நிகழ்தகவுடன், ஒரு எளிய வெர்டெக்ஸ் வகைப்பாட்டு வழிமுறை அனைத்து என்-வெர்டெக்ஸ் வரைபடங்களின் தொகுப்பிலிருந்து சீரற்ற முறையில் ஒரே மாதிரியாக தேர்ந்தெடுக்கப்பட்ட வரைபடத்தின் நியதி முத்திரையை உருவாக்குகிறது என்று அறிவித்தார். சிறிய மாற்றங்கள் மற்றும் கூடுதல் ஆழம்-முதல் தேடல் படி ஆகியவை நேரியல் எதிர்பார்க்கப்பட்ட நேரத்தில் ஒரே சீராக தேர்ந்தெடுக்கப்பட்ட சீரற்ற வரைபடங்களின் நியமன லேபிளிங்கை உருவாக்குகின்றன. பல அறிக்கையிடப்பட்ட கிராஃப் ஐசோமார்பிசம் வழிமுறைகள் ஏன் நடைமுறையில் நன்றாக செயல்படுகின்றன என்ற உண்மையை இந்த முடிவு வெளிச்சம் போட்டுக் காட்டுகிறது. இது நிகழ்தகவு சிக்கலான கோட்பாட்டில் ஒரு முக்கியமான திருப்புமுனையாக இருந்தது, இது அதன் கையெழுத்துப் பிரதி வடிவத்தில் பரவலாக அறியப்பட்டது, மேலும் இது ஒரு சிம்போசியத்தில் அறிவிக்கப்பட்ட நீண்ட காலத்திற்குப் பிறகும் "வெளியிடப்படாத கையெழுத்துப் பிரதி" என்று மேற்கோள் காட்டப்பட்டது. பொதுவாக அறியப்பட்ட நியம வடிவம் ஐசோமார்பிசம் வகுப்பிற்குள் அகரவரிசை ரீதியாக மிகச்சிறிய வரைபடமாகும், இது அகரவரிசை ரீதியாக மிகச்சிறிய அருகாமை மேட்ரிக்ஸைக் கொண்ட வகுப்பின் வரைபடமாகும், இது ஒரு நேரியல் சரமாகக் கருதப்படுகிறது. இருப்பினும், அகராதியியல் ரீதியாக மிகச்சிறிய வரைபடத்தின் கணக்கீடு NP-கடினமானது. மரங்களைப் பொறுத்தவரை, O (n) இடம் தேவைப்படும் ஒரு சுருக்கமான பல்லுறுப்புக்கோவை நியமன வழிமுறை வழங்கப்படுகிறது. ஒவ்வொரு உச்சியையும் சரம் 01 உடன் முத்திரை குத்துவதன் மூலம் தொடங்கவும். ஒவ்வொரு இலை அல்லாத x க்கும் x இன் லேபிளிலிருந்து முன்னணி 0 மற்றும் பின்தங்கிய 1 ஐ அகற்றவும்; பின்னர் x இன் லேபிளை அருகிலுள்ள அனைத்து இலைகளின் லேபிள்களுடன் அகராதி வரிசையில் வரிசைப்படுத்தவும். இந்த வரிசைப்படுத்தப்பட்ட லேபிள்களை இணைத்து, ஒரு முன்னணி 0 மற்றும் பின்தங்கிய 1 ஐ மீண்டும் சேர்க்கவும், இதை x இன் புதிய லேபிளாக மாற்றவும், அருகிலுள்ள இலைகளை நீக்கவும். இரண்டு செங்குத்துகள் எஞ்சியிருந்தால், அவற்றின் முத்திரைகளை அகர வரிசைப்படி இணைக்கவும். பயன்பாடுகள் கிராஃப் கேனோனைசேஷன் என்பது பல கிராஃப் ஐசோமார்பிசம் வழிமுறைகளின் சாராம்சமாகும். முன்னணி கருவிகளில் ஒன்று நௌட்டி ஆகும். கிராஃப் கேனோனைசேஷனின் பொதுவான பயன்பாடு கிராஃபிக் தரவு சுரங்கத்தில், குறிப்பாக வேதியியல் தரவுத்தள பயன்பாடுகளில் உள்ளது. ரசாயனப் பொருட்களுக்கான பல அடையாளங்காட்டிகள், எஸ். எம். ஐ. எல். இ. எஸ் மற்றும் இன்சி போன்றவை அவற்றின் கணக்கீட்டில் நியமனம் படிகளைப் பயன்படுத்துகின்றன, இது அடிப்படையில் மூலக்கூறைக் குறிக்கும் வரைபடத்தின் நியமனம் ஆகும். இந்த அடையாளங்காட்டிகள் மூலக்கூறு தகவல்களை குறியாக்கம் செய்வதற்கும், தரவுத்தளங்களிலும் இணையத்திலும் அத்தகைய தகவல்களைத் தேடுவதற்கு வசதியாக ஒரு நிலையான (மற்றும் சில நேரங்களில் மனிதனால் படிக்கக்கூடிய) வழியை வழங்க வடிவமைக்கப்பட்டுள்ளன. குறிப்புகள் வரைபடக் கோட்பாடு