Lucchesi–Younger theorem
ہدایت شدہ گرافوں کی ریاضی میں، لوچیسی-ینگ تھیوریم ڈکٹس اور ڈیجوائنز کے درمیان تعلق ہے۔ اسے 1978 میں کلاڈیو ایل لوچیسی اور ڈینیل ایچ ینگر نے شائع کیا تھا۔ ان کے ثبوت نے ایک قیاس آرائی کو حل کیا جو تقریبا ایک دہائی قبل ینگر کے ذریعہ پیش کیا گیا تھا، اور نیل رابرٹسن کے غیر شائع شدہ کام میں، جو جوڑ اور فیڈ بیک آرک سیٹوں کے درمیان پلانر گراف میں دوہری سے متاثر تھا۔ ڈکٹ عمودی حصوں کو دو ذیلی سیٹوں میں اس طرح تقسیم کرنا ہے کہ تقسیم کو عبور کرنے والے تمام کنارے ایک ہی سمت میں ایسا کرتے ہیں۔ ڈاجائن کناروں کا ایک ذیلی مجموعہ ہے جو، جب سکڑتا ہے، تو مضبوطی سے جڑا ہوا گراف تیار کرتا ہے۔ مساوی طور پر، یہ کناروں کا ایک ذیلی مجموعہ ہے جس میں ہر ڈکٹ سے کم از کم ایک کنارہ شامل ہوتا ہے۔ اگر ڈکٹوں کا مجموعہ تمام جداگانہ ہے، تو کسی بھی ڈجوائن میں ان ڈکٹوں میں سے ہر ایک کا کم از کم ایک کنارہ ہونا چاہیے، اور اس کا سائز کم از کم مجموعہ کے سائز کے برابر ہونا چاہیے۔ لہذا، کسی بھی گراف میں جداگانہ ڈکٹوں کی زیادہ سے زیادہ تعداد کسی ڈاجائن کے کم سے کم سائز سے کم یا اس کے برابر ہونی چاہیے۔ لوچیسی-ینگ تھیوریم میں کہا گیا ہے کہ یہ تعلق ہمیشہ ایک مساوات ہے۔ ڈیجوائن کا کم از کم سائز ڈیجوائنٹ ڈکٹ کی زیادہ سے زیادہ تعداد کے برابر ہوتا ہے جو کسی دیئے گئے گراف میں پایا جا سکتا ہے۔ حوالہ جات ڈائریکٹڈ گراف