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