Erdős–Gallai theorem
ایرڈس گلائی تھیوریم گراف تھیوری کا نتیجہ ہے، جو مشترکہ ریاضی کی ایک شاخ ہے۔ یہ گراف کے احساس کے مسئلے کو حل کرنے کے لیے دو معروف طریقوں میں سے ایک فراہم کرتا ہے، یعنی۔ یہ قدرتی اعداد کی ایک محدود ترتیب کے لیے ایک سادہ گراف کی ڈگری ترتیب ہونے کے لیے ایک ضروری اور کافی شرط دیتا ہے۔ ان شرائط کی پابندی کرنے والی ترتیب کو "گرافک" کہا جاتا ہے۔ یہ نظریہ 1960 میں پال ایرڈس اور تبور گیلائی نے شائع کیا تھا، جن کے نام پر اس کا نام رکھا گیا ہے۔ غیر منفی انٹیجرز کی ایک ترتیب کو n عمودی پر ایک محدود سادہ گراف کی ڈگری ترتیب کے طور پر پیش کیا جا سکتا ہے اگر اور صرف اس صورت میں جب ہر ایک کے لیے یکساں اور برقرار ہو۔ ثبوت یہ دکھانا مشکل نہیں ہے کہ اعداد کی ترتیب کے گرافک ہونے کے لیے ایرڈس گلائی تھیوریم کے شرائط ضروری ہیں۔ ڈگریوں کا مجموعہ یکساں ہونے کی ضرورت ہاتھ ملانے والا لیما ہے، جو پہلے ہی اویلر نے کونگسبرگ کے پلوں پر اپنے 1736 کے مقالے میں استعمال کیا تھا۔ سب سے بڑی ڈگریوں کے مجموعے اور باقی ڈگریوں کے مجموعے کے درمیان عدم مساوات کو دوہری گنتی سے قائم کیا جا سکتا ہے: بائیں طرف سب سے زیادہ ڈگری والے عمودی حصوں کے درمیان ایج-ورٹیکس ملحقہ علاقوں کی تعداد دیتا ہے، اس طرح کی ہر ملحقہ جگہ یا تو ایک یا دو ہائی ڈگری والے اختتامی نکات کے ساتھ کنارے پر ہونی چاہیے، دائیں طرف کی اصطلاح ایج-ورٹیکس ملحقہ علاقوں کی زیادہ سے زیادہ ممکنہ تعداد دیتی ہے جس میں دونوں اختتامی نکات ہائی ڈگری کے ہوتے ہیں، اور دائیں اوپری حدود پر بقیہ اصطلاح ان کناروں کی تعداد کو ظاہر کرتی ہے جن میں بالکل ایک ہائی ڈگری اینڈ پوائنٹ ہوتا ہے۔ اس طرح، ثبوت کا زیادہ مشکل حصہ یہ ظاہر کرنا ہے کہ، ان شرائط کی پابندی کرنے والے اعداد کے کسی بھی سلسلے کے لیے، ایک گراف موجود ہے جس کے لیے یہ ڈگری ترتیب ہے۔ کا اصل ثبوت لمبا اور ملوث تھا۔ نیٹ ورک کے بہاؤ کے خیالات پر مبنی کلاڈ برج کے ایک مختصر ثبوت کا حوالہ دیتے ہیں۔ چودم اس کے بجائے ڈگریوں کے مجموعے پر ریاضیاتی انڈکشن کے ذریعے ایک ثبوت فراہم کرتا ہے: وہ اس ترتیب میں کسی نمبر کا پہلا انڈیکس ہونے دیتا ہے جس کے لیے (یا اگر سب برابر ہیں تو آخری نمبر)، کیس تجزیہ کا استعمال کرتا ہے تاکہ یہ ظاہر کیا جا سکے کہ ترتیب میں آخری نمبر سے ایک کو گھٹا کر تشکیل دی گئی ترتیب (اور آخری نمبر کو ہٹا کر اگر یہ گھٹاؤ اسے صفر بنا دیتا ہے) دوبارہ گرافک ہے، اور ایک گراف بناتا ہے جو اصل ترتیب کی نمائندگی کرتا ہے جس میں ان دو پوزیشنوں کے درمیان ایک کنارے کا اضافہ کیا جاتا ہے جہاں سے ایک کو گھٹا دیا گیا تھا۔ "سب ریالائزیشنز" کی ایک ترتیب پر غور کریں، گراف جن کی ڈگریاں دی گئی ڈگری کی ترتیب سے بالائی حد میں ہوتی ہیں۔ وہ ظاہر کرتے ہیں کہ، اگر G ایک سب ریالائزیشن ہے، اور i G میں کسی ورٹیکس کا سب سے چھوٹا انڈیکس ہے جس کی ڈگری ڈائی کے برابر نہیں ہے، تو G کو اس طرح سے تبدیل کیا جا سکتا ہے جس سے ایک اور سب ریالائزیشن پیدا ہو، جس سے ورٹیکس i کی ڈگری میں اضافہ ہوتا ہے بغیر ترتیب میں پہلے والے ورٹیکس کی ڈگریوں کو تبدیل کیے۔ اس قسم کے بار بار کیے جانے والے اقدامات کو بالآخر نظریہ کو ثابت کرتے ہوئے دی گئی ترتیب کے احساس تک پہنچنا چاہیے۔ انٹیجر پارٹیشنز سے تعلق ایرڈس گلائی تھیوریم اور انٹیجر پارٹیشنز کے نظریہ کے درمیان قریبی روابط کو بیان کرتا ہے۔ چلو ؛ پھر ترتیب شدہ انٹیجر سیکوینس کا خلاصہ پارٹیشن کے طور پر کیا جا سکتا ہے۔ ان کے سابقہ جملوں کی بڑی تعداد کے تحت، پارٹیشنز ایک جالی بناتی ہیں، جس میں انفرادی پارٹیشن اور پارٹیشن کے ترتیب میں نیچے والے دوسرے پارٹیشن کے درمیان کم سے کم تبدیلی یہ ہے کہ ایک نمبر سے ایک کو گھٹا کر اسے ایک ایسے نمبر میں شامل کیا جائے جو کم از کم دو سے چھوٹا ہو (صفر ہو سکتا ہے)۔ جیسا کہ ایگنر اور ٹرائش دکھاتے ہیں، یہ عمل گرافک ہونے کی خاصیت کو محفوظ رکھتا ہے، لہذا ایرڈس-گلائی تھیوریم کو ثابت کرنے کے لیے یہ گرافک ترتیبات کی خصوصیت کے لیے کافی ہے جو اس بڑی ترتیب میں زیادہ سے زیادہ ہیں۔ وہ متعلقہ پارٹیشنوں کے فیررس خاکے کے لحاظ سے اس طرح کی خصوصیت فراہم کرتے ہیں، اور یہ ظاہر کرتے ہیں کہ یہ ایرڈس-گلائی تھیوریم کے مساوی ہے۔ دیگر اقسام کے گرافوں کے لیے گرافک ترتیبات اسی طرح کے نظریات سادہ ہدایت شدہ گرافوں کے ڈگری ترتیبات، لوپس کے ساتھ سادہ ہدایت شدہ گراف، اور سادہ دو طرفہ گراف کی وضاحت کرتے ہیں۔ پہلا مسئلہ فلکرسن-چین-اینسٹی تھیوریم کی طرف سے نمایاں ہے۔ مؤخر الذکر دو معاملات، جو مساوی ہیں، گیل-رائسر تھیوریم کی طرف سے نمایاں ہیں۔ مضبوط تر ورژن نے ثابت کیا کہ اس عدم مساوات پر غور کرنا کافی ہے جیسے کہ ساتھ اور اس کے لیے۔ مخالف زور میں گراف کے لیے عدم مساوات کے سیٹ کو محدود کریں۔ اگر ایک یکساں خلاصہ مثبت ترتیب d میں زیادہ سے زیادہ اور کم سے کم (اور لمبائی سب سے بڑی اندراج سے زیادہ ہے) کے علاوہ کوئی بار بار اندراج نہیں ہے، تو یہ صرف ویں عدم مساوات کی جانچ کرنے کے لیے کافی ہے، جہاں۔ عمومی کاری غیر منفی انٹیجرز کی ایک محدود ترتیب گرافک ہے اگر یکساں ہے اور ایک ایسی ترتیب موجود ہے جو گرافک ہے اور بڑی ہوتی ہے۔ اس کا نتیجہ دیا گیا۔ اسے دوبارہ ایجاد کیا اور مزید براہ راست ثبوت دیا۔ حویل-ہکیمی الگورتھم حوالہ جات بھی دیکھیں۔ ۔ گراف تھیوری میں گیلائی تھیوریم تھیوریمز