Gilbert–Pollack conjecture
गणित में, गिल्बर्ट-पोलक अनुमान यूक्लिडियन तल में एक ही बिंदु सेट के लिए स्टेनर पेड़ों की लंबाई और यूक्लिडियन न्यूनतम फैले हुए पेड़ों के अनुपात पर एक अप्रमाणित अनुमान है। यह 1968 में एडगर गिल्बर्ट और हेनरी ओ. पोलक द्वारा प्रस्तावित किया गया था। कथन समतल में बिंदुओं के एक समूह के लिए, रेखा खंडों का सबसे छोटा नेटवर्क जो बिंदुओं को जोड़ता है, जिसमें केवल दिए गए बिंदु अंतिम बिंदु के रूप में होते हैं, सेट का यूक्लिडियन न्यूनतम फैलाव वृक्ष होता है। अतिरिक्त अंतिम बिंदुओं का उपयोग करके एक छोटे नेटवर्क का निर्माण करना संभव हो सकता है, जो दिए गए बिंदु सेट में मौजूद नहीं हैं। इन अतिरिक्त बिंदुओं को स्टेनर पॉइंट कहा जाता है और उनका उपयोग करके बनाए जा सकने वाले सबसे छोटे नेटवर्क को स्टेनर मिनिमम ट्री कहा जाता है। स्टेनर अनुपात यूक्लिडियन न्यूनतम फैले हुए पेड़ और स्टेनर न्यूनतम पेड़ की लंबाई के अनुपात का सर्वोच्च, सभी बिंदु सेटों पर है। चूँकि स्टेनर न्यूनतम वृक्ष छोटा होता है, इसलिए यह अनुपात हमेशा एक से अधिक होता है। स्टेनर अनुपात पर एक निचली सीमा इकाई पक्ष की लंबाई के एक समबाहु त्रिभुज के शीर्षों पर तीन बिंदुओं द्वारा प्रदान की जाती है। इन तीन बिंदुओं के लिए, यूक्लिडियन न्यूनतम फैलाव वृक्ष त्रिभुज के दो किनारों का उपयोग करता है, जिनकी कुल लंबाई दो है। स्टेनर न्यूनतम वृक्ष तीनों बिंदुओं को त्रिभुज के केंद्रक पर एक स्टेनर बिंदु से जोड़ता है, जिसकी कुल लंबाई कम होती है। इस उदाहरण के कारण, स्टेनर अनुपात कम से कम होना चाहिए। गिल्बर्ट-पोलक अनुमान में कहा गया है कि यह उदाहरण स्टेनर अनुपात के लिए सबसे खराब स्थिति है, और यह अनुपात बराबर है। अर्थात्, यूक्लिडियन तल में निर्धारित प्रत्येक परिमित बिंदु के लिए, यूक्लिडियन न्यूनतम फैलाव वृक्ष स्टेनर न्यूनतम वृक्ष की लंबाई से अधिक नहीं हो सकता है। यह अनुमान डिंग-झु डू और फ्रैंक क्वांग-मिंग ह्वांग द्वारा अपने प्रमाण के लिए प्रसिद्ध है, जो बाद में एक गंभीर अंतर साबित हुआ। त्रुटिपूर्ण डू और ह्वांग परिणाम के आधार पर, जे. हायम रुबिनस्टीन और जिया एफ. वेंग ने निष्कर्ष निकाला कि स्टेनर अनुपात भी स्थिर वक्रता के द्वि-आयामी क्षेत्र के लिए है, लेकिन डू और ह्वांग के आधार परिणाम में अंतर के कारण, रुबिनस्टीन और वेंग का परिणाम भी अब तक साबित नहीं हुआ है। संदर्भ ग्राफ सिद्धांत में अनसुलझी समस्याओं का अनुमान कंप्यूटर विज्ञान में अनसुलझी समस्याएं ज्यामितीय एल्गोरिदम संयोजन अनुकूलन मीट्रिक ज्यामिति