Dicut
ریاضی میں، ڈکٹ ایک ہدایت شدہ گراف کے عمودی حصوں کو دو ذیلی سیٹوں میں تقسیم کرنا ہے، تاکہ دونوں ذیلی سیٹوں میں اختتامی نقطہ رکھنے والے ہر کنارے کو پہلے ذیلی سیٹ سے دوسرے تک ہدایت دی جائے۔ گراف کے ہر مضبوطی سے جڑے ہوئے جزو کو مکمل طور پر دو ذیلی سیٹوں میں سے کسی ایک میں ہونا چاہیے، لہذا مضبوطی سے جڑے ہوئے گراف میں کوئی غیر معمولی ڈکٹ نہیں ہوتا ہے۔ ڈکٹ میں دو ذیلی سیٹوں میں سے دوسرا، عمودی کا ایک ذیلی سیٹ جس میں کوئی کنارے نہیں ہوتے ہیں جو ذیلی سیٹ سے باہر نکلتے ہیں، کو بندش کہا جاتا ہے۔ بندش کا مسئلہ ایک ڈکٹ کو تلاش کرنے کا الگورتھمک مسئلہ ہے، ایک کنارے کے وزن والے ڈائریکٹڈ گراف میں، جس کا کل وزن جتنا ممکن ہو اتنا بڑا ہے۔ اسے کثیر الجہتی وقت میں حل کیا جا سکتا ہے۔ پلانر گراف میں، ڈکٹ اور سائیکل دوہرے تصورات ہیں۔ ایک ہدایت شدہ گراف کا دوہری گراف، جو سطح میں سرایت کرتا ہے، ایک گراف ہوتا ہے جس میں دیئے گئے گراف کے ہر چہرے کے لیے ایک عمودی ہوتا ہے، اور دو دوہری عمودی کے درمیان ایک دوہری کنارے ہوتا ہے جب متعلقہ دو چہرے ایک کنارے سے الگ ہوتے ہیں۔ ہر دوہری کنارہ گراف کے اصل کناروں میں سے ایک کو عبور کرتا ہے، جو 90 ڈگری گھڑی کی سمت مڑ جاتا ہے۔ دیئے گئے گراف میں ایک ڈکٹ کے لیے، ڈکٹ کو عبور کرنے والے کناروں کے ڈوئلز ڈوئل گراف میں ایک ڈائریکٹڈ سائیکل بناتے ہیں، اور اس کے برعکس۔ ڈیجوائن کو کناروں کے ایک سیٹ کے طور پر بیان کیا جا سکتا ہے جو تمام ڈکٹوں کو عبور کرتا ہے۔ جب ڈیجوائن کے کناروں کو سکڑا جاتا ہے، تو نتیجہ ایک مضبوطی سے جڑا ہوا گراف ہوتا ہے۔ ووڈال کا قیاس، جو اس علاقے میں ایک غیر حل شدہ مسئلہ ہے، بیان کرتا ہے کہ کسی بھی ہدایت شدہ گراف میں ڈکٹ میں کناروں کی کم از کم تعداد (غیر وزن شدہ کم از کم بندش) گراف میں پائے جانے والے جداگانہ جوڑوں کی زیادہ سے زیادہ تعداد (جوڑوں کی پیکنگ) کے برابر ہوتی ہے۔ جیک ایڈمنڈز اور رک جائلز کے پیش کردہ قیاس آرائی کے ایک جزوی وزن والے ورژن کی تردید الیگزینڈر شریجور نے کی تھی۔ دوسری سمت میں، لوچیسی-ینگ تھیوریم بیان کرتا ہے کہ ڈائیجوائن کا کم از کم سائز کسی دیئے گئے گراف میں پائے جانے والے جداگانہ ڈکٹوں کی زیادہ سے زیادہ تعداد کے برابر ہوتا ہے۔ حوالہ جات ڈائریکٹڈ گراف