Nowhere-zero flow
گراف تھیوری میں، کہیں صفر کا بہاؤ یا NZ کا بہاؤ ایک نیٹ ورک کا بہاؤ ہے جو کہیں صفر نہیں ہے۔ یہ رنگین پلانر گراف سے (دوہری طور پر) گہرا جڑا ہوا ہے۔ تعریف G = (V، E) کو ڈیگراف مان لیں اور M کو ابیلین گروپ مان لیں۔ نقشہ φ: E → M ایک M-گردش ہے اگر ہر ورٹیکس v ωV کے لیے جہاں δ + (v) v سے باہر کناروں کے سیٹ کو ظاہر کرتا ہے اور δ− (v) v میں کناروں کے سیٹ کو ظاہر کرتا ہے۔ بعض اوقات، اس حالت کو کرچوف کا قانون کہا جاتا ہے۔ اگر ہر ای کے لیے φ (e)  ऒत्त 0 ہے، تو ہم φ کو کہیں صفر بہاؤ، M بہاؤ، یا NZ بہاؤ کہتے ہیں۔ اگر k ایک عدد ہے اور 0 <|φ (e) | <k تو φ ایک k بہاؤ ہے۔ دیگر تصورات G = (V، E) کو ایک غیر ہدایت شدہ گراف ہونے دیں۔ E کی سمت بندی ایک ماڈیولر k-بہاؤ ہے اگر ہمارے پاس ہر ورٹیکس v bul V کے لیے: خصوصیات M-بہاؤ کا مجموعہ لازمی طور پر ایک گروپ نہیں بناتا ہے کیونکہ ایک کنارے پر دو بہاؤ کا مجموعہ 0 میں شامل ہو سکتا ہے۔ (ٹوٹے 1950) ایک گراف G میں M-فلو ہوتا ہے اگر اور صرف اس صورت میں جب اس میں |M |-فلو ہو۔ نتیجے کے طور پر، ایک بہاؤ موجود ہے اگر اور صرف اس صورت میں جب ایک k-بہاؤ موجود ہو۔ نتیجے کے طور پر اگر G ایک k-بہاؤ کو قبول کرتا ہے تو یہ ایک H-بہاؤ کو قبول کرتا ہے۔ سمت بندی کی آزادی۔ گراف G پر کہیں صفر کے بہاؤ φ کو ایک کنارے e کا انتخاب کرکے، اسے الٹ کر، اور پھر φ (e) کو −φ (e) سے تبدیل کر کے تبدیل کریں۔ اس ایڈجسٹمنٹ کے بعد، φ اب بھی کہیں صفر کا بہاؤ نہیں ہے۔ مزید برآں، اگر φ اصل میں ایک k-بہاؤ تھا، تو نتیجہ φ بھی ایک k-بہاؤ ہے۔ اس طرح، کہیں-صفر M-بہاؤ یا کہیں-صفر 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) | Tutte پر انڈکشن کا استعمال کرتے ہوئے ثابت ہوا کہ الٹا بھی درست ہے۔ اس کا اظہار مختصر طور پر اس طرح کیا جا سکتا ہے: جہاں RHS بہاؤ نمبر ہے، سب سے چھوٹا k جس کے لیے G k بہاؤ کی اجازت دیتا ہے۔ عمومی گراف عام ایم بہاؤ کے لیے بھی دوہری حیثیت درست ہے: ایم میں اقدار کے ساتھ چہرے کے رنگ کا فنکشن ہونے دیں۔ اس بات کی وضاحت کریں کہ کہاں r1، e کے بائیں طرف کا چہرہ ہے اور r2 دائیں طرف ہے۔ ہر ایم-سرکولیشن کے لیے ایک کلرنگ فنکشن سی ہوتا ہے جو (انڈکشن کے ذریعے ثابت ہوتا ہے)۔ c ایک |E (G) |-چہرے کا رنگ ہے اگر اور صرف اس صورت میں جب NZ M-فلو (سیدھا) ہو۔ دوہرا پن آخری دو نکات کو یکجا کرنے کے بعد آتا ہے۔ ہم اوپر بیان کردہ کے-فلوز کے لیے اسی طرح کے نتائج حاصل کرنے میں مہارت حاصل کر سکتے ہیں۔ این زیڈ کے بہاؤ اور رنگوں کے درمیان اس دوہری حیثیت کو دیکھتے ہوئے، اور چونکہ ہم صوابدیدی گرافوں کے لیے این زیڈ کے بہاؤ کی وضاحت کر سکتے ہیں (نہ کہ صرف پلینر)، ہم اسے چہرے کے رنگوں کو غیر پلینر گراف تک بڑھانے کے لیے استعمال کر سکتے ہیں۔ ایپلی کیشنز G 2 چہرے پر رنگین ہے اگر اور صرف اس صورت میں جب ہر سرے کی ڈگری یکساں ہو (NZ 2 بہاؤ پر غور کریں)۔ کلائن-4 گروپ ہونے دیں۔ پھر ایک کیوبک گراف میں K-بہاؤ ہوتا ہے اگر اور صرف اس صورت میں جب یہ 3 کنارے پر رنگین ہو۔ نتیجہ کے طور پر ایک کیوبک گراف جو 3 کنارے کا رنگین ہے 4 چہرے والا رنگین ہوتا ہے۔ ایک گراف 4 چہرے والا رنگین ہوتا ہے اگر اور صرف اس صورت میں جب یہ NZ 4 بہاؤ کی اجازت دیتا ہے (چار رنگ تھیوریم دیکھیں)۔ پیٹرسن گراف میں NZ 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 بہاؤ ہوتا ہے۔ 4 بہاؤ کے قیاس کا متصادم نہیں ہے کیونکہ مکمل گراف K11 میں پیٹرسن گراف اور 4 بہاؤ ہے۔ بغیر پل کے کیوبک گراف کے لیے جن میں کوئی پیٹرسن معمولی نہیں ہے، 4-بہاؤ اسنارک تھیوریم کے ذریعہ موجود ہیں (سیمور، اور دیگر 1998، ابھی تک شائع نہیں ہوئے ہیں)۔ چار رنگوں کا نظریہ اس بیان کے مساوی ہے کہ کوئی اسنارک پلینر نہیں ہے۔ سائیکل اسپیس سائیکل ڈبل کور قیاس چار رنگین تھیوریم گراف کلرنگ ایج کلرنگ ٹوٹے کثیر حوالہ جات مزید پڑھنے نیٹ ورک کے بہاؤ کا مسئلہ دیکھیں۔