Nowhere-zero flow
வரைபடக் கோட்பாட்டில், எங்கும் பூஜ்ஜிய ஓட்டம் அல்லது NZ ஓட்டம் என்பது எங்கும் பூஜ்ஜியமாக இல்லாத ஒரு நெட்வொர்க் ஓட்டம் ஆகும். இது வண்ணமயமான பிளானர் வரைபடங்களுடன் நெருக்கமாக இணைக்கப்பட்டுள்ளது (இரட்டைத்தன்மை மூலம்). வரையறைகள் G = (V, E) ஒரு டிகிராஃப் ஆகவும், M ஒரு அபெலியன் குழுவாகவும் இருக்கட்டும். ஒரு வரைபடம் φ: E → M என்பது ஒரு M-சுழற்சியாகும், ஒவ்வொரு உச்சிக்கும் v ωV இல் δ + (v) என்பது v க்கு வெளியே உள்ள விளிம்புகளின் தொகுப்பைக் குறிக்கிறது மற்றும் δ− (v) என்பது v க்குள் விளிம்புகளின் தொகுப்பைக் குறிக்கிறது. சில நேரங்களில், இந்த நிபந்தனை கிர்ச்சோஃப்பின் விதி என்று குறிப்பிடப்படுகிறது. ஒவ்வொரு e ω E க்கும் φ (e)  ஒத்ததாக இருந்தால், நாம் φ ஐ எங்கும் பூஜ்ஜிய ஓட்டம், ஒரு M-ஓட்டம் அல்லது ஒரு NZ-ஓட்டம் என்று அழைக்கிறோம். k ஒரு முழு எண் மற்றும் 0 <|φ (e) | <k என்றால் φ ஒரு k-ஓட்டம். மற்ற கருத்துக்கள் G = (V, E) ஒரு திசைதிருப்பப்படாத வரைபடமாக இருக்கட்டும். ஒரு விளிம்பில் இரண்டு ஓட்டங்களின் கூட்டுத்தொகை 0 ஆகச் சேர்க்கப்படலாம் என்பதால், எம்-ஓட்டங்களின் தொகுப்பு ஒரு குழுவை உருவாக்க வேண்டிய அவசியமில்லை. (டுட்டே 1950) ஒரு வரைபடம் ஜி ஒரு |M |-ஃப்லோ இருந்தால் மட்டுமே எம்-ஃப்லோவைக் கொண்டுள்ளது. இதன் விளைவாக, ஒரு கே-ஓட்டம் இருந்தால் மட்டுமே ஒரு ஓட்டம் இருக்கும். இதன் விளைவாக G ஒரு k-ஓட்டத்தை ஏற்றுக்கொண்டால், அது ஒரு h-ஓட்டத்தை அங்கு ஏற்றுக்கொள்கிறது. நோக்குநிலை சுதந்திரம். ஒரு விளிம்பு e ஐத் தேர்ந்தெடுத்து, அதை மாற்றியமைத்து, பின்னர் φ (e) ஐ −φ (e) உடன் மாற்றுவதன் மூலம் G வரைபடத்தில் எங்கும் பூஜ்ஜிய ஓட்டத்தை மாற்றியமைக்கவும். இந்த சரிசெய்தலுக்குப் பிறகு, φ இன்னும் எங்கும் பூஜ்ஜியமாக இல்லை. மேலும், φ முதலில் ஒரு k-ஓட்டமாக இருந்தால், அதன் விளைவாக வரும் φ ஒரு k-ஓட்டமாகும். எனவே, எங்கும்-பூஜ்ஜிய எம்-ஓட்டம் அல்லது எங்கும்-பூஜ்ஜிய கே-ஓட்டம் இருப்பது வரைபடத்தின் நோக்குநிலையிலிருந்து சுயாதீனமாக உள்ளது. எனவே, G இன் சில (எனவே ஒவ்வொரு) நோக்குநிலையும் அத்தகைய ஓட்டத்தைக் கொண்டிருந்தால், ஒரு திசைதிருப்பப்படாத வரைபடம் G க்கு எங்கும் பூஜ்ஜிய M-ஓட்டம் அல்லது எங்கும் பூஜ்ஜிய k-ஓட்டம் இல்லை என்று கூறப்படுகிறது. ஓட்டம் பல்லுறுப்புக்கோவை G இல் உள்ள M-ஓட்டங்களின் எண்ணிக்கையாக இருக்கட்டும். இது நீக்குதல்-சுருக்க சூத்திரத்தை திருப்திப்படுத்துகிறதுஃ இதை தூண்டலுடன் இணைப்பது ஒரு பல்லுறுப்புக்கோவை என்பதை நாம் காட்ட முடியும், இதில் குழு M இன் வரிசை உள்ளது. G மற்றும் அபெலியன் குழு M இன் ஓட்ட பல்லுறுப்புக்கோவை என்று அழைக்கிறோம். மேலே உள்ள சம வரிசையில் உள்ள இரண்டு குழுக்கள் சம எண்ணிக்கையிலான NZ ஓட்டங்களைக் கொண்டுள்ளன என்பதைக் குறிக்கிறது. வரிசை மட்டுமே முக்கியமானது, எம் இன் அமைப்பு அல்ல. குறிப்பாக மேற்கண்ட முடிவுகள் 1953 ஆம் ஆண்டில் டூட்டே பல்லுறுப்புக்கோவையைப் படிக்கும்போது நிரூபிக்கப்பட்டன, இது ஓட்டம் பல்லுறுப்புக்கோவையின் பொதுமைப்படுத்தலாகும். ஃப்ளோ-கலரிங் டூயல்டி பிரிட்ஜ்லெஸ் பிளானர் கிராஃப்ஸ் பிரிட்ஜ்லெஸ் பிளானர் கிராஃப்ஸுக்கு கே-ஃபேஸ் வண்ணங்கள் மற்றும் கே-ஃப்ளோக்களுக்கு இடையே ஒரு டூயல்டிட்டி உள்ளது. இதைப் பார்க்க, G என்பது நிறங்களுடன் சரியான k-முகம்-நிறத்துடன் ஒரு திசைப்படுத்தப்பட்ட பாலம் இல்லாத சமதள வரைபடமாக இருக்கட்டும் பின்வரும் விதியின் மூலம் ஒரு வரைபடத்தை உருவாக்கவும்ஃ விளிம்பில் இடதுபுறத்தில் x நிற முகமும் வலதுபுறத்தில் y நிற முகமும் இருந்தால், φ (e) = x-y ஆக இருக்கட்டும். x மற்றும் y வெவ்வேறு நிறங்களாக இருக்க வேண்டும் என்பதால் φ என்பது ஒரு (NZ) k-ஓட்டம். எனவே G மற்றும் G * ஆகியவை சமதள இரட்டை வரைபடங்களாகவும், G * என்பது k-நிறமாகவும் இருந்தால் (G இன் முகங்களின் நிறம் உள்ளது), G ஒரு NZ k-ஓட்டத்தைக் கொண்டுள்ளது. |E (G) | Tutte இல் தூண்டலைப் பயன்படுத்துவது நேர்மாறும் உண்மை என்பதை நிரூபித்தது. இதை சுருக்கமாக இவ்வாறு வெளிப்படுத்தலாம்ஃ RHS என்பது ஓட்ட எண், G ஒரு k-ஓட்டத்தை அனுமதிக்கும் மிகச்சிறிய k. பொது வரைபடங்கள் பொதுவான எம்-ஓட்டங்களுக்கும் இரட்டைத்தன்மை பொருந்தும்ஃ எம் இல் உள்ள மதிப்புகளுடன் முக-வண்ண செயல்பாடாக இருக்கட்டும். r1 என்பது e இன் இடதுபுறத்தில் உள்ள முகமாகவும், r2 வலதுபுறத்தில் உள்ள இடமாகவும் வரையறுக்கவும். ஒவ்வொரு எம்-சுழற்சிக்கும் ஒரு வண்ண செயல்பாடு சி உள்ளது (தூண்டல் மூலம் நிரூபிக்கப்பட்டுள்ளது). ஒரு NZ M-ஓட்டம் (நேராக) இருந்தால் மட்டுமே c என்பது ஒரு |E (G) |-முகம்-நிறமாகும். கடைசி இரண்டு புள்ளிகளை இணைப்பதன் மூலம் இரட்டைத்தன்மை தொடர்கிறது. மேலே விவாதிக்கப்பட்ட கே-ஃப்ளோக்களுக்கான ஒத்த முடிவுகளைப் பெற நாம் நிபுணத்துவம் பெறலாம். NZ ஓட்டங்களுக்கும் வண்ணங்களுக்கும் இடையிலான இந்த இரட்டைத்தன்மையைக் கருத்தில் கொண்டு, தன்னிச்சையான வரைபடங்களுக்கு (பிளானர் மட்டுமல்ல) NZ ஓட்டங்களை வரையறுக்க முடியும் என்பதால், முக வண்ணங்களை பிளானர் அல்லாத வரைபடங்களுக்கு நீட்டிக்க இதைப் பயன்படுத்தலாம். ஒவ்வொரு உச்சிக்கும் சம டிகிரி இருந்தால் மட்டுமே பயன்பாடுகள் ஜி 2-முகம்-வண்ணமயமானது (NZ 2-ஓட்டங்களைக் கருத்தில் கொள்ளுங்கள்). க்ளீன்-4 குழுவாக இருக்கட்டும். ஒரு கன வரைபடம் 3-முனை-வண்ணமயமானதாக இருந்தால் மட்டுமே அது கே-ஓட்டத்தைக் கொண்டிருக்கும். இதன் விளைவாக 3-முனை வண்ணமயமான ஒரு கன வரைபடம் 4-முகம் வண்ணமயமானதாக இருக்கும். ஒரு NZ 4-ஓட்டத்தை அனுமதித்தால் மட்டுமே ஒரு வரைபடம் 4-முகம் வண்ணமயமானதாக இருக்கும் (நான்கு வண்ணத் தேற்றத்தைப் பார்க்கவும்). பீட்டர்சன் வரைபடத்தில் NZ 4-ஓட்டம் இல்லை, இது 4-ஓட்டம் அனுமானத்திற்கு வழிவகுத்தது (கீழே காண்க). G ஒரு முக்கோணமாக இருந்தால், ஒவ்வொரு உச்சிக்கும் சம டிகிரி இருந்தால் மட்டுமே G 3-(உச்சி) நிறமாக இருக்கும். முதல் புல்லட் மூலம், இரட்டை வரைபடம் G * 2-வண்ணமயமானது, இதனால் இருதரப்பு மற்றும் பிளானர் கனசதுரம். எனவே G * ஒரு NZ 3-ஓட்டத்தைக் கொண்டுள்ளது, இதனால் 3-முகம் வண்ணமயமானது, இது G 3-வெர்டெக்ஸை வண்ணமயமாக்குகிறது. ஒரு வளைய விளிம்புடன் எந்த வரைபடமும் சரியான உச்சி நிறத்தைக் கொண்டிருக்கவில்லை போலவே, ஒரு பாலத்துடன் எந்த வரைபடமும் எந்த குழுவிற்கும் ஒரு NZ M-ஓட்டத்தைக் கொண்டிருக்க முடியாது. மாறாக, ஒவ்வொரு பாலம் இல்லாத வரைபடமும் ஒரு NZ-ஓட்டத்தைக் கொண்டுள்ளது (ராபின்ஸின் தேற்றத்தின் ஒரு வடிவம்). k-ஓட்டங்களின் இருப்பு k இன் சிறிய மதிப்புகளுக்கு எங்கும்-பூஜ்ஜிய k-ஓட்டங்களைக் கண்டுபிடிக்க முயற்சிக்கும்போது சுவாரஸ்யமான கேள்விகள் எழுகின்றன. பின்வருபவை நிரூபிக்கப்பட்டுள்ளனஃ ஜேகரின் 4-ஓட்ட தேற்றம். ஒவ்வொரு 4-விளிம்புடன் இணைக்கப்பட்ட வரைபடமும் 4-ஓட்டத்தைக் கொண்டுள்ளது. சீமோரின் 6-ஓட்டம் தேற்றம். ஒவ்வொரு பாலம் இல்லாத வரைபடமும் 6-ஓட்டத்தைக் கொண்டுள்ளது. 3-ஓட்டம், 4-ஓட்டம் மற்றும் 5-ஓட்டம் அனுமானங்கள் 2019 ஆம் ஆண்டு நிலவரப்படி, பின்வருவன தற்போது தீர்க்கப்படவில்லை (டுட்டே காரணமாக): 3-ஓட்டம் அனுமானம். ஒவ்வொரு 4-விளிம்புடன் இணைக்கப்பட்ட வரைபடமும் எங்கும் பூஜ்ஜிய 3-ஓட்டத்தைக் கொண்டிருக்கவில்லை. 4-ஓட்டம் ஊகம். சிறியதாக பீட்டர்சன் வரைபடம் இல்லாத ஒவ்வொரு பாலம் இல்லாத வரைபடமும் எங்கும் பூஜ்ஜிய 4-ஓட்டத்தைக் கொண்டிருக்கவில்லை. 5-ஓட்டம் ஊகம். ஒவ்வொரு பாலம் இல்லாத வரைபடமும் எங்கும் பூஜ்ஜிய 5-ஓட்டத்தைக் கொண்டிருக்கவில்லை. முழுமையான வரைபடம் K11 ஒரு பீட்டர்சன் வரைபடத்தையும் 4-ஓட்டத்தையும் கொண்டிருப்பதால் 4-ஓட்டம் அனுமானத்தின் நேர்மாறாக இல்லை. பீட்டர்சன் மைனர் இல்லாத பாலம் இல்லாத கன வரைபடங்களுக்கு, ஸ்னார்க் தேற்றத்தால் 4-ஓட்டங்கள் உள்ளன (சீமோர், மற்றும் பலர் 1998, இன்னும் வெளியிடப்படவில்லை). நான்கு வண்ணத் தேற்றம் எந்த ஸ்னார்க்கும் பிளானர் அல்ல என்ற கூற்றுக்கு சமம். மேலும் காண்க சைக்கிள் ஸ்பேஸ் சைக்கிள் இரட்டை கவர் அனுமானம் நான்கு வண்ணத் தேற்றம் வரைபடம் நிறம் விளிம்பு நிறம் துட்டே பல்லுறுப்புக்கோவை குறிப்புகள் மேலும் வாசிப்பு நெட்வொர்க் ஓட்டம் சிக்கல்