Ore's theorem
اوری کا نظریہ گراف تھیوری کا نتیجہ ہے جو 1960 میں ناروے کے ریاضی دان اوسٹین اوری نے ثابت کیا تھا۔ یہ گراف کے ہیملٹنین ہونے کے لیے کافی شرط دیتا ہے، بنیادی طور پر یہ کہتے ہوئے کہ کافی حد تک کناروں والے گراف میں ہیملٹن سائیکل ہونا ضروری ہے۔ خاص طور پر، نظریہ غیر ملحقہ عمودی کے جوڑوں کی ڈگریوں کے مجموعے پر غور کرتا ہے: اگر اس طرح کے ہر جوڑے کا مجموعہ کم از کم گراف میں عمودی کی کل تعداد کے برابر ہے، تو گراف ہیملٹنین ہے۔ رسمی بیان چلو عمودی کے ساتھ ایک (محدود اور سادہ) گراف ہو. ہم ایک سرے کی ڈگری سے ظاہر کرتے ہیں، یعنی۔ واقعے کے کناروں کی تعداد۔ پھر، اوری کا نظریہ بیان کرتا ہے کہ اگر تب ہیملٹنین ہے۔ ثبوت یہ ظاہر کرنے کے مساوی ہے کہ ہر غیر ہیملٹنین گراف شرط (ऱ्ऱं) کی پابندی نہیں کرتا ہے۔ اس کے مطابق، ایسے عمودی حصوں پر ایک گراف ہونے دیں جو ہیملٹنین نہیں ہیں، اور ایک وقت میں ایک ایسے کنارے کو شامل کرکے تشکیل دیا جائے جو ہیملٹنین سائیکل نہیں بناتے ہیں، جب تک کہ مزید کناروں کو شامل نہیں کیا جا سکے۔ کسی بھی دو غیر ملحقہ چوٹیوں کو اندر آنے دیں۔ پھر کنارے کو شامل کرنے سے کم از کم ایک نیا ہیملٹنین سائیکل پیدا ہوگا، اور اس طرح کے سائیکل کے علاوہ دیگر کناروں کو اور کے ساتھ ہیملٹنین راستہ بنانا ہوگا۔ رینج میں ہر انڈیکس کے لیے، دو ممکنہ کناروں پر غور کریں۔ ان دو کناروں میں سے زیادہ سے زیادہ ایک کنارے میں موجود ہو سکتا ہے، بصورت دیگر سائیکل ہیملٹنین سائیکل ہوگا۔ اس طرح، کناروں کی کل تعداد یا تو ہوتی ہے یا زیادہ سے زیادہ انتخاب کی تعداد کے برابر ہوتی ہے، جو ہے۔ لہذا، خاصیت کی اطاعت نہیں کرتا ہے، جس کے لیے ضروری ہے کہ کناروں کی یہ کل تعداد () سے زیادہ یا اس کے برابر ہو۔ چونکہ ورٹیکس ڈگریاں زیادہ سے زیادہ ڈگریوں کے برابر ہوتی ہیں، اس کے بعد یہ بھی پراپرٹی کی اطاعت نہیں کرتا ہے۔ الگورتھم اوری کی حالت سے ملنے والے گراف میں ہیملٹنین سائیکل کی تعمیر کے لیے درج ذیل آسان الگورتھم کی وضاحت کرتا ہے۔ گراف میں ملحقہ علاقوں کو نظر انداز کرتے ہوئے عمودی حصوں کو من مانی طور پر ایک چکر میں ترتیب دیں۔ جب کہ سائیکل میں دو مسلسل عمودی سرے vi اور vi + 1 ہوتے ہیں جو گراف میں ملحقہ نہیں ہوتے ہیں، مندرجہ ذیل دو مراحل انجام دیں: ایک انڈیکس j کو اس طرح تلاش کریں کہ چار عمودی سرے vi، vi + 1، vj، اور vj + 1 سبھی الگ الگ ہوں اور اس طرح کہ گراف میں vi سے vj اور vj + 1 سے vi + 1 تک کے کنارے ہوں۔ ہر قدم سائیکل میں مسلسل جوڑوں کی تعداد میں اضافہ کرتا ہے جو گراف میں ملحقہ ہیں، ایک یا دو جوڑوں سے (اس بات پر منحصر ہے کہ آیا vj اور vj + 1 پہلے ہی ملحقہ ہیں)، لہذا بیرونی لوپ الگورتھم کے ختم ہونے سے پہلے زیادہ سے زیادہ n اوقات میں ہی ہو سکتا ہے، جہاں n دیئے گئے گراف میں عمودی جوڑوں کی تعداد ہے۔ نظریہ کے ثبوت سے ملتی جلتی دلیل کے مطابق، مطلوبہ اشاریہ جے موجود ہونا چاہیے، ورنہ غیر ملحقہ عمودی vi اور vi + 1 کی کل ڈگری بہت کم ہوگی۔ آئی اور جے کو تلاش کرنا، اور سائیکل کے حصے کو الٹنا، یہ سب وقت او (این) میں مکمل کیا جا سکتا ہے۔ لہذا، الگورتھم کا کل وقت O (n2) ہے، جو ان پٹ گراف میں کناروں کی تعداد سے ملتا جلتا ہے۔ متعلقہ نتائج اوری تھیوریم ڈیراک کے تھیوریم کی عمومی شکل ہے کہ، جب ہر ورٹیکس میں کم از کم ڈگری ہوتی ہے، تو گراف ہیملٹنین ہوتا ہے۔ کیونکہ، اگر کوئی گراف ڈیراک کی شرط پر پورا اترتا ہے، تو واضح طور پر ہر جوڑی کے عمودی حصوں میں کم از کم ڈگری کا اضافہ ہوتا ہے۔ بدلے میں اوری کے تھیوریم کو بونڈی-چوتال تھیوریم کے ذریعے عام کیا جاتا ہے۔ ایک گراف پر کلوزر آپریشن کی وضاحت کی جا سکتی ہے جس میں، جب بھی دو غیر ملحقہ عمودی حصوں میں کم از کم ڈگری کا اضافہ ہوتا ہے، تو ایک ان کو جوڑنے والے کنارے کا اضافہ کرتا ہے۔ اگر کوئی گراف اوری کے نظریہ کی شرائط پر پورا اترتا ہے، تو اس کی بندش ایک مکمل گراف ہے۔ بونڈی-چوتال تھیوریم بیان کرتا ہے کہ گراف ہیملٹنین ہے اگر اور صرف اس صورت میں جب اس کی بندش ہیملٹنین ہو۔ چونکہ مکمل گراف ہیملٹنین ہے، اوری کا تھیوریم ایک فوری نتیجہ ہے۔ اوری کے نظریہ کا ایک ورژن ملا جو ہدایت شدہ گرافوں پر لاگو ہوتا ہے۔ فرض کریں کہ ڈیگراف G میں یہ خاصیت ہے کہ، ہر دو عمودی حصوں u اور v کے لیے، یا تو u سے v تک ایک کنارہ ہے یا u کی آؤٹ ڈگری کے علاوہ v کی انڈیگری G میں عمودی حصوں کی تعداد کے برابر یا اس سے زیادہ ہے۔ پھر، ووڈال کے نظریہ کے مطابق، G ایک ہدایت شدہ ہیملٹنین سائیکل پر مشتمل ہے۔ اوری کا نظریہ ووڈال سے کسی دیئے گئے غیر ہدایت شدہ گراف میں ہر کنارے کو ہدایت شدہ کناروں کے جوڑے سے تبدیل کرکے حاصل کیا جاسکتا ہے۔ ایک قریب سے متعلق تھیوریم میں کہا گیا ہے کہ ایک n-ورٹیکس اس پراپرٹی کے ساتھ مضبوطی سے جڑا ہوا ڈیگراف ہے کہ، ہر دو غیر ملحقہ چوٹیوں u اور v کے لیے، u یا v سے منسلک کناروں کی کل تعداد کم از کم 2n−1 ہونی چاہیے۔ تھیوریم میں ڈگری کی حالت کے نتیجے میں ہیملٹنسیٹی سے زیادہ مضبوط نتیجہ دینے کے لیے اوری کے تھیوریم کو بھی مضبوط کیا جا سکتا ہے۔ خاص طور پر، اوری کے نظریہ کی شرائط کو پورا کرنے والا ہر گراف یا تو باقاعدہ مکمل دو طرفہ گراف ہوتا ہے یا پینسیکلک ہوتا ہے۔ حوالہ جات۔ ۔ ۔ ۔ ۔ ماورائے گراف تھیوری گراف تھیوری میں نظریات ثبوتوں پر مشتمل مضامین ہیملٹنین راستوں اور چکروں