Nowhere-zero flow
গ্রাফ তত্ত্বে, কোথাও-শূন্য প্রবাহ বা এনজেড প্রবাহ হল এমন একটি নেটওয়ার্ক প্রবাহ যা কোথাও শূন্য নয়। এটি রঙিন প্ল্যানার গ্রাফের সাথে ঘনিষ্ঠভাবে সংযুক্ত (দ্বৈততা দ্বারা)। সংজ্ঞাগুলি ধরা যাক জি = (ভি, ই) একটি ডিগ্রাফ এবং এম একটি আবেলিয়ান গ্রুপ। একটি মানচিত্র φ: E → M একটি এম-সঞ্চালন হয় যদি প্রতিটি শীর্ষে v ωV-এর জন্য যেখানে δ + (v), v-এর বাইরে প্রান্তের সেটকে নির্দেশ করে এবং δ− (v), v-এর মধ্যে প্রান্তের সেটকে নির্দেশ করে। কখনও কখনও, এই শর্তটিকে কির্চফের সূত্র হিসাবে উল্লেখ করা হয়। যদি প্রতিটি e ω E-এর জন্য φ (e) ω0 হয়, তাহলে আমরা φ-কে কোথাও-শূন্য প্রবাহ, একটি M-প্রবাহ বা একটি NZ-প্রবাহ বলি। যদি k একটি পূর্ণসংখ্যা হয় এবং 0 <|φ (e)। <k হয় তবে φ একটি k-প্রবাহ। অন্যান্য ধারণাগুলি ধরা যাক জি = (ভি, ই) একটি অনির্দিষ্ট গ্রাফ। E-এর অভিমুখীকরণ হল একটি মডুলার k-প্রবাহ যদি আমাদের প্রতিটি শীর্ষে v ωV থাকেঃ বৈশিষ্ট্য এম-প্রবাহের সেটটি অগত্যা একটি গ্রুপ গঠন করে না কারণ একটি প্রান্তে দুটি প্রবাহের যোগফল 0-তে যোগ হতে পারে। (টুটে 1950) একটি গ্রাফ জি-এর একটি এম-প্রবাহ থাকে যদি এবং শুধুমাত্র যদি এটির একটি |M।-প্রবাহ থাকে। ফলস্বরূপ, একটি প্রবাহ বিদ্যমান থাকে যদি এবং শুধুমাত্র যদি একটি কে-প্রবাহ বিদ্যমান থাকে। ফলস্বরূপ, যদি জি একটি কে-প্রবাহ স্বীকার করে তবে এটি যেখানে একটি এইচ-প্রবাহ স্বীকার করে। অভিমুখীকরণের স্বাধীনতা। একটি গ্রাফ জি-তে শূন্য-শূন্য প্রবাহ φ-কে একটি প্রান্ত e বেছে নিয়ে, এটিকে বিপরীত করে এবং তারপর φ (e)-কে −φ (e) দিয়ে প্রতিস্থাপন করে পরিবর্তন করুন। এই সমন্বয়ের পরে, φ এখনও শূন্য-শূন্য প্রবাহ। উপরন্তু, যদি φ মূলত একটি k-প্রবাহ হয়, তবে ফলস্বরূপ φ একটি k-প্রবাহও হয়। সুতরাং, কোথাও-শূন্য এম-প্রবাহের অস্তিত্ব বা কোথাও-শূন্য কে-প্রবাহের অস্তিত্ব গ্রাফের অভিযোজন থেকে স্বাধীন। সুতরাং, একটি অনির্দিষ্ট গ্রাফ জি-এর কোথাও-শূন্য এম-প্রবাহ বা কোথাও-শূন্য কে-প্রবাহ রয়েছে বলে বলা হয় যদি জি-এর কিছু (এবং এইভাবে প্রতিটি) অভিযোজনের এই ধরনের প্রবাহ থাকে। প্রবাহ বহুপদী ধরা যাক জি-তে এম-প্রবাহের সংখ্যা। এটি মুছে ফেলার-সংকোচনের সূত্রকে সন্তুষ্ট করেঃ প্রবর্তনের সাথে এটি একত্রিত করে আমরা দেখাতে পারি যে একটি বহুপদী যেখানে গ্রুপ এম-এর ক্রম। আমরা জি এবং আবেলিয়ান গ্রুপ এম-এর প্রবাহ বহুপদী বলি। উপরেরটি বোঝায় যে সমান ক্রমের দুটি গোষ্ঠীর এনজেড প্রবাহের সমান সংখ্যা রয়েছে। ক্রমটিই একমাত্র গ্রুপ প্যারামিটার যা গুরুত্বপূর্ণ, এম-এর কাঠামো নয়। বিশেষত যদি উপরের ফলাফলগুলি 1953 সালে টুট দ্বারা প্রমাণিত হয় যখন তিনি টুট বহুপদ অধ্যয়ন করছিলেন, যা প্রবাহ বহুপদের একটি সাধারণীকরণ। প্রবাহ-রঙ দ্বৈততা ব্রিজলেস প্ল্যানার গ্রাফ ব্রিজলেস প্ল্যানার গ্রাফের জন্য কে-ফেস রঙ এবং কে-প্রবাহের মধ্যে দ্বৈততা রয়েছে। এটি দেখার জন্য, জি-কে রং সহ সঠিক কে-ফেস-রঙ সহ একটি নির্দেশিত ব্রিজলেস প্ল্যানার গ্রাফ হিসাবে ধরা যাক নিম্নলিখিত নিয়ম অনুসারে একটি মানচিত্র তৈরি করুনঃ যদি ই প্রান্তের বাম দিকে x রঙের একটি মুখ এবং ডানদিকে y রঙের একটি মুখ থাকে, তবে ধরা যাক φ (e) = x-y। তারপর φ হল একটি (NZ) k-প্রবাহ যেহেতু x এবং y অবশ্যই ভিন্ন রঙ হতে হবে। সুতরাং যদি জি এবং জি * সমতলীয় দ্বৈত গ্রাফ হয় এবং জি * কে-রঙিন হয় (জি-এর মুখগুলির একটি রঙ থাকে), তবে জি-এর একটি এনজেড কে-প্রবাহ রয়েছে। |E (G)। টুটের উপর ইন্ডাকশন ব্যবহার করে প্রমাণিত হয়েছে যে বিপরীতটিও সত্য। এটিকে সংক্ষেপে এভাবে প্রকাশ করা যেতে পারেঃ যেখানে আর. এইচ. এস হল প্রবাহ সংখ্যা, সবচেয়ে ছোট কে যার জন্য জি একটি কে-প্রবাহের অনুমতি দেয়। সাধারণ গ্রাফ সাধারণ এম-প্রবাহের ক্ষেত্রেও দ্বৈততা সত্যঃ এম-এ মান সহ মুখ-রঙ ফাংশন হতে দিন। যেখানে r1 হল ই-এর বাম দিকের মুখ এবং r2 ডান দিকে রয়েছে তা নির্ধারণ করুন। প্রতিটি এম-সঞ্চালনের জন্য একটি রঙিন ফাংশন সি রয়েছে যা (আনয়ন দ্বারা প্রমাণিত)। সি হল একটি |E (জি)।-ফেস-কালারিং যদি এবং শুধুমাত্র যদি একটি এনজেড এম-ফ্লো (সোজা) হয়। দ্বৈততা শেষ দুটি পয়েন্ট একত্রিত করে অনুসরণ করে। আমরা উপরে আলোচিত কে-প্রবাহের জন্য অনুরূপ ফলাফল পেতে বিশেষজ্ঞ হতে পারি। এনজেড প্রবাহ এবং রঙগুলির মধ্যে এই দ্বৈততার পরিপ্রেক্ষিতে, এবং যেহেতু আমরা নির্বিচারে গ্রাফের জন্য এনজেড প্রবাহকে সংজ্ঞায়িত করতে পারি (কেবল সমতলীয় নয়), তাই আমরা এটি অ-সমতলীয় গ্রাফগুলিতে মুখের রঙ প্রসারিত করতে ব্যবহার করতে পারি। অ্যাপ্লিকেশন জি 2-মুখ-রঙিন হয় যদি এবং শুধুমাত্র যদি প্রতিটি শীর্ষে জোড় ডিগ্রি থাকে (এনজেড 2-প্রবাহ বিবেচনা করুন)। ধরা যাক ক্লেইন-4 গ্রুপ। তারপর একটি ঘন গ্রাফের একটি কে-প্রবাহ থাকে যদি এবং শুধুমাত্র যদি এটি 3-প্রান্ত-রঙিন হয়। ফলস্বরূপ একটি ঘন গ্রাফ যা 3-প্রান্তের রঙিন হয় তা 4-মুখের রঙিন হয়। একটি গ্রাফ 4-মুখ রঙিন হয় যদি এবং শুধুমাত্র যদি এটি একটি এনজেড 4-প্রবাহের অনুমতি দেয় (চারটি রঙের উপপাদ্য দেখুন)। পিটারসেন গ্রাফের একটি এনজেড 4-প্রবাহ নেই, এবং এটি 4-প্রবাহ অনুমানের দিকে পরিচালিত করে (নীচে দেখুন)। যদি জি একটি ত্রিভুজ হয় তবে জি 3-(শীর্ষ) রঙিন হয় যদি এবং শুধুমাত্র যদি প্রতিটি শীর্ষে জোড় ডিগ্রি থাকে। প্রথম বুলেট দ্বারা, দ্বৈত গ্রাফ জি * 2-রঙিন এবং এইভাবে দ্বিদলীয় এবং সমতল ঘন। সুতরাং জি *-এর একটি এনজেড 3-প্রবাহ রয়েছে এবং এইভাবে 3-মুখ রঙিন, যা জি 3-ভার্টেক্সকে রঙিন করে তোলে। ঠিক যেমন একটি লুপ প্রান্ত সহ কোনও গ্রাফের সঠিক শীর্ষ রঙ থাকে না, তেমনি একটি সেতু সহ কোনও গ্রাফের কোনও গ্রুপ এম-এর জন্য এনজেড এম-প্রবাহ থাকতে পারে না। বিপরীতভাবে, প্রতিটি ব্রিজলেস গ্রাফের একটি এনজেড-প্রবাহ থাকে (রবিন্সের উপপাদ্যের একটি রূপ)। কে-প্রবাহের অস্তিত্ব কে-এর ছোট মানের জন্য কোথাও-শূন্য কে-প্রবাহ খুঁজে বের করার চেষ্টা করার সময় আকর্ষণীয় প্রশ্ন উত্থাপিত হয়। নিম্নলিখিতগুলি প্রমাণিত হয়েছেঃ জেগারের 4-প্রবাহ উপপাদ্য। প্রতিটি 4-প্রান্ত-সংযুক্ত গ্রাফের একটি 4-প্রবাহ রয়েছে। সেমুরের 6-প্রবাহ উপপাদ্য। প্রতিটি ব্রিজলেস গ্রাফের একটি 6-প্রবাহ থাকে। 3-প্রবাহ, 4-প্রবাহ এবং 5-প্রবাহ অনুমান 2019 সালের হিসাবে, নিম্নলিখিতগুলি বর্তমানে অমীমাংসিত (টুট্টের কারণে): 3-প্রবাহ অনুমান। প্রতিটি 4-প্রান্ত-সংযুক্ত গ্রাফের কোথাও-শূন্য 3-প্রবাহ থাকে না। 4-প্রবাহ অনুমান। প্রতিটি ব্রিজলেস গ্রাফ যার পিটারসেন গ্রাফ মাইনর হিসাবে নেই তার কোথাও-শূন্য 4-প্রবাহ থাকে না। 5-প্রবাহ অনুমান। প্রতিটি সেতুহীন গ্রাফের কোথাও-শূন্য 5-প্রবাহ থাকে না। 4-প্রবাহ অনুমানের বিপরীতটি ধরে রাখে না কারণ সম্পূর্ণ গ্রাফ কে11-এ একটি পিটারসেন গ্রাফ এবং একটি 4-প্রবাহ রয়েছে। পিটারসেন মাইনর ছাড়া ব্রিজলেস কিউবিক গ্রাফের জন্য, স্নার্ক উপপাদ্য দ্বারা 4-প্রবাহ বিদ্যমান (সেমুর, এট আল 1998, এখনও প্রকাশিত হয়নি)। চার রঙের উপপাদ্যটি এই বিবৃতির সমতুল্য যে কোনও স্নার্ক সমতল নয়। আরও দেখুন সাইকেল স্পেস সাইকেল ডাবল কভার কনজেকচার ফোর কালার থিওরেম গ্রাফ কালারিং এজ কালারিং টুটে পলিনোমিয়াল রেফারেন্স আরও পড়া নেটওয়ার্ক প্রবাহ সমস্যা