Frucht's theorem
फ्रुक्ट की प्रमेय बीजगणितीय ग्राफ सिद्धांत में एक प्रमेय है जिसका अनुमान 1936 में डेन्स कनिग द्वारा लगाया गया था और 1939 में रॉबर्ट फ्रुक्ट द्वारा साबित किया गया था। यह बताता है कि प्रत्येक परिमित समूह एक परिमित दिशाहीन ग्राफ की सममितियों का समूह है। अधिक दृढ़ता से, किसी भी सीमित समूह जी के लिए असीम रूप से कई गैर-समरूप सरल जुड़े हुए ग्राफ मौजूद हैं जैसे कि उनमें से प्रत्येक का स्वरूपता समूह जी के लिए समरूपता है। प्रमाण विचार प्रमाण का मुख्य विचार यह देखना है कि जी के केली ग्राफ, एक दूसरे से जी के जनरेटर को अलग करने के लिए अपने किनारों पर रंगों और अभिविन्यासों को जोड़ने के साथ, वांछित स्वरूपता समूह है। इसलिए, यदि इन किनारों में से प्रत्येक को एक उपयुक्त उपग्राफ द्वारा प्रतिस्थापित किया जाता है, जैसे कि प्रत्येक प्रतिस्थापन उपग्राफ स्वयं असममित है और दो प्रतिस्थापन समरूप हैं यदि और केवल यदि वे एक ही रंग के किनारों को प्रतिस्थापित करते हैं, तो इन प्रतिस्थापनों को निष्पादित करके बनाए गए दिशाहीन ग्राफ में भी समरूपता समूह के रूप में G होगा। ग्राफ का आकार तीन अपवादों के साथ-3,4 और 5 क्रम के चक्रीय समूहों-प्रत्येक समूह को एक ग्राफ की समरूपता के रूप में दर्शाया जा सकता है जिसके शीर्षों में केवल दो कक्षाएं होती हैं। इसलिए, ग्राफ में शीर्षों की संख्या समूह के क्रम से अधिक से अधिक दोगुनी है। अपवादों के एक बड़े समूह के साथ, अधिकांश परिमित समूहों को एक शीर्ष-सकर्मक ग्राफ की समरूपता के रूप में दर्शाया जा सकता है, जिसमें समूह के क्रम के बराबर कई शीर्ष होते हैं। ग्राफ के विशेष परिवार फ्रुक्ट के प्रमेय के मजबूत संस्करण हैं जो बताते हैं कि ग्राफ के कुछ प्रतिबंधित परिवारों में अभी भी किसी भी समरूपता समूह को प्राप्त करने के लिए पर्याप्त ग्राफ हैं। फ्रुक्ट ने साबित किया कि वास्तव में वांछित गुण के साथ कई 3-नियमित ग्राफ मौजूद हैं; उदाहरण के लिए, फ्रुक्ट ग्राफ, 12 शीर्षों और 18 किनारों के साथ एक 3-नियमित ग्राफ, में कोई गैर-तुच्छ समरूपता नहीं है, जो तुच्छ समूह के लिए इस प्रकार की प्राप्ति प्रदान करता है। गर्ट सबिदुस्सी ने दिखाया कि किसी भी समूह को सभी सकारात्मक पूर्णांक मानों के लिए (नियमित ग्राफ और के-क्रोमेटिक ग्राफ के लिए) कई अलग-अलग के-नियमित ग्राफ, के-वर्टेक्स से जुड़े ग्राफ, या के-क्रोमेटिक ग्राफ के समरूपता समूहों के रूप में महसूस किया जा सकता है। इन तथ्यों से कि प्रत्येक ग्राफ को इसके किनारों और शीर्षों के आंशिक क्रम से पुनर्निर्मित किया जा सकता है, कि प्रत्येक सीमित आंशिक क्रम बिरखॉफ के प्रतिनिधित्व प्रमेय द्वारा एक सीमित वितरण जाली के बराबर है, यह इस प्रकार है कि प्रत्येक सीमित समूह को एक वितरण जाली की समरूपता के रूप में महसूस किया जा सकता है, और जाली के ग्राफ की, एक मध्य रेखाचित्र। प्रत्येक परिमित समूह को एक प्रबल नियमित ग्राफ की सममितियों के समूह के रूप में प्राप्त करना संभव है। प्रत्येक परिमित समूह को संख्या दो को अलग करने वाले ग्राफ की समरूपता के रूप में भी महसूस किया जा सकता हैः कोई भी (अनुचित रूप से) ग्राफ को दो रंगों से रंग सकता है ताकि ग्राफ की कोई भी समरूपता रंग को संरक्षित न कर सके। हालांकि, ग्राफ के कुछ महत्वपूर्ण वर्ग सभी समूहों को उनकी समरूपता के रूप में महसूस करने में असमर्थ हैं। केमिली जॉर्डन ने पेड़ों के समरूपता समूहों को तुच्छ समूह वाले सीमित समूहों के सबसे छोटे समूह के रूप में वर्णित किया और एक दूसरे के साथ प्रत्यक्ष उत्पादों के तहत बंद किया और सममित समूहों के साथ पुष्प उत्पाद; विशेष रूप से, क्रम तीन का चक्रीय समूह एक पेड़ का समरूपता समूह नहीं है। समतलीय ग्राफ भी सभी समूहों को उनकी समरूपता के रूप में महसूस करने में सक्षम नहीं हैं; उदाहरण के लिए, केवल सीमित सरल समूह जो समतलीय ग्राफ की समरूपता हैं, वे हैं चक्रीय समूह और वैकल्पिक समूह। अधिक आम तौर पर, प्रत्येक लघु-बंद ग्राफ परिवार अपने ग्राफ की सममितियों द्वारा सभी सीमित समूहों का प्रतिनिधित्व करने में असमर्थ है। लेज़लो बाबाई, अधिक दृढ़ता से, अनुमान लगाते हैं कि प्रत्येक लघु-बंद परिवार केवल सीमित रूप से कई गैर-चक्रीय सीमित सरल समूहों का प्रतिनिधित्व कर सकता है। अनंत ग्राफ और समूहों इज़बिकी ने 1959 में इन परिणामों का विस्तार किया और दिखाया कि किसी भी सीमित समरूपता समूह को साकार करने वाले अनगिनत अनंत ग्राफ थे। अंत में, जोहान्स डी ग्रूट और सबिदुस्सी ने 1959/1960 में स्वतंत्र रूप से साबित किया कि किसी भी समूह (इस धारणा को छोड़ते हुए कि समूह सीमित है, लेकिन पसंद के स्वयंसिद्ध की धारणा के साथ) को एक अनंत ग्राफ की समरूपता के समूह के रूप में महसूस किया जा सकता है। संदर्भ स्रोत। .. .. .. .. .. जैसा कि उद्धृत किया गया है। .. .. ग्राफ सिद्धांत में बीजगणितीय ग्राफ सिद्धांत प्रमेय