1960 کی دہائی کی گراف پہیلی آخرکار حل

کچھ نقطے لیں اور ان کے کچھ جوڑوں کو لکیروں سے ملا دیں: ریاضی دان اسے گراف کہتے ہیں، نقطوں کو اس کے راس (vertices) اور لکیروں کو اس کے کنارے (edges)۔ ایک سائیکل ایسا بند حلقہ ہے جو مختلف راسوں سے گزر کر اپنے نقطۂ آغاز پر لوٹ آتا ہے۔ ایک فطری سوال یہ ہے کہ کیا کسی گراف کے کناروں کو — ہر کنارہ ٹھیک ایک بار استعمال کرتے ہوئے — سائیکلوں میں بانٹا جا سکتا ہے۔

جیسا کہ مقالہ یاد دلاتا ہے، اس کا جواب بہت پہلے سے معلوم ہے: یہ عین اسی وقت ممکن ہے جب ہر راس جفت تعداد میں کناروں کو چھوتا ہو۔ ایسے گرافوں کو اویلری (Eulerian) کہا جاتا ہے۔ اگلا سوال یہ ہے کہ کتنے سائیکل درکار ہیں۔ اور جن گرافوں میں صرف سائیکلوں سے کام نہیں چلتا، ان میں اکیلے کناروں کو بھی ٹکڑوں کے طور پر اجازت دی جاتی ہے۔

قیاس

1960 کی دہائی میں ایردوش اور گالائی نے قیاس کیا کہ n راسوں والے ہر گراف کے کناروں کو ایسے سائیکلوں اور اکیلے کناروں میں بانٹا جا سکتا ہے جن کی تعداد زیادہ سے زیادہ n کے متناسب ہو — جسے O(n) لکھا جاتا ہے۔ ایردوش نے اسے حل طلب مسائل کے اپنے کئی مجموعوں میں شامل کیا۔ ہایوش کا ایک متعلقہ قیاس ہر اویلری گراف میں زیادہ سے زیادہ (n − 1)/2 سائیکلوں کا تقاضا کرتا ہے۔

خطی (linear) ہی وہ بہترین نتیجہ ہے جس کی امید کی جا سکتی ہے: ایردوش نے دکھایا کہ کچھ گرافوں کو تقریباً 1.5 n ٹکڑوں کی ضرورت ہوتی ہے۔ سوال یہ تھا کہ کیا کوئی مستقل عدد ضرب n ہمیشہ کافی ہوتا ہے۔

پچاس سال تک رینگتی ہوئی حدیں

خود ایردوش اور گالائی نے ایک سادہ طریقہ دیکھا: بار بار سب سے لمبا سائیکل نکال دیں۔ اس سے تقریباً n log n ٹکڑے بنتے ہیں — اور مقالے کے مطابق تقریباً پچاس سال تک یہی سب سے بہتر عمومی حد رہی۔ حال ہی میں کونلن، فاکس اور سوداکوف نے اسے n log log n تک کم کیا، پھر بوچچ اور مونٹگمری نے n log* n تک، جہاں log* n — یعنی یہ کہ ایک سے نیچے آنے کے لیے کتنی بار لوگارتھم لینا پڑتا ہے — ناقابلِ تصور حد تک آہستہ بڑھتا ہے۔ یہ طریقے مرحلوں میں کام کرتے تھے، اور ہر مرحلے کی قیمت تقریباً n سائیکل تھی، اس لیے مرحلوں کی تعداد ہمیشہ آخری گنتی میں شامل ہو جاتی تھی۔ یہ قیاس خاص خاندانوں، جیسے بے ترتیب گرافوں، کے لیے بھی ثابت ہو چکا تھا۔

وزن جو حلقوں کی قیمت ادا کرتے ہیں

جنوبی کوریا کے KAIST کے جے ہون کم اب اس قیاس کو ثابت کرتے ہیں: ایک ایسا مقررہ مستقل عدد C موجود ہے کہ n راسوں والا ہر گراف زیادہ سے زیادہ Cn سائیکلوں اور کناروں میں بٹ جاتا ہے۔ اس کے نتیجے کے طور پر ہایوش کا قیاس ایک مستقل ضربی عامل تک درست ثابت ہوتا ہے۔

یہ ثبوت مرحلوں کو ترک کر دیتا ہے۔ ایک واحد طریقۂ کار سائیکلوں اور کناروں کو ایک ایک کر کے نکالتا ہے، اور کل تعداد کو دو مقداریں قابو میں رکھتی ہیں جن میں سے ہر ایک مستقل عدد ضرب n سے نیچے رہتی ہے۔

• درجوں پر مبنی ایک پوٹینشل۔ ہر راس کو ایک وزن ملتا ہے جو اس کے کناروں کی تعداد کے ساتھ گھٹتا ہے، تقریباً 1 / (درجہ × log² درجہ)۔ کوئی سائیکل بھاری ہے اگر اس کے راسوں کے وزن کا مجموعہ کم از کم 1 ہو۔ بھاری سائیکل نکالنے سے ایک مجموعی “پوٹینشل” کم از کم 1 کم ہوتا ہے، اور یہ پوٹینشل شروع میں ایک مستقل عدد ضرب n سے زیادہ نہیں ہوتا۔ اس لیے بھاری سائیکل صرف O(n) بار نکالے جا سکتے ہیں۔
• راسوں کی تعداد۔ جب کوئی بھاری سائیکل باقی نہیں رہتا تو گراف “ہلکا” ہوتا ہے — اور مرکزی نیا مسئلہ (theorem) دکھاتا ہے کہ بڑے درجوں والے ہلکے گراف میں ایک گھنا، تقریباً بند علاقہ ضرور ہوتا ہے۔ اس علاقے کو اس کے سائز کے متناسب تعداد میں سائیکلوں اور کناروں میں بانٹا جاتا ہے، جس کے بعد اس کے کم از کم پچاسویں حصے کے راسوں کے پاس زیادہ سے زیادہ دو کنارے رہ جاتے ہیں اور وہ ہمیشہ کے لیے باہر ہو جاتے ہیں۔ چونکہ ہر راس صرف ایک بار باہر ہو سکتا ہے، اس لیے اس حصے کی قیمت بھی O(n) ہے۔

گراف کے گھنے حصوں کے اندر راستوں کے ٹکڑوں کو “ایکسپینڈرز” سے گزرنے والے جوڑنے والے راستوں کے ذریعے ایک واحد سائیکل میں بند کیا جاتا ہے؛ ایک بے ترتیب رنگ بندی ایک ہی سائیکل کے جوڑنے والے راستوں کو الگ رکھتی ہے۔ — شکل 3، Kim (2026)، arXiv:2610.07840۔

ان گھنے علاقوں کو بانٹنے کے لیے ثبوت بوچچ اور مونٹگمری کے مضبوط “ایکسپینڈرز” (expanders) کے اوزاروں کو وسعت دیتا ہے — یعنی ایسے گراف جن میں راسوں کے ہر مجموعے کے بہت سے پڑوسی ہوں — اور راسوں کو بے ترتیب طور پر رنگتا ہے تاکہ ایک ہی سائیکل کے جوڑنے والے راستے کبھی آپس میں نہ ٹکرائیں۔

کیا ابھی تک کھلا ہے

مستقل عدد C بہت بڑا ہے، اور مصنف نے اسے بہتر بنانے کی کوشش نہیں کی۔ بہترین مستقل عدد — جو کم از کم 1.5 ہے — تلاش کرنا ابھی باقی ہے، اسی طرح ہایوش کا عین قیاس اور گرافوں کو راستوں میں بانٹنے کے بارے میں گالائی کا ایک متعلقہ قیاس بھی۔ وزن کی ترکیب کو صرف ایسے وزنوں کی ضرورت ہے جن کا مجموعہ متقارب (convergent) ہو، اور مصنف تجویز کرتے ہیں کہ یہ تقسیم کے دوسرے مسائل میں بھی کام آ سکتی ہے۔

یہ ایک واحد مصنف کا پری پرنٹ ہے، جس کی ابھی ہم مرتبہ جائزے سے جانچ نہیں ہوئی۔

مفادات کا ٹکراؤ۔ مصنف بیان کرتے ہیں کہ انہوں نے دلائل تیار کرنے اور متن اور اشکال بنانے میں ChatGPT (OpenAI) اور Claude (Anthropic) کا وسیع استعمال کیا، اور یہ کہ انہوں نے تمام نتائج کی تصدیق کی ہے اور مقالے کی پوری ذمہ داری قبول کرتے ہیں۔ جو متن آپ پڑھ رہے ہیں وہ بھی Claude ہی نے لکھا ہے۔