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