Gilbert–Pollack conjecture
ریاضی میں، گلبرٹ پولاک قیاس یوکلڈین سطح میں ایک ہی نقطہ سیٹ کے لیے اسٹینر درختوں کی لمبائی اور یوکلڈین کم از کم پھیلے ہوئے درختوں کے تناسب پر ایک غیر مصدقہ قیاس ہے۔ اس کی تجویز ایڈگر گلبرٹ اور ہنری او پولاک نے 1968 میں پیش کی تھی۔ طیارہ میں پوائنٹس کے ایک سیٹ کے لیے، لائن سیگمنٹس کا سب سے چھوٹا نیٹ ورک جو پوائنٹس کو جوڑتا ہے، جس میں صرف دیئے گئے پوائنٹس اختتامی پوائنٹس کے طور پر ہوتے ہیں، سیٹ کا یوکلڈین کم از کم پھیلا ہوا درخت ہوتا ہے۔ اضافی اختتامی نکات کا استعمال کرکے ایک چھوٹا نیٹ ورک بنانا ممکن ہو سکتا ہے، جو دیئے گئے پوائنٹ سیٹ میں موجود نہیں ہے۔ ان اضافی نکات کو اسٹینر پوائنٹس کہا جاتا ہے اور ان کا استعمال کرتے ہوئے جو مختصر ترین نیٹ ورک بنایا جا سکتا ہے اسے اسٹینر کم از کم ٹری کہا جاتا ہے۔ اسٹینر تناسب تمام پوائنٹ سیٹوں پر، یوکلیڈین کم از کم پھیلے ہوئے درخت اور اسٹینر کم از کم درخت کی لمبائی کے تناسب کا بالادستی ہے۔ چونکہ سٹینر کا کم از کم درخت چھوٹا ہوتا ہے، اس لیے یہ تناسب ہمیشہ ایک سے زیادہ ہوتا ہے۔ سٹینر تناسب پر ایک نچلی باؤنڈ یونٹ سائیڈ لمبائی کے مساوی مثلث کے عمودی حصوں پر تین پوائنٹس کے ذریعے فراہم کی جاتی ہے۔ ان تین نکات کے لیے، یوکلیڈین کم از کم پھیلا ہوا درخت مثلث کے دو کناروں کا استعمال کرتا ہے، جس کی کل لمبائی دو ہے۔ اسٹینر کا کم از کم درخت تینوں نکات کو مثلث کے مرکز پر ایک اسٹینر پوائنٹ سے جوڑتا ہے، جس کی کل لمبائی کم ہوتی ہے۔ اس مثال کی وجہ سے، سٹینر کا تناسب کم از کم ہونا چاہیے۔ گلبرٹ-پولک قیاس آرائی میں کہا گیا ہے کہ یہ مثال اسٹینر تناسب کے لیے بدترین صورت حال ہے، اور یہ تناسب برابر ہے۔ یعنی، یوکلڈین سطح میں مقرر کردہ ہر محدود نقطہ کے لیے، یوکلڈین کم از کم پھیلا ہوا درخت اسٹینر کم از کم درخت کی لمبائی سے زیادہ نہیں ہو سکتا۔ یہ قیاس ڈنگ زو ڈو اور فرینک کوانگ منگ ہوانگ کے ثبوت کے لیے مشہور ہے، جو بعد میں ایک سنگین خلا ثابت ہوا۔ ڈو اور ہوانگ کے ناقص نتائج کی بنیاد پر، جے ہائیم روبنسٹائن اور جیا ایف وینگ نے یہ نتیجہ اخذ کیا کہ اسٹینر کا تناسب مستقل منحنی خطوط کے دو جہتی دائرے کے لیے بھی ہے، لیکن ڈو اور ہوانگ کے بنیادی نتائج میں فرق کی وجہ سے، روبنسٹائن اور وینگ کا نتیجہ بھی اب تک ثابت نہیں ہوا سمجھا جاتا ہے۔ حوالہ جات گراف تھیوری میں غیر حل شدہ مسائل کمپیوٹر سائنس میں غیر حل شدہ مسائل جیومیٹرک الگورتھم مشترکہ اصلاح میٹرک جیومیٹری