Nowhere-zero flow
આલેખ સિદ્ધાંતમાં, ક્યાંય-શૂન્ય પ્રવાહ અથવા એનઝેડ પ્રવાહ એ નેટવર્ક પ્રવાહ છે જે ક્યાંય શૂન્ય નથી. તે રંગીન સમતલ આલેખ સાથે (દ્વૈત દ્વારા) ગાઢ રીતે જોડાયેલું છે. વ્યાખ્યાઓ ધારો કે G = (V, E) એ ડિગ્રાફ છે અને M એ અબેલિયન જૂથ છે. નકશો φ: E → M એ M-પરિભ્રમણ છે જો દરેક શિરોબિંદુ v ωV માટે જ્યાં δ + (v) એ v ની બહારની ધારોનો સમૂહ સૂચવે છે અને δ − (v) એ v માં ધારોનો સમૂહ સૂચવે છે. કેટલીકવાર, આ સ્થિતિને કિર્ચોફના નિયમ તરીકે ઓળખવામાં આવે છે. જો દરેક e ω E માટે φ (e)  ઒ત્ત 0 હોય, તો આપણે φ ને શૂન્ય પ્રવાહ, M-પ્રવાહ અથવા NZ-પ્રવાહ કહીએ છીએ. જો k એ પૂર્ણાંક હોય અને 0 <|φ (e) | <k હોય તો φ એ k-પ્રવાહ છે. અન્ય ધારણાઓ G = (V, E) એક દિશાહીન આલેખ છે. E ની દિશા એ મોડ્યુલર k-પ્રવાહ છે જો આપણી પાસે દરેક શિરોબિંદુ v ± V માટે હોય તોઃ ગુણધર્મો M-પ્રવાહોનો સમૂહ એક જૂથ બનાવે તે જરૂરી નથી કારણ કે એક ધાર પર બે પ્રવાહોનો સરવાળો 0 માં ઉમેરી શકે છે. (ટુટ્ટે 1950) ગ્રાફ G માં એમ-ફ્લો હોય છે જો અને માત્ર ત્યારે જ જો તેમાં |M |-ફ્લો હોય. પરિણામે, પ્રવાહ ત્યારે જ અસ્તિત્વ ધરાવે છે જ્યારે કે-પ્રવાહ અસ્તિત્વમાં હોય. પરિણામે જો G એ k-પ્રવાહ સ્વીકારે તો તે જ્યાં H-પ્રવાહ સ્વીકારે છે. અભિગમની સ્વતંત્રતા. ગ્રાફ G પર ક્યાંય શૂન્ય ન હોય તેવા પ્રવાહ φ ને ધાર e પસંદ કરીને, તેને ઉલટાવીને અને પછી φ (e) ને −φ (e) સાથે બદલીને સંશોધિત કરો. આ ગોઠવણ પછી, φ હજુ પણ શૂન્ય પ્રવાહ છે. વધુમાં, જો φ મૂળરૂપે k-પ્રવાહ હતો, તો પરિણામી φ પણ k-પ્રવાહ છે. આમ, ક્યાંય-શૂન્ય એમ-પ્રવાહ અથવા ક્યાંય-શૂન્ય કે-પ્રવાહનું અસ્તિત્વ આલેખની દિશાથી સ્વતંત્ર છે. આમ, એક દિશાહીન આલેખ G ને ક્યાંય-શૂન્ય M-પ્રવાહ અથવા ક્યાંય-શૂન્ય k-પ્રવાહ હોવાનું કહેવાય છે જો G ની કેટલીક (અને આમ દરેક) દિશા આવી પ્રવાહ ધરાવે છે. પ્રવાહ બહુપદી G પર M-પ્રવાહોની સંખ્યા હોવી જોઈએ. તે કાઢી નાંખવાના-સંકોચન સૂત્રને સંતોષે છેઃ આને ઇન્ડક્શન સાથે જોડીને આપણે બતાવી શકીએ છીએ કે બહુપદી જ્યાં જૂથ M નો ક્રમ છે. આપણે G અને અબેલિયન જૂથ M ની પ્રવાહ બહુપદી કહીએ છીએ. ઉપરોક્ત સૂચવે છે કે સમાન ક્રમના બે જૂથોમાં NZ પ્રવાહની સમાન સંખ્યા હોય છે. ક્રમ એ એકમાત્ર જૂથ પરિમાણ છે જે મહત્વનું છે, એમ. ની રચના નહીં. ખાસ કરીને જો ઉપરોક્ત પરિણામો ટુટ્ટે દ્વારા 1953 માં સાબિત કરવામાં આવ્યા હતા જ્યારે તેઓ ટુટ્ટે બહુપદીનો અભ્યાસ કરી રહ્યા હતા, જે પ્રવાહ બહુપદીનું સામાન્યીકરણ છે. પ્રવાહ-રંગ દ્વૈત બ્રિજલેસ પ્લાનર આલેખ બ્રિજલેસ પ્લાનર આલેખ માટે કે-ફેસ રંગ અને કે-ફ્લો વચ્ચે દ્વૈતતા છે. આ જોવા માટે, G ને રંગો સાથે યોગ્ય k-ચહેરો-રંગ સાથે નિર્દેશિત બ્રિજલેસ પ્લાનર ગ્રાફ દો નીચે આપેલા નિયમ દ્વારા નકશાનું નિર્માણ કરો જો ધાર e પાસે ડાબી બાજુએ x રંગનો ચહેરો અને જમણી બાજુએ y રંગનો ચહેરો હોય, તો φ (e) = x-y દો. પછી φ એ એક (NZ) k-પ્રવાહ છે કારણ કે x અને y જુદા જુદા રંગો હોવા જોઈએ. તેથી જો G અને G * સમતલીય બેવડા આલેખ હોય અને G * k-રંગીન હોય (ત્યાં G ના ચહેરાનો રંગ હોય છે), તો G પાસે NZ k-પ્રવાહ છે. |E (G) | ટુટ્ટે પર ઇન્ડક્શનનો ઉપયોગ કરીને સાબિત થયું કે વિપરીત પણ સાચું છે. આને સંક્ષિપ્તમાં આ રીતે વ્યક્ત કરી શકાય છેઃ જ્યાં RHS એ પ્રવાહ સંખ્યા છે, સૌથી નાનો k જેના માટે G એ k-પ્રવાહને મંજૂરી આપે છે. સામાન્ય આલેખ સામાન્ય એમ-પ્રવાહ માટે પણ દ્વૈતતા સાચી છેઃ એમ માં મૂલ્યો સાથે ચહેરાના રંગનું કાર્ય થવા દો. વ્યાખ્યાયિત કરો કે જ્યાં r1 એ e ની ડાબી બાજુએ ચહેરો છે અને r2 જમણી બાજુએ છે. દરેક એમ-પરિભ્રમણ માટે એક રંગ કાર્ય સી હોય છે જે (ઇન્ડક્શન દ્વારા સાબિત). c એ |E (G) |-ફેસ-કલરિંગ છે જો અને માત્ર ત્યારે જ જો તે NZ M-ફ્લો (સીધો) હોય. છેલ્લા બે બિંદુઓને જોડીને દ્વૈતતા અનુસરવામાં આવે છે. આપણે ઉપર ચર્ચા કરેલા કે-ફ્લો માટે સમાન પરિણામો મેળવવા માટે નિષ્ણાત બની શકીએ છીએ. એનઝેડ પ્રવાહ અને રંગ વચ્ચેની આ દ્વૈતતાને જોતાં, અને આપણે મનસ્વી આલેખ (માત્ર સમતલીય નહીં) માટે એનઝેડ પ્રવાહને વ્યાખ્યાયિત કરી શકીએ છીએ, તેથી આપણે આનો ઉપયોગ ચહેરાના રંગને બિન-સમતલીય આલેખ સુધી વિસ્તારવા માટે કરી શકીએ છીએ. એપ્લિકેશન્સ જી 2-ચહેરો-રંગીન હોય છે જો અને માત્ર ત્યારે જ જો દરેક શિરોબિંદુ સમાન ડિગ્રી ધરાવે (એનઝેડ 2-પ્રવાહને ધ્યાનમાં લો). ચાલો ક્લેઈન-4 જૂથ બનીએ. પછી ક્યુબિક ગ્રાફમાં કે-પ્રવાહ હોય છે જો અને માત્ર ત્યારે જ જો તે 3-ધાર-રંગીન હોય. પરિણામે 3 ધારનો રંગીન ઘન આલેખ 4-ચહેરો રંગીન હોય છે. ગ્રાફ 4-ચહેરો રંગીન હોય છે જો અને માત્ર ત્યારે જ જો તે NZ 4-પ્રવાહને મંજૂરી આપે (જુઓ ચાર રંગ પ્રમેય). પીટરસન આલેખમાં એનઝેડ 4-પ્રવાહ નથી, અને આ 4-પ્રવાહ અનુમાન તરફ દોરી ગયો (નીચે જુઓ). જો G એ ત્રિકોણ હોય તો G એ 3-(શિરોબિંદુ) રંગીન હોય છે જો અને માત્ર ત્યારે જ જો દરેક શિરોબિંદુ સમ ડિગ્રી હોય. પ્રથમ ગોળી દ્વારા, બેવડો આલેખ G * 2-રંગીન હોય છે અને આમ દ્વિપક્ષી અને સમતલ ઘન હોય છે. તેથી G * પાસે NZ 3-પ્રવાહ છે અને આમ તે 3-ચહેરો રંગીન છે, જે G 3-વર્ટેક્સને રંગીન બનાવે છે. જેમ લૂપ ધારવાળા કોઈ ગ્રાફમાં યોગ્ય શિરોબિંદુ રંગ હોતો નથી, તેમ બ્રિજ સાથેના કોઈ ગ્રાફમાં કોઈપણ જૂથ એમ માટે એનઝેડ એમ-ફ્લો હોઈ શકતો નથી. તેનાથી વિપરીત, દરેક બ્રિજલેસ ગ્રાફમાં એનઝેડ-ફ્લો હોય છે (રોબિન્સના પ્રમેયનું એક સ્વરૂપ). k-પ્રવાહોનું અસ્તિત્વ જ્યારે k ના નાના મૂલ્યો માટે ક્યાંય-શૂન્ય k-પ્રવાહ શોધવાનો પ્રયાસ કરવામાં આવે ત્યારે રસપ્રદ પ્રશ્નો ઉભા થાય છે. નીચેની બાબતો સાબિત થઈ છેઃ જેગરની 4-પ્રવાહ પ્રમેય. દરેક 4-ધાર-જોડાયેલ આલેખમાં 4-પ્રવાહ હોય છે. સીમોરની 6-પ્રવાહ પ્રમેય. દરેક બ્રિજલેસ ગ્રાફમાં 6-પ્રવાહ હોય છે. 3-પ્રવાહ, 4-પ્રવાહ અને 5-પ્રવાહના અનુમાનો 2019 સુધીમાં, નીચેના હાલમાં વણઉકેલાયેલા છે (ટુટ્ટેને કારણે): 3-પ્રવાહ અનુમાન. દરેક 4-ધાર-જોડાયેલ આલેખમાં ક્યાંય-શૂન્ય 3-પ્રવાહ નથી. 4-પ્રવાહ અનુમાન. દરેક બ્રિજલેસ ગ્રાફ કે જેમાં નાના તરીકે પીટરસન ગ્રાફ નથી, તેમાં શૂન્ય-શૂન્ય 4-પ્રવાહ હોય છે. 5-પ્રવાહ અનુમાન. દરેક બ્રિજલેસ ગ્રાફમાં ક્યાંય-શૂન્ય 5-પ્રવાહ હોય છે. સંપૂર્ણ આલેખ K11માં પીટરસન આલેખ અને 4-પ્રવાહ હોવાથી 4-પ્રવાહના અનુમાનનું વિપરીત લાગતું નથી. પીટરસન નાના વગરના બ્રિજલેસ ક્યુબિક આલેખ માટે, સ્નાર્ક પ્રમેય (સીમોર, એટ અલ 1998, હજુ સુધી પ્રકાશિત નથી) દ્વારા 4-પ્રવાહ અસ્તિત્વમાં છે. ચાર રંગ પ્રમેય એ નિવેદનની સમકક્ષ છે કે કોઈ સ્નાર્ક સમતલીય નથી. સાયકલ સ્પેસ સાયકલ ડબલ કવર અનુમાન ફોર કલર થીયરમ ગ્રાફ કલરિંગ એજ કલરિંગ ટુટ્ટે બહુપદી સંદર્ભો વધુ વાંચન નેટવર્ક પ્રવાહ સમસ્યા જુઓ.