Gilbert–Pollack conjecture
গণিতে, গিলবার্ট-পোলাক অনুমান হল ইউক্লিডীয় সমতলে একই বিন্দু সেটের জন্য স্টেইনার গাছের দৈর্ঘ্য এবং ইউক্লিডীয় ন্যূনতম বিস্তৃত গাছের অনুপাতের উপর একটি অপ্রমাণিত অনুমান। 1968 সালে এডগার গিলবার্ট এবং হেনরি ও. পোলাক এটি প্রস্তাব করেছিলেন। বিবৃতি সমতলে পয়েন্টগুলির একটি সেটের জন্য, লাইন সেগমেন্টগুলির সংক্ষিপ্ততম নেটওয়ার্ক যা পয়েন্টগুলিকে সংযুক্ত করে, শেষ পয়েন্ট হিসাবে কেবল প্রদত্ত পয়েন্টগুলি থাকে, সেটটির ইউক্লিডীয় ন্যূনতম স্প্যানিং ট্রি। প্রদত্ত পয়েন্ট সেটে উপস্থিত না থাকা অতিরিক্ত এন্ডপয়েন্ট ব্যবহার করে একটি ছোট নেটওয়ার্ক তৈরি করা সম্ভব হতে পারে। এই অতিরিক্ত পয়েন্টগুলিকে স্টেইনার পয়েন্ট বলা হয় এবং এগুলি ব্যবহার করে তৈরি করা যেতে পারে এমন সংক্ষিপ্ততম নেটওয়ার্ককে স্টেইনার মিনিমাম ট্রি বলা হয়। স্টেইনার অনুপাত হল সর্বোচ্চ, সমস্ত বিন্দু সেটের উপর, ইউক্লিডীয় ন্যূনতম বিস্তৃত গাছের দৈর্ঘ্যের অনুপাত এবং স্টেইনার ন্যূনতম গাছ। যেহেতু স্টেইনার ন্যূনতম গাছটি ছোট, তাই এই অনুপাতটি সর্বদা একের চেয়ে বেশি হয়। একক পার্শ্ব দৈর্ঘ্যের একটি সমবাহু ত্রিভুজের শীর্ষে তিনটি বিন্দু দ্বারা স্টেইনার অনুপাতের একটি নিম্ন সীমা প্রদান করা হয়। এই তিনটি বিন্দুর জন্য, ইউক্লিডীয় ন্যূনতম বিস্তৃত গাছটি ত্রিভুজের দুটি প্রান্ত ব্যবহার করে, যার মোট দৈর্ঘ্য দুই। স্টেইনার ন্যূনতম গাছ তিনটি বিন্দুকে ত্রিভুজের কেন্দ্রস্থলে একটি স্টেইনার বিন্দুর সাথে সংযুক্ত করে, যার মোট দৈর্ঘ্য কম। এই উদাহরণের কারণে, স্টেইনারের অনুপাত অবশ্যই কমপক্ষে হতে হবে। গিলবার্ট-পোলাক অনুমান বলে যে এই উদাহরণটি স্টেইনার অনুপাতের জন্য সবচেয়ে খারাপ পরিস্থিতি এবং এই অনুপাত সমান। অর্থাৎ, ইউক্লিডীয় সমতলে নির্ধারিত প্রতিটি সসীম বিন্দুর জন্য, ইউক্লিডীয় ন্যূনতম বিস্তৃত গাছটি স্টেইনার ন্যূনতম গাছের দৈর্ঘ্যের চেয়ে বেশি হতে পারে না। চেষ্টা করা প্রমাণ অনুমানটি ডিং-ঝু ডু এবং ফ্রাঙ্ক কোয়াং-মিং হোয়াং দ্বারা তার প্রমাণের জন্য বিখ্যাত, যা পরে একটি গুরুতর ফাঁক হিসাবে প্রমাণিত হয়েছিল। ত্রুটিপূর্ণ ডু এবং হোয়াং ফলাফলের উপর ভিত্তি করে, জে. হায়াম রুবিনস্টাইন এবং জিয়া এফ. ওয়েং এই সিদ্ধান্তে উপনীত হন যে স্টেইনার অনুপাত ধ্রুবক বক্রতার একটি দ্বিমাত্রিক গোলকের জন্যও, কিন্তু ডু এবং হোয়াং-এর মূল ফলাফলের ব্যবধানের কারণে, রুবিনস্টাইন এবং ওয়েং-এর ফলাফলও এখন এখনও প্রমাণিত হয়নি বলে মনে করা হয়। তথ্যসূত্র অনুমান গ্রাফ তত্ত্বে অমীমাংসিত সমস্যা কম্পিউটার বিজ্ঞানে অমীমাংসিত সমস্যা জ্যামিতিক অ্যালগরিদম সমন্বিত অনুকূলকরণ মেট্রিক জ্যামিতি