Tutte theorem
گراف تھیوری کے ریاضیاتی شعبے میں ٹٹ تھیوریم، جس کا نام ولیم تھامس ٹٹ کے نام پر رکھا گیا ہے، کامل ملاپ کے ساتھ محدود غیر ہدایت شدہ گراف کی خصوصیت ہے۔ یہ ہال کے شادی کے نظریہ کو دو طرفہ سے صوابدیدی گراف تک عام کرنا ہے۔ یہ ٹوٹے برج فارمولے کا ایک خاص معاملہ ہے۔ وجدان مقصد ان تمام گرافوں کو نمایاں کرنا ہے جن میں کامل مماثلت نہیں ہے۔ کامل مماثلت کے بغیر گراف کے سب سے واضح کیس سے شروع کریں: عمودی کی ایک عجیب تعداد کے ساتھ ایک گراف۔ اس طرح کے گراف میں، کوئی بھی مماثل کم از کم ایک بے مثال سرے کو چھوڑ دیتا ہے، لہذا یہ کامل نہیں ہو سکتا۔ قدرے زیادہ عام صورت ایک منقطع گراف ہے جس میں ایک یا زیادہ اجزاء میں عمودی حصوں کی ایک عجیب تعداد ہوتی ہے (چاہے عمودی حصوں کی کل تعداد یکساں ہی کیوں نہ ہو)۔ آئیے اس طرح کے اجزاء کو عجیب اجزاء کہتے ہیں۔ کسی بھی مماثلت میں، ہر سرے کو صرف ایک ہی جزو کے عمودی حصوں سے ملایا جا سکتا ہے۔ لہذا، کوئی بھی ملاپ ہر عجیب جزو میں کم از کم ایک بے مثال سرے کو چھوڑ دیتا ہے، لہذا یہ کامل نہیں ہو سکتا۔ اگلا، گراف G پر ایک ورٹیکس u کے ساتھ اس طرح غور کریں کہ، اگر ہم G سے ورٹیکس u اور اس کے ملحقہ کناروں کو ہٹاتے ہیں، تو باقی گراف (اشارہ کردہ) میں دو یا زیادہ عجیب اجزاء ہوتے ہیں۔ جیسا کہ اوپر بتایا گیا ہے، کوئی بھی مماثل پتے، ہر عجیب جزو میں، کم از کم ایک ورٹیکس جو اسی جزو کے دوسرے عمودی حصوں سے بے مثال ہو۔ اس طرح کا ورٹیکس صرف u سے ملایا جا سکتا ہے۔ لیکن چونکہ دو یا دو سے زیادہ بے مثال سرے ہیں، اور ان میں سے صرف ایک کو یو سے ملایا جا سکتا ہے، کم از کم ایک اور سرے بے مثال رہتا ہے، اس لیے ملاپ کامل نہیں ہے۔ آخر میں، ایک گراف G پر غور کریں جس میں عمودی حصوں کا ایک مجموعہ ہو، اگر ہم G سے عمودی حصوں کو اور ان سے ملحقہ تمام کناروں کو ہٹا دیں، تو باقی گراف (اشارہ شدہ) میں عجیب اجزاء سے زیادہ ہوتے ہیں۔ جیسا کہ اوپر بیان کیا گیا ہے، کوئی بھی ملاپ ہر عجیب جزو میں کم از کم ایک بے مثال سرے کو چھوڑ دیتا ہے، اور ان کو صرف کے سرے سے ملایا جا سکتا ہے-لیکن ان تمام بے مثال سرے کے لیے کافی سرے نہیں ہیں، اس لیے ملاپ کامل نہیں ہے۔ ہم ایک ضروری شرط پر پہنچ چکے ہیں: اگر G کا کامل ملاپ ہے، تو G میں ہر ورٹیکس سب سیٹ کے لیے، گراف میں زیادہ تر عجیب اجزاء ہوتے ہیں۔ ٹوٹے کا نظریہ کہتا ہے کہ یہ شرط کامل مماثلت کے وجود کے لیے ضروری اور کافی دونوں ہے۔ ٹوٹے کا نظریہ ایک گراف، ایک کامل مماثلت رکھتا ہے اگر اور صرف اس صورت میں جب اس کے ہر ذیلی سیٹ کے لیے، ذیلی گراف میں زیادہ سے زیادہ عجیب اجزاء ہوں (منسلک اجزاء جن میں عمودی کی ایک عجیب تعداد ہو)۔ ثبوت پہلے ہم شرط لکھتے ہیں: جہاں سے متاثر ہونے والے ذیلی گراف کے عجیب اجزاء کی تعداد کی نشاندہی ہوتی ہے۔ کی ضرورت: اس سمت پر پہلے ہی ذیل کے سیکشن انٹوئشن میں تبادلہ خیال کیا گیا تھا، لیکن آئیے یہاں ثبوت کا خلاصہ کریں۔ ایک کامل مماثلت کے ساتھ گراف پر غور کریں۔ آئیے ایک صوابدیدی ذیلی سیٹ بنیں۔ حذف کریں۔ ایک صوابدیدی عجیب جزو ہونے دیں۔ چونکہ ایک کامل مماثلت تھی، اس لیے کم از کم ایک سرے کو سرے سے ملایا جانا چاہیے۔ لہذا، ہر عجیب جزو میں کم از کم ایک ورٹیکس ہوتا ہے جس میں ایک ورٹیکس ہوتا ہے۔ چونکہ ہر ایک ورٹیکس زیادہ سے زیادہ ایک منسلک جزو کے ساتھ اس سلسلے میں ہو سکتا ہے (اس کی وجہ یہ ہے کہ یہ ایک کامل مماثلت میں زیادہ سے زیادہ ایک بار مماثل ہوتا ہے)۔ کی کافییت: آئیے ایک صوابدیدی گراف ہو جس میں کوئی کامل ملاپ نہ ہو۔ ہمیں ایک نام نہاد ٹوٹے خلاف ورزی کرنے والا ملے گا، یعنی اس طرح کا ایک ذیلی مجموعہ۔ ہم فرض کر سکتے ہیں کہ یہ ایج میکسمل ہے، یعنی، ہر کنارے کے لیے ایک بہترین مماثلت ہے جو پہلے سے موجود نہیں ہے۔ درحقیقت، اگر ہمیں ایج میکسمل گراف میں ٹوٹے کی خلاف ورزی کرنے والا مل جاتا ہے، تو پھر اس کے ہر پھیلے ہوئے ذیلی گراف میں بھی ٹوٹے کی خلاف ورزی کرنے والا ہے، کیونکہ اس کے ہر عجیب جزو کو ممکنہ طور پر مزید اجزاء میں تقسیم کیا جائے گا جن میں سے کم از کم ایک پھر سے عجیب ہوگا۔ ہم ڈگری کے ساتھ عمودی سیٹ ہونے کی وضاحت کرتے ہیں۔ پہلے ہم اس معاملے پر غور کرتے ہیں جہاں کے تمام اجزاء مکمل گراف ہیں۔ پھر ٹوٹے کی خلاف ورزی کرنے والا ہونا پڑتا ہے، کیونکہ اگر، تو ہم ہر عجیب جزو سے ایک ورٹیکس کو ایک ورٹیکس کے ساتھ ملا کر اور دیگر تمام عمودی حصوں کو جوڑ کر ایک کامل ملاپ تلاش کر سکتے ہیں (یہ تب تک کام کرے گا جب تک کہ عجیب نہ ہو، لیکن پھر ٹوٹے کی خلاف ورزی کرنے والا ہو)۔ اب فرض کریں کہ یہ اس کا ایک جزو ہے اور اس طرح کے عمودی ہیں۔ آئیے سب سے چھوٹے راستے پر پہلے عمودی ہوں۔ یہ یقینی بناتا ہے کہ اور۔ چونکہ، اس طرح کا ایک ورٹیکس موجود ہے۔ کے کنارے-زیادہ سے زیادہ سے، ہم ایک کامل مماثلت کے طور پر اور ایک کامل مماثلت کے طور پر بیان کرتے ہیں۔ یقینی طور پر اس کا مشاہدہ کریں۔ اس میں زیادہ سے زیادہ راستہ ہونے دیں جو ایک کنارے سے شروع ہوتا ہے اور جس کے کنارے اور کے درمیان بدلتے ہیں۔ کیسے ختم ہو سکتا ہے؟ جب تک کہ ہم 'خاص' سرے پر نہیں پہنچتے جیسے کہ یا، ہم ہمیشہ جاری رکھ سکتے ہیں: اس سے مماثل ہے، اس لیے اس کا پہلا کنارہ اندر نہیں ہے، اس لیے دوسرا سرے ایک مختلف کنارے سے مماثل ہے اور ہم اس طریقے سے جاری رکھتے ہیں۔ آئیے کے آخری سرے کو ظاہر کرتے ہیں۔ اگر کا آخری کنارہ اندر ہے، تو ہونا چاہیے، کیونکہ بصورت دیگر ہم ایک کنارے کے ساتھ جاری رکھ سکتے ہیں (یہاں تک کہ پہنچنے کے لیے یا)۔ اس صورت میں ہم وضاحت کرتے ہیں۔ اگر کا آخری کنارہ اندر ہے، تو یقینی طور پر اسی طرح کی وجہ سے اور ہم اس کی وضاحت کرتے ہیں۔ اب ہر دوسرے کنارے کے ساتھ یکساں لمبائی کا ایک چکر ہے۔ اب ہم وضاحت کر سکتے ہیں (جہاں ہم آہنگی کا فرق ہے) اور ہم ایک تضاد میں ایک کامل ملاپ حاصل کرتے ہیں۔ ٹوٹے-برج فارمولے کا مساوات ٹوٹے-برج فارمولے کا کہنا ہے کہ گراف کے زیادہ سے زیادہ ملاپ کا سائز برابر ہوتا ہے۔ مساوی طور پر، زیادہ سے زیادہ مماثل میں بے مثال عمودی کی تعداد برابر ہوتی ہے۔ یہ فارمولا ٹوٹے کے نظریہ کی پیروی کرتا ہے، اس مشاہدے کے ساتھ جو سائز کا مماثلت رکھتا ہے اگر اور صرف اس صورت میں جب نئے عمودی حصوں کو شامل کرکے حاصل کردہ گراف، ہر ایک کے اصل عمودی حصے سے جڑا ہوا، ایک کامل مماثلت رکھتا ہے۔ چونکہ کوئی بھی سیٹ جو اجزاء سے زیادہ میں الگ ہوتا ہے اس میں تمام نئے عمودی حصے ہونے چاہئیں، (*) صرف اگر اور صرف اگر کے لیے مطمئن ہے۔ لامحدود گرافوں میں جڑے ہوئے لامحدود گرافوں کے لیے جو مقامی طور پر محدود ہیں (ہر ورٹیکس میں محدود ڈگری ہوتی ہے)، ٹوٹے کی حالت کی عمومی شکل ہوتی ہے: اس طرح کے گراف کامل مماثلت رکھتے ہیں اگر اور صرف اس صورت میں جب کوئی محدود ذیلی سیٹ نہ ہو، جس کو ہٹانے سے ذیلی سیٹ کے سائز سے بڑے محدود عجیب اجزاء پیدا ہوتے ہیں۔ یہ بھی دیکھیں کہ بپارٹائٹ میچنگ ہال کا میرج تھیوریم پیٹرسن کا تھیوریم نوٹس ریفرنس میچنگ (گراف تھیوری) تھیوریمز ان گراف تھیوری ثبوتوں پر مشتمل مضامین