Universal graph
गणित में, एक सार्वभौमिक ग्राफ एक अनंत ग्राफ है जिसमें एक प्रेरित उपग्राफ के रूप में प्रत्येक परिमित (या सबसे अधिक गणना योग्य) ग्राफ होता है। इस प्रकार का एक सार्वभौमिक ग्राफ सबसे पहले रिचर्ड राडो द्वारा बनाया गया था और अब इसे राडो ग्राफ या यादृच्छिक ग्राफ कहा जाता है। हाल के काम ने एक ग्राफ परिवार के लिए सार्वभौमिक ग्राफ पर ध्यान केंद्रित किया हैः यानी, एफ से संबंधित एक अनंत ग्राफ जिसमें सभी सीमित ग्राफ शामिल हैं। उदाहरण के लिए,-क्लिक-मुक्त ग्राफ के लिए हेंसन ग्राफ इस मायने में सार्वभौमिक हैं। ग्राफ के एक परिवार के लिए एक सार्वभौमिक ग्राफ भी सीमित ग्राफ के अनुक्रम के एक सदस्य को संदर्भित कर सकता है जिसमें सभी ग्राफ शामिल हैं; उदाहरण के लिए, प्रत्येक सीमित ट्री पर्याप्त रूप से बड़े हाइपरक्यूब ग्राफ का एक उपग्राफ है इसलिए एक हाइपरक्यूब को पेड़ों के लिए एक सार्वभौमिक ग्राफ कहा जा सकता है। हालाँकि यह इस तरह का सबसे छोटा ग्राफ नहीं हैः यह ज्ञात है कि-वर्टेक्स पेड़ों के लिए एक सार्वभौमिक ग्राफ है, जिसमें केवल शीर्ष और किनारे हैं, और यह इष्टतम है। समतलीय विभाजक प्रमेय पर आधारित एक निर्माण का उपयोग यह दिखाने के लिए किया जा सकता है कि-वर्टेक्स समतलीय ग्राफ में किनारों के साथ सार्वभौमिक ग्राफ होते हैं, और यह कि सीमित-डिग्री समतलीय ग्राफ में किनारों के साथ सार्वभौमिक ग्राफ होते हैं। समतल आलेखों के लिए सार्वभौमिक आलेखों का निर्माण करना भी संभव है जिनमें शीर्ष होते हैं। सुमनर के अनुमान में कहा गया है कि टूर्नामेंट पॉलीट्री के लिए सार्वभौमिक हैं, इस अर्थ में कि शीर्षों वाले प्रत्येक टूर्नामेंट में प्रत्येक पॉलीट्री होता है जिसमें शीर्ष एक उपग्राफ के रूप में होते हैं। ग्राफ के एक परिवार में बहुपद आकार का एक सार्वभौमिक ग्राफ होता है, जिसमें प्रत्येक-वर्टेक्स ग्राफ एक प्रेरित उपग्राफ के रूप में होता है, अगर और केवल तभी जब इसमें एक आसन्न लेबलिंग योजना हो जिसमें शीर्षों को-बिट बिटस्ट्रिंग द्वारा इस तरह से लेबल किया जा सकता है कि एक एल्गोरिथ्म यह निर्धारित कर सकता है कि क्या दो शीर्ष उनके लेबल की जांच करके आसन्न हैं। क्योंकि, यदि इस प्रकार का एक सार्वभौमिक ग्राफ मौजूद है, तो किसी भी ग्राफ के शीर्षों को सार्वभौमिक ग्राफ में संबंधित शीर्षों की पहचान द्वारा लेबल किया जा सकता है, और इसके विपरीत यदि एक लेबलिंग योजना मौजूद है तो प्रत्येक संभावित लेबल के लिए एक शीर्ष के साथ एक सार्वभौमिक ग्राफ का निर्माण किया जा सकता है। पुरानी गणितीय शब्दावली में, वाक्यांश "सार्वभौमिक ग्राफ" का उपयोग कभी-कभी एक पूर्ण ग्राफ को दर्शाने के लिए किया जाता था। सार्वभौमिक ग्राफ की धारणा को अनुकूलित किया गया है और इसका उपयोग औसत भुगतान खेलों को हल करने के लिए किया गया है। संदर्भ बाहरी लिंक वृक्षों के लिए सार्वभौमिक ग्राफ से संबंधित पैनार्बोरियल सूत्र, "दिन का प्रमेय" ग्राफ परिवार अनंत ग्राफ