Circuit rank
வரைபடக் கோட்பாட்டில், கணிதத்தின் ஒரு கிளை, சுற்று தரவரிசை, சுழற்சி எண், சுழற்சி தரவரிசை அல்லது திசைதிருப்பப்படாத வரைபடத்தின் பூஜ்யம் என்பது வரைபடத்திலிருந்து அகற்றப்பட வேண்டிய குறைந்தபட்ச விளிம்புகளின் எண்ணிக்கை, அதன் அனைத்து சுழற்சிகளையும் உடைத்து, அதை ஒரு மரம் அல்லது காடாக மாற்றுகிறது. இது வரைபடத்தில் உள்ள சுயாதீன சுழற்சிகளின் எண்ணிக்கைக்கு சமம் (ஒரு சுழற்சி அடிப்படையின் அளவு). இயக்கப்படும் வரைபடங்களுக்கான தொடர்புடைய பின்னூட்ட வளைவு தொகுப்பு சிக்கலைப் போலல்லாமல், கொடுக்கப்பட்ட வரைபடத்தில் உள்ள விளிம்புகளின் எண்ணிக்கை, செங்குத்துகளின் எண்ணிக்கை மற்றும் இணைக்கப்பட்ட கூறுகளின் எண்ணிக்கை ஆகிய சூத்திரத்தைப் பயன்படுத்தி சுற்று தரவரிசை எளிதில் கணக்கிடப்படுகிறது. பேராசை வழிமுறையைப் பயன்படுத்தி அல்லது பரவியிருக்கும் காடுகளை பூர்த்தி செய்வதன் மூலம் அனைத்து சுழற்சிகளையும் திறம்பட உடைக்கும் குறைந்தபட்ச அளவிலான விளிம்புகளை உருவாக்கவும் முடியும். சர்க்யூட் தரவரிசையை இயற்கணித வரைபடக் கோட்பாட்டின் அடிப்படையில் ஒரு வரைபடத்தின் சுழற்சி இடத்தின் பரிமாணமாகவும், மேட்ராய்டு கோட்பாட்டின் அடிப்படையில் ஒரு கிராஃபிக் மேட்ராய்டின் கொராங்காகவும், இடவியல் அடிப்படையில் ஒரு இடவியல் இடத்தின் பெட்டி எண்களில் ஒன்றாகவும் விளக்கலாம். இது வரைபடத்தின் காது சிதைவில் காதுகளை கணக்கிடுகிறது, கிட்டத்தட்ட மரங்களில் அளவுரு சிக்கலின் அடிப்படையை உருவாக்குகிறது, மேலும் ஒரு குறியீட்டின் சுழற்சி சிக்கலின் வரையறையின் ஒரு பகுதியாக மென்பொருள் அளவீடுகளில் பயன்படுத்தப்படுகிறது. சைக்ளோமாட்டிக் எண் என்ற பெயரில், இந்த கருத்தை குஸ்டாவ் கிர்ச்சோஃப் அறிமுகப்படுத்தினார். மேட்ராய்டு தரவரிசை மற்றும் குறைந்தபட்ச பின்னூட்ட விளிம்பு தொகுப்பின் கட்டுமானம் மேட்ராய்டு கோட்பாட்டைப் பயன்படுத்தி ஒரு வரைபடத்தின் சுற்று தரவரிசையை மேட்ராய்டின் கிராஃபிக் மேட்ராய்டின் கொராங்க் என்று விவரிக்கலாம். மேட்ராய்டுகளின் பேராசை பண்பைப் பயன்படுத்தி, ஒரு பேராசை வழிமுறையைப் பயன்படுத்தி அனைத்து சுழற்சிகளையும் உடைக்கும் குறைந்தபட்ச விளிம்புகளைக் கண்டறியலாம், இது ஒவ்வொரு கட்டத்திலும் மீதமுள்ள வரைபடத்தின் குறைந்தபட்சம் ஒரு சுழற்சியைச் சேர்ந்த ஒரு விளிம்பைத் தேர்ந்தெடுக்கிறது. மாற்றாக, அனைத்து சுழற்சிகளையும் உடைக்கும் குறைந்தபட்ச விளிம்புகளின் தொகுப்பை ஒரு பரவலான காட்டை உருவாக்குவதன் மூலமும், பரவியிருக்கும் காட்டைச் சேராத விளிம்புகளின் நிரப்பு தொகுப்பைத் தேர்ந்தெடுப்பதன் மூலமும் காணலாம். சுயாதீன சுழற்சிகளின் எண்ணிக்கை இயற்கணித வரைபடக் கோட்பாட்டில், சுற்று தரவரிசையும் சுழற்சி இடத்தின் பரிமாணமாகும். உள்ளுணர்வாக, சுற்று தரவரிசை வரைபடத்தில் உள்ள சுயாதீன சுழற்சிகளின் எண்ணிக்கையை கணக்கிடுகிறது, அங்கு சுழற்சிகளின் தொகுப்பு சுயாதீனமாக இருக்கும், மற்றவற்றின் சில துணைக்குழுக்களின் சமச்சீர் வேறுபாட்டாக சுழற்சிகளில் ஒன்றை உருவாக்க முடியாவிட்டால். சுயாதீன சுழற்சிகளின் இந்த எண்ணிக்கையை இடவியல் பிரிவான ஹோமோலஜி கோட்பாட்டைப் பயன்படுத்தி விளக்கலாம். எந்தவொரு வரைபடத்தையும் 1 பரிமாண எளிய சிக்கலான ஒரு எடுத்துக்காட்டாக பார்க்க முடியும், ஒவ்வொரு வரைபட விளிம்பையும் ஒரு கோடு பிரிவால் பிரதிநிதித்துவப்படுத்துவதன் மூலமும், இந்த கோடு பிரிவுகளை அவற்றின் இறுதிப் புள்ளிகளில் ஒன்றாக இணைப்பதன் மூலமும் உருவாக்கப்பட்ட ஒரு வகை இடவியல் இடைவெளி. சுழற்சி எண் என்பது இந்த வளாகத்தின் முதல் (முழு எண்) ஒத்தவியல் குழுவின் தரவரிசையாகும், இந்த இடவியல் இணைப்பின் காரணமாக, ஒரு வரைபடத்தின் சுழற்சி எண் முதல் பெட்டி எண் என்றும் அழைக்கப்படுகிறது. மேலும் பொதுவாக, எந்தவொரு இடவியல் இடத்தின் முதல் பெட்டி எண், அதே வழியில் வரையறுக்கப்படுகிறது, விண்வெளியில் சுயாதீன சுழற்சிகளின் எண்ணிக்கையை கணக்கிடுகிறது. பயன்பாடுகள் மெஷெட்னஸ் குணகம் பிளானர் வரைபடங்களுக்கான சுற்று தரவரிசையின் ஒரு மாறுபாடு, அதே உச்சி தொகுப்புடன் எந்தவொரு பிளானர் வரைபடத்தின் அதிகபட்ச சுற்று தரவரிசையால் வகுப்பதன் மூலம் இயல்பாக்கப்படுகிறது, இது மெஷெட்னஸ் குணகம் என்று அழைக்கப்படுகிறது. விளிம்புகள் மற்றும் செங்குத்துகளுடன் இணைக்கப்பட்ட சமதள வரைபடத்திற்கு, இணைப்புக் குணகத்தை இந்த சூத்திரத்தால் கணக்கிட முடியும் இங்கே, சூத்திரத்தின் எண் கொடுக்கப்பட்ட வரைபடத்தின் சுற்று தரவரிசையாகும், மேலும் வகுத்தல் என்பது-வெர்டெக்ஸ் சமதள வரைபடத்தின் மிகப்பெரிய சாத்தியமான சுற்று தரவரிசையாகும். மெஷெட்னஸ் குணகம் மரங்களுக்கு 0 க்கும் அதிகபட்ச பிளானர் வரைபடங்களுக்கு 1 க்கும் இடையில் இருக்கும். காது சிதைவு சுற்று தரவரிசை ஒரு வரைபடத்தின் காது சிதைவில் காதுகளின் எண்ணிக்கையைக் கட்டுப்படுத்துகிறது, இது வரைபடத்தின் விளிம்புகளை பாதைகள் மற்றும் சுழற்சிகளாக பிரிப்பது பல வரைபட வழிமுறைகளில் பயனுள்ளதாக இருக்கும். குறிப்பாக, திறந்த காது சிதைவு இருந்தால் மட்டுமே ஒரு வரைபடம் 2-வெர்டெக்ஸ்-இணைக்கப்பட்டுள்ளது. இது துணை வரைபடங்களின் வரிசையாகும், இதில் முதல் துணை வரைபடம் ஒரு எளிய சுழற்சி, மீதமுள்ள துணை வரைபடங்கள் அனைத்தும் எளிய பாதைகள், ஒவ்வொரு பாதையும் முந்தைய துணை வரைபடங்களைச் சேர்ந்த செங்குத்துகளில் தொடங்கி முடிவடைகிறது, மேலும் ஒரு பாதையின் ஒவ்வொரு உள் முனையும் அந்த பாதையில் முதல் முறையாகத் தோன்றும். சுற்று தரவரிசை கொண்ட எந்த இரு இணைக்கப்பட்ட வரைபடத்திலும், ஒவ்வொரு திறந்த காது சிதைவுக்கும் சரியாக காதுகள் உள்ளன. ஏறத்தாழ மரங்கள் சுழற்சி எண் கொண்ட ஒரு வரைபடம் r-அருகிலுள்ள-மரம் என்றும் அழைக்கப்படுகிறது, ஏனெனில் அதை ஒரு மரம் அல்லது காடாக மாற்ற வரைபடத்திலிருந்து r விளிம்புகளை மட்டுமே அகற்ற வேண்டும். 1-க்கு அருகில் உள்ள மரம் என்பது அருகிலுள்ள மரமாகும்ஃ இணைக்கப்பட்ட அருகிலுள்ள மரம் என்பது ஒரு போலி மரம், ஒவ்வொரு முனையிலும் வேரூன்றிய (ஒருவேளை அற்பமான) மரத்தைக் கொண்ட ஒரு சுழற்சி. பல எழுத்தாளர்கள் ஆர்-அருகிலுள்ள மரங்கள் மீது வரைபட வழிமுறைகளின் அளவுரு சிக்கலை ஆய்வு செய்துள்ளனர். இயக்கப்பட்ட வரைபடங்களுக்கான பொதுமைப்படுத்தல்கள் சுழற்சி தரவரிசை என்பது இயக்கப்பட்ட வரைபடங்களின் மாறாதது, இது வரைபடத்தில் சுழற்சிகளின் கூடு கட்டும் அளவை அளவிடுகிறது. இது சுற்று தரவரிசையை விட மிகவும் சிக்கலான வரையறையைக் கொண்டுள்ளது (திசைதிருப்பப்படாத வரைபடங்களுக்கான மர ஆழத்தின் வரையறையுடன் நெருக்கமாக தொடர்புடையது) மற்றும் கணக்கிடுவது மிகவும் கடினம். சுற்று தரவரிசை தொடர்பான இயக்கப்படும் வரைபடங்களுக்கான மற்றொரு சிக்கல் குறைந்தபட்ச பின்னூட்ட வளைவு தொகுப்பாகும், இது அனைத்து இயக்கப்படும் சுழற்சிகளையும் உடைக்கும் மிகச்சிறிய விளிம்புகளின் தொகுப்பாகும். சுழற்சி தரவரிசை மற்றும் குறைந்தபட்ச பின்னூட்ட வளைவு தொகுப்பு இரண்டும் கணக்கிட NP-கடினமானவை. விளிம்புகளின் திசைகளை புறக்கணிப்பதன் மூலமும், அடிப்படை திசைதிருப்பப்படாத வரைபடத்தின் சுற்று தரவரிசையை கணக்கிடுவதன் மூலமும் இயக்கப்படும் வரைபடங்களின் எளிய மாறுபாட்டைக் கணக்கிட முடியும். இந்த கொள்கை சுழற்சி சிக்கலின் வரையறையின் அடிப்படையை உருவாக்குகிறது, இது கணினி குறியீட்டின் ஒரு பகுதி எவ்வளவு சிக்கலானது என்பதை மதிப்பிடுவதற்கான ஒரு மென்பொருள் அளவீடு ஆகும். வேதியியல் மற்றும் கெமின்ஃபார்மட்டிக்ஸ் துறைகளில், ஒரு மூலக்கூறு வரைபடத்தின் சுற்று தரவரிசை (மிகச்சிறிய வளையங்களின் மிகச்சிறிய தொகுப்பில் உள்ள வளையங்களின் எண்ணிக்கை) சில நேரங்களில் ஃப்ரெரேஜாக் எண் என்று குறிப்பிடப்படுகிறது. அளவுரு சிக்கலானது வரைபடங்களில் உள்ள சில கணக்கீட்டு சிக்கல்கள் பொதுவாக NP-கடினமானவை, ஆனால் ஒரு சிறிய சுற்று தரவரிசை கொண்ட வரைபடங்களுக்கு பல்லுறுப்புக்கோவை நேரத்தில் தீர்க்கப்படலாம். பாதை மறுசீரமைப்பு சிக்கல் ஒரு எடுத்துக்காட்டு. தொடர்புடைய கருத்துக்கள் வரைபடங்களிலிருந்து விஷயங்களை நீக்கும் வகையில் வரையறுக்கப்பட்ட பிற எண்கள்ஃ விளிம்பு இணைப்பு-வரைபடத்தைத் துண்டிக்க குறைந்தபட்சம் நீக்க வேண்டிய விளிம்புகள்; பொருந்தக்கூடிய முன் விலக்கு-ஒரு சரியான பொருத்தம் இருப்பதை தடுக்க நீக்க வேண்டிய குறைந்தபட்ச விளிம்புகள்; பின்னூட்ட உச்சி செட் எண்-வரைபடத்தை அசைக்ளிக் செய்ய நீக்க வேண்டிய குறைந்தபட்ச செங்குத்துகளின் எண்ணிக்கை; பின்னூட்ட வளைவு செட்-இயக்கப்பட்ட வரைபடத்திலிருந்து நீக்க வேண்டிய குறைந்தபட்ச வளைவுகளின் எண்ணிக்கை, அதை அசைக்ளிக் செய்ய. குறிப்புகள் வரைபட மாறிலிகள் மேட்ராய்டு கோட்பாடு பரவலான மரம்