Directed graph
கணிதத்தில், மேலும் குறிப்பாக வரைபடக் கோட்பாட்டில், ஒரு இயக்கப்படும் வரைபடம் (அல்லது டிகிராஃப்) என்பது ஒரு வரைபடமாகும், இது இயக்கப்படும் விளிம்புகளால் இணைக்கப்பட்ட செங்குத்துகளின் தொகுப்பால் ஆனது, இது பெரும்பாலும் வளைவுகள் என்று அழைக்கப்படுகிறது. வரையறை முறையான சொற்களில், ஒரு இயக்கப்படும் வரைபடம் என்பது ஒரு வரிசைப்படுத்தப்பட்ட ஜோடி, இதில் V என்பது செங்குத்துகள், முனைகள் அல்லது புள்ளிகள் என்று அழைக்கப்படும் ஒரு தொகுப்பாகும்; A என்பது வளைவுகள், இயக்கப்படும் விளிம்புகள் (சில நேரங்களில் வெறுமனே A க்கு பதிலாக E என்ற தொடர்புடைய தொகுப்புடன் விளிம்புகள்), அம்புகள் அல்லது இயக்கப்படும் கோடுகள் என்று அழைக்கப்படும் வரிசைப்படுத்தப்பட்ட ஜோடி செங்குத்துகளின் தொகுப்பாகும். இது ஒரு சாதாரண அல்லது திசைதிருப்பப்படாத வரைபடத்திலிருந்து வேறுபடுகிறது, இதில் பிந்தையது வரிசைப்படுத்தப்படாத ஜோடி செங்குத்துகளின் அடிப்படையில் வரையறுக்கப்படுகிறது, அவை பொதுவாக விளிம்புகள், இணைப்புகள் அல்லது கோடுகள் என்று அழைக்கப்படுகின்றன. மேற்கூறிய வரையறை ஒரு இயக்கப்பட்ட வரைபடம் ஒரே மூல மற்றும் இலக்கு முனைகளுடன் பல அம்புகளைக் கொண்டிருக்க அனுமதிக்காது, ஆனால் சில ஆசிரியர்கள் ஒரு பரந்த வரையறையைக் கருதுகின்றனர், இது இயக்கப்பட்ட வரைபடங்கள் அத்தகைய பல வளைவுகளைக் கொண்டிருக்க அனுமதிக்கிறது (அதாவது, அவை வளைவு தொகுப்பை பல தொகுப்பாக இருக்க அனுமதிக்கின்றன). சில நேரங்களில் இந்த நிறுவனங்கள் இயக்கப்படும் பன்முகக் கல்வெட்டுகள் (அல்லது பன்முகக் கல்வெட்டுகள்) என்று அழைக்கப்படுகின்றன. மறுபுறம், மேற்கூறிய வரையறை ஒரு இயக்கப்பட்ட வரைபடத்தை சுழல்களைக் கொண்டிருக்க அனுமதிக்கிறது (அதாவது, முனைகளை நேரடியாக இணைக்கும் வளைவுகள்), ஆனால் சில ஆசிரியர்கள் ஒரு குறுகிய வரையறையைக் கருதுகின்றனர், இது இயக்கப்பட்ட வரைபடங்களை சுழல்களைக் கொண்டிருக்க அனுமதிக்காது. சுழல்கள் இல்லாத இயக்கப்படும் வரைபடங்கள் எளிய இயக்கப்படும் வரைபடங்கள் என்று அழைக்கப்படலாம், அதே நேரத்தில் சுழல்கள் கொண்ட இயக்கப்படும் வரைபடங்கள் சுழல்-டிகிராஃப்கள் என்று அழைக்கப்படலாம் (இயக்கப்படும் வரைபடத்தின் பிரிவு வகைகளைப் பார்க்கவும்). வழிநடத்தப்பட்ட வரைபடங்களின் வகைகள் துணைப்பிரிவுகள் சமச்சீர் வழிநடத்தப்பட்ட வரைபடங்கள் என்பது அனைத்து விளிம்புகளும் இரண்டு முறை தோன்றும் வரைபடங்கள், ஒவ்வொரு திசையிலும் ஒன்று (அதாவது, டிகிராஃபுக்கு சொந்தமான ஒவ்வொரு அம்புக்கும், அதனுடன் தொடர்புடைய தலைகீழ் அம்பும் அதற்கு சொந்தமானது). (அத்தகைய விளிம்பு சில நேரங்களில் "இருதரப்பு" என்று அழைக்கப்படுகிறது மற்றும் அத்தகைய வரைபடங்கள் சில நேரங்களில் "இருதரப்பு" என்று அழைக்கப்படுகின்றன, ஆனால் இது இருதரப்பு வரைபடங்களுக்கான அர்த்தத்துடன் முரண்படுகிறது.) எளிய வழிநடத்தப்பட்ட வரைபடங்கள் சுழல்கள் இல்லாத (செங்குத்துகளை நேரடியாக தங்களுக்குள் இணைக்கும் அம்புகள்) மற்றும் ஒரே மூல மற்றும் இலக்கு முனைகளுடன் பல அம்புகள் இல்லாத வரைபடங்களை இயக்குகின்றன. ஏற்கனவே அறிமுகப்படுத்தப்பட்டபடி, பல அம்புகள் இருந்தால், அந்த உருவம் பொதுவாக டைரக்ட் மல்டி கிராஃபிக் என்று அழைக்கப்படுகிறது. சில எழுத்தாளர்கள் சுழல்கள் கொண்ட டிகிராஃப்களை சுழல்-டிகிராஃப்கள் என்று விவரிக்கின்றனர். முழுமையான திசை வரைபடங்கள் எளிய திசை வரைபடங்களாகும், இதில் ஒவ்வொரு ஜோடி செங்குத்துகளும் ஒரு சமச்சீர் ஜோடி திசை வளைவுகளால் இணைக்கப்படுகின்றன (இது திசை திருப்பப்படாத முழுமையான வரைபடத்திற்கு சமம், விளிம்புகள் ஜோடி தலைகீழ் வளைவுகளால் மாற்றப்படுகின்றன). இது ஒரு முழுமையான டிகிராப் சமச்சீர் என்பதைப் பின்பற்றுகிறது. செமிகம்ப்லீட் மல்டிபார்டைட் டிகிராஃப்கள் என்பது எளிய டிகிராஃப்கள் ஆகும், இதில் வெர்டெக்ஸ் செட் வெவ்வேறு செட்களில் உள்ள x மற்றும் y செங்குத்துகளின் ஒவ்வொரு ஜோடிக்கும், x மற்றும் y க்கு இடையில் ஒரு வளைவு இருக்கும் வகையில் செட்களாக பிரிக்கப்படுகிறது. x மற்றும் y க்கு இடையில் ஒரு வளைவு அல்லது எதிர் திசைகளில் இரண்டு வளைவுகள் இருக்கலாம். அரை முழுமையடைந்த டிகிராஃப்கள் எளிய டிகிராஃப்கள் ஆகும், அங்கு ஒவ்வொரு ஜோடி செங்குத்துகளுக்கும் இடையில் ஒரு வளைவு உள்ளது. ஒவ்வொரு அரை முழுமையடைந்த டிகிராப்பும் ஒரு அற்பமான வழியில் ஒரு அரை முழுமையடைந்த பன்முக டிகிராஃப் ஆகும், ஒவ்வொரு முனையும் பகிர்வின் தொகுப்பை உருவாக்குகிறது. அரை-இடைநிலை டிகிராஃப்கள் எளிய டிகிராஃப்கள் ஆகும், இதில் x முதல் y வரையிலும், y முதல் z வரையிலும் வளைவுகளைக் கொண்ட தனித்துவமான செங்குத்துகளின் ஒவ்வொரு மூன்று x, y, z க்கும், x மற்றும் z க்கு இடையில் ஒரு வளைவு உள்ளது. x மற்றும் z க்கு இடையில் ஒரு வளைவு அல்லது எதிர் திசைகளில் இரண்டு வளைவுகள் மட்டுமே இருக்கலாம். ஒரு அரை முழுமையான டிகிராப் என்பது ஒரு அரை-இடைநிலை டிகிராப் ஆகும். கே-குவாசி-டிரான்ஸிட்டிவ் டிகிராஃப்கள் எனப்படும் குவாசி-டிரான்ஸிட்டிவ் டிகிராஃப்களின் நீட்டிப்புகள் உள்ளன. நோக்குநிலை வரைபடங்கள் என்பது எதிர் ஜோடி திசையில் உள்ள விளிம்புகள் இல்லாத திசையில் உள்ள வரைபடங்கள் ஆகும் (அதாவது. அதிகபட்சம் ஒன்று மற்றும் வரைபடத்தின் அம்புகளாக இருக்கலாம்). ஒரு திசைப்படுத்தப்பட்ட வரைபடம் 2-சுழற்சி இல்லையென்றால் மட்டுமே அது ஒரு நோக்குநிலை வரைபடம் என்பதை இது பின்பற்றுகிறது. (இது "நோக்குநிலை வரைபடத்தின்" ஒரே பொருள் அல்ல; நோக்குநிலை (வரைபடக் கோட்பாடு) ஐப் பார்க்கவும். போட்டிகள் என்பது திசைதிருப்பப்படாத முழுமையான வரைபடங்களில் ஒவ்வொரு விளிம்பிற்கும் ஒரு திசையைத் தேர்ந்தெடுப்பதன் மூலம் பெறப்படும் சார்ந்த வரைபடங்கள் ஆகும். ஒரு போட்டி என்பது அரை முழுமையடைந்த டிகிராஃப் ஆகும். ஒரு இயக்கப்படும் வரைபடத்திற்கு இயக்கப்படும் சுழற்சிகள் இல்லையென்றால் அது அசைக்லிக் ஆகும். அத்தகைய டிகிராப்பின் வழக்கமான பெயர் டைரக்ட் அசைக்ளிக் கிராஃப் (டிஏஜி) ஆகும். மல்டிட்ரீஸ் என்பது டிஏஜி ஆகும், இதில் ஒரே தொடக்க உச்சியிலிருந்து ஒரே இறுதி உச்சிக்கு இரண்டு தனித்துவமான திசைகள் இல்லை. ஓரியண்டட் மரங்கள் அல்லது பாலிட்ரிகள் மரங்களின் விளிம்புகளை (இணைக்கப்பட்ட, அசைக்ளிக் திசைதிருப்பப்படாத வரைபடங்கள்) திசைதிருப்புவதன் மூலம் உருவாகும் டிஏஜி ஆகும். வேரூன்றிய மரங்கள் என்பது திசைதிருப்பப்படாத மரத்தின் அனைத்து விளிம்புகளும் வேரிலிருந்து விலகி அல்லது திசையை நோக்கி இயக்கப்படும் மரங்கள் ஆகும் (அவை முறையே, ஆர்போரேசென்சஸ் அல்லது வெளி மரங்கள் மற்றும் மரங்களில் அழைக்கப்படுகின்றன. எடை கொண்ட இயக்கப்படும் வரைபடங்கள் (இயக்கப்படும் நெட்வொர்க்குகள் என்றும் அழைக்கப்படுகின்றன) (எளிய) இயக்கப்படும் வரைபடங்கள் அவற்றின் அம்புகளுக்கு ஒதுக்கப்பட்ட எடைகளுடன், எடை கொண்ட வரைபடங்களைப் போலவே (அவை இயக்கப்படாத நெட்வொர்க்குகள் அல்லது எடையுள்ள நெட்வொர்க்குகள் என்றும் அழைக்கப்படுகின்றன). ஓட்டம் நெட்வொர்க்குகள் எடையுள்ள இயக்கப்படும் வரைபடங்கள் ஆகும், அங்கு இரண்டு முனைகள் வேறுபடுகின்றன, ஒரு மூல மற்றும் ஒரு மூழ்கி. வேரூன்றிய வழிநடத்தப்பட்ட வரைபடங்கள் (ஓட்ட வரைபடங்கள் என்றும் அழைக்கப்படுகின்றன) டிகிராஃப்கள் ஆகும், இதில் ஒரு உச்சி வேர் என வேறுபடுத்தப்பட்டுள்ளது. கட்டுப்பாட்டு-ஓட்ட வரைபடங்கள் என்பது கணினி அறிவியலில் பயன்படுத்தப்படும் வேரூன்றிய டிகிராஃப்கள் ஆகும், இது ஒரு நிரலின் செயல்பாட்டின் போது கடந்து செல்லக்கூடிய பாதைகளின் பிரதிநிதித்துவமாக பயன்படுத்தப்படுகிறது. சமிக்ஞை-ஓட்ட வரைபடங்கள் என்பது இயக்கப்படும் வரைபடங்கள் ஆகும், இதில் முனைகள் அமைப்பு மாறிகள் மற்றும் கிளைகள் (விளிம்புகள், வளைவுகள் அல்லது அம்புகள்) ஜோடி முனைகளுக்கு இடையிலான செயல்பாட்டு இணைப்புகளைக் குறிக்கின்றன. ஓட்டம் வரைபடங்கள் என்பது நேரியல் இயற்கணித அல்லது வேறுபட்ட சமன்பாடுகளின் தொகுப்புடன் தொடர்புடைய டிகிராஃப்கள் ஆகும். மாநில வரைபடங்கள் வரையறுக்கப்பட்ட மாநில இயந்திரங்களைக் குறிக்கும் இயக்கப்படும் பன்முக எழுத்துக்கள் ஆகும். பரிமாற்ற வரைபடங்கள் என்பது வகைக் கோட்பாட்டில் பயன்படுத்தப்படும் டிகிராஃப்கள் ஆகும், இதில் செங்குத்துகள் (கணித) பொருள்களைக் குறிக்கின்றன மற்றும் அம்புகள் உருவகங்களைக் குறிக்கின்றன, ஒரே தொடக்க மற்றும் இறுதிப் புள்ளிகளைக் கொண்ட அனைத்து வழிநடத்தப்பட்ட பாதைகளும் கலவையின் மூலம் ஒரே முடிவுக்கு வழிவகுக்கும் பண்பு கொண்டது. லை குழுக்களின் கோட்பாட்டில், ஒரு க்விவர் க்யூ என்பது ஒரு இயக்க வரைபடமாகும், இது ஒரு பிரதிநிதித்துவம் V இன் வடிவத்தை ஒரு செயல்பாட்டாளராக வரையறுக்கிறது, குறிப்பாக ஃபங்க்ட்டர் வகை FinVctKF (Q) இன் ஒரு பொருள், இதில் F (Q) என்பது Q இல் உள்ள பாதைகளைக் கொண்ட இலவச வகை மற்றும் FinVctK என்பது ஒரு புலத்தின் மீது வரையறுக்கப்பட்ட பரிமாண திசையன் இடைவெளிகளின் வகை K. ஒரு க்விவரின் பிரதிநிதித்துவங்கள் அதன் செங்குத்துகளை திசையன் இடைவெளிகள் மற்றும் அதன் விளிம்புகளுடன் (எனவே பாதைகள்) அவற்றுக்கிடையேயான நேரியல் மாற்றங்களுடன் பொருந்துகின்றன, மேலும் இயற்கையான மாற்றங்கள் மூலம் மாற்றப்படுகின்றன. அடிப்படை சொற்களஞ்சியம் ஒரு வளைவு x முதல் y வரை இயக்கப்படுவதாகக் கருதப்படுகிறது; y என்பது தலை என்றும் x என்பது வளைவின் வால் என்றும் அழைக்கப்படுகிறது; y என்பது x இன் நேரடி வாரிசு என்றும் x என்பது y இன் நேரடி முன்னோடி என்றும் கூறப்படுகிறது. ஒரு பாதை x இலிருந்து y க்குச் சென்றால், y என்பது x இன் வாரிசு மற்றும் x இலிருந்து அடையக்கூடியது என்றும், x என்பது y இன் முன்னோடி என்றும் கூறப்படுகிறது. இந்த வளைவு தலைகீழ் வளைவு என்று அழைக்கப்படுகிறது. சுழல்கள் கொண்ட ஒரு பன்முகக் கல்வெட்டின் அருகாமை அணி என்பது செங்குத்துகளுடன் தொடர்புடைய வரிசைகள் மற்றும் நெடுவரிசைகளைக் கொண்ட முழு எண் மதிப்புள்ள அணி ஆகும், இதில் ஒரு முக்கோணமற்ற நுழைவு என்பது உச்சி i முதல் உச்சி j வரை வளைவுகளின் எண்ணிக்கை, மற்றும் மூலைவிட்ட நுழைவு iii என்பது உச்சி i இல் சுழல்களின் எண்ணிக்கை. ஒரு வழிநடத்தப்பட்ட வரைபடத்தின் அருகாமை அணி ஒரு தர்க்கரீதியான அணி, மற்றும் வரிசைகள் மற்றும் நெடுவரிசைகளின் வரிசைமாற்றத்திற்கு தனித்துவமானது. வழிநடத்தப்பட்ட வரைபடத்திற்கான மற்றொரு மேட்ரிக்ஸ் பிரதிநிதித்துவம் அதன் நிகழ்வு மேட்ரிக்ஸ் ஆகும். மேலும் வரையறைகளுக்கு திசையைப் பார்க்கவும். ஒரு உச்சிக்கு, ஒரு உச்சிக்கு அருகிலுள்ள தலை முனைகளின் எண்ணிக்கை உச்சியின் இன்டெக்ரி என்றும், ஒரு உச்சிக்கு அருகிலுள்ள வால் முனைகளின் எண்ணிக்கை அதன் வெளிப்புறம் என்றும் அழைக்கப்படுகிறது (மரங்களில் கிளைக்கும் காரணி என்று அழைக்கப்படுகிறது). மற்றும் விடுங்கள். v இன் இன்டெக்ரி டிகிரி − (v) என்றும் அதன் அவுட் டிகிரி டிகிரி + (v) என்றும் குறிக்கப்படுகிறது. அதன் ஒவ்வொரு வெளியேறும் வளைவுகளின் தோற்றம் என்பதால், ஒரு உச்சி ஒரு ஆதாரம் என்று அழைக்கப்படுகிறது. இதேபோல், ஒரு உச்சி ஒரு மூழ்கி என்று அழைக்கப்படுகிறது, ஏனெனில் இது அதன் ஒவ்வொரு உள்வரும் வளைவுகளின் முடிவாகும். டிகிரி கூட்டுத்தொகை சூத்திரம் கூறுகிறது, ஒரு இயக்கப்படும் வரைபடத்திற்கு, ஒவ்வொரு உச்சிக்கும், வரைபடம் ஒரு சீரான இயக்கப்படும் வரைபடம் என்று அழைக்கப்படுகிறது. டிகிரி வரிசை ஒரு வழிநடத்தப்பட்ட வரைபடத்தின் டிகிரி வரிசை அதன் இன்டெக்ரி மற்றும் அவுட்டெக்ரி ஜோடிகளின் பட்டியலாகும்; மேலே உள்ள எடுத்துக்காட்டுக்கு நம்மிடம் டிகிரி வரிசை ((2,0), (2,2), (0,2), (1,1)) உள்ளது. டிகிரி வரிசை ஒரு இயக்கப்பட்ட வரைபட மாறாதது, எனவே ஐசோமார்பிக் இயக்கப்பட்ட வரைபடங்கள் ஒரே டிகிரி வரிசையைக் கொண்டுள்ளன. இருப்பினும், டிகிரி வரிசை பொதுவாக, ஒரு இயக்கப்பட்ட வரைபடத்தை தனித்துவமாக அடையாளம் காணவில்லை; சில சந்தர்ப்பங்களில், ஐசோமார்பிக் அல்லாத டிகிராஃப்கள் ஒரே டிகிரி வரிசையைக் கொண்டுள்ளன. வழிநடத்தப்பட்ட வரைபட உணர்தல் சிக்கல் என்பது நேர்மறை முழு எண் ஜோடிகளின் கொடுக்கப்பட்ட வரிசையுடன் ஒரு வழிநடத்தப்பட்ட வரைபடத்தைக் கண்டுபிடிப்பதில் உள்ள சிக்கலாகும். (இயக்கப்படும் வரைபடத்தில் பொருத்தமான எண்ணிக்கையிலான தனிமைப்படுத்தப்பட்ட செங்குத்துகளைச் சேர்ப்பதன் மூலம் அவை அற்பமாக உணரப்படுவதால் பூஜ்ஜியங்களின் பின்தங்கிய ஜோடிகள் புறக்கணிக்கப்படலாம்.) ஒரு வரிசை, இது சில இயக்கப்படும் வரைபடத்தின் டிகிரி வரிசை, அதாவது. இயக்கப்படும் வரைபட உணர்தல் சிக்கலுக்கு ஒரு தீர்வு உள்ளது, இது ஒரு இயக்கப்படும் வரைபடம் அல்லது இயக்கப்படும் வரைபட வரிசை என்று அழைக்கப்படுகிறது. இந்த சிக்கலை க்ளைட்மேன்-வாங் வழிமுறை அல்லது ஃபுல்கர்சன்-சென்-அன்ஸ்டீ தேற்றம் மூலம் தீர்க்க முடியும். திசைதிருப்பப்படாத விளிம்புகளுடன் அனைத்து திசைதிருப்பப்பட்ட விளிம்புகளையும் மாற்றுவதன் மூலம் பெறப்பட்ட திசைதிருப்பப்படாத அடிப்படை வரைபடம் இணைக்கப்பட்ட வரைபடமாக இருந்தால், திசைதிருப்பப்பட்ட வரைபட இணைப்பு ஒரு திசைதிருப்பப்பட்ட வரைபடம் பலவீனமாக இணைக்கப்பட்டுள்ளது (அல்லது இணைக்கப்பட்டுள்ளது). ஒவ்வொரு ஜோடி செங்குத்துகளுக்கும் x முதல் y வரை (மற்றும் y முதல் x வரை) ஒரு வழிநடத்தப்பட்ட பாதையைக் கொண்டிருந்தால் ஒரு வழிநடத்தப்பட்ட வரைபடம் வலுவாக இணைக்கப்பட்டுள்ளது அல்லது வலுவானது. வலுவான கூறுகள் அதிகபட்சமாக வலுவாக இணைக்கப்பட்ட துணை வரைபடங்கள் ஆகும். ஒரு இணைக்கப்பட்ட வேரூன்றிய வரைபடம் (அல்லது ஓட்ட வரைபடம்) என்பது ஒரு தனித்துவமான வேர் முனையிலிருந்து ஒவ்வொரு உச்சிக்கும் ஒரு திசைப்படுத்தப்பட்ட பாதை உள்ளது. குறிப்புகள் குறிப்புகளையும் பார்க்கவும் (2007 ஆம் ஆண்டின் திருத்தப்பட்ட 1 வது பதிப்பு இப்போது ஆசிரியர்களின் தளத்தில் இலவசமாகக் கிடைக்கிறது; 2 வது பதிப்பு 2009 இல் தோன்றியது). . . (மின்னணு 3 வது பதிப்பு ஆசிரியரின் தளத்தில் இலவசமாகக் கிடைக்கிறது). . முழு எண் வரிசைகளின் ஆன்-லைன் என்சைக்ளோபீடியாவிலிருந்து n முனைகளுடன் இயக்கப்படும் வரைபடங்களின் எண்ணிக்கை (அல்லது இயக்கப்படும் வரைபடங்கள்) வெளிப்புற இணைப்புகள் இயக்கப்படும் வரைபடங்கள் வரைபடக் கோட்பாடு வரைபட தரவு கட்டமைப்புகள்