Symmetric graph
ग्राफ सिद्धांत के गणितीय क्षेत्र में, एक ग्राफ सममित (या चाप-सकर्मक) होता है यदि, आसन्न शीर्षों के किसी भी दो जोड़े को दिए जाने पर, एक स्वरूपता ऐसी होती है और दूसरे शब्दों में, एक ग्राफ सममित होता है यदि इसका स्वरूपता समूह आसन्न शीर्षों के क्रमबद्ध जोड़े पर पारगमन रूप से कार्य करता है (यानी, किनारों पर जिसे एक दिशा माना जाता है)। इस तरह के ग्राफ को कभी-कभी-ट्रांजिटिव या फ्लैग-ट्रांजिटिव भी कहा जाता है। परिभाषा के अनुसार (अनदेखा और), अलग-अलग शीर्षों के बिना एक सममित ग्राफ भी शीर्ष-सकर्मक होना चाहिए। चूँकि उपरोक्त परिभाषा एक किनारे से दूसरे किनारे का मानचित्रण करती है, एक सममित ग्राफ भी किनारे-संक्रमणशील होना चाहिए। हालांकि, एक एज-ट्रांजिटिव ग्राफ को सममित होने की आवश्यकता नहीं है, क्योंकि यह मानचित्रित हो सकता है, लेकिन नहीं। स्टार ग्राफ शीर्ष-सकर्मक या सममित हुए बिना धार-सकर्मक होने का एक सरल उदाहरण है। एक और उदाहरण के रूप में, अर्ध-सममित ग्राफ धार-संक्रमणशील और नियमित होते हैं, लेकिन शीर्ष-संक्रमणशील नहीं होते हैं। इस प्रकार प्रत्येक जुड़ा हुआ सममित ग्राफ शीर्ष-सकर्मक और किनारा-सकर्मक दोनों होना चाहिए, और विषम डिग्री के ग्राफ के लिए विपरीत सही है। हालांकि, सम डिग्री के लिए, जुड़े हुए ग्राफ मौजूद हैं जो शीर्ष-संक्रमणशील और किनारे-संक्रमणशील हैं, लेकिन सममित नहीं हैं। इस तरह के आलेखों को अर्ध-संक्रमणशील कहा जाता है। सबसे छोटा जुड़ा हुआ अर्ध-संक्रमणीय ग्राफ होल्ट का ग्राफ है, जिसमें डिग्री 4 और 27 शीर्ष हैं। भ्रमित करने वाली बात यह है कि कुछ लेखक "सममित ग्राफ" शब्द का उपयोग एक ऐसे ग्राफ के लिए करते हैं जो एक चाप-सकर्मक ग्राफ के बजाय शीर्ष-सकर्मक और किनारे-सकर्मक है। इस तरह की परिभाषा में अर्ध-संक्रमणशील ग्राफ शामिल होंगे, जिन्हें उपरोक्त परिभाषा के तहत बाहर रखा गया है। एक दूरी-सकर्मक ग्राफ वह है जहाँ निकटवर्ती शीर्षों के जोड़े पर विचार करने के बजाय (यानी। 1 की दूरी पर शीर्ष), परिभाषा में शीर्षों के दो जोड़े शामिल हैं, जिनमें से प्रत्येक समान दूरी पर है। परिभाषा के अनुसार इस तरह के ग्राफ स्वचालित रूप से सममित होते हैं। ए को शीर्षों के एक अनुक्रम के रूप में परिभाषित किया गया है, जैसे कि अनुक्रम में कोई भी दो लगातार शीर्ष निकटवर्ती हैं, और किसी भी दोहराए गए शीर्ष के साथ 2 चरणों से अधिक की दूरी है। ग्राफ एक ऐसा ग्राफ है जिस पर ऑटोमोर्फिज्म समूह पारगमनशील रूप से कार्य करता है, लेकिन उस पर नहीं। चूंकि केवल किनारे होते हैं, इसलिए डिग्री 3 या उससे अधिक का प्रत्येक सममित ग्राफ कुछ के लिए होना चाहिए, और के मान का उपयोग सममित ग्राफ को आगे वर्गीकृत करने के लिए किया जा सकता है। उदाहरण के लिए, घन है। ध्यान दें कि पारंपरिक रूप से "सममित ग्राफ" शब्द "असममित ग्राफ" शब्द का पूरक नहीं है, क्योंकि बाद वाला एक ऐसे ग्राफ को संदर्भित करता है जिसमें कोई गैर-तुच्छ समरूपता नहीं है। उदाहरण किसी भी संख्या में शीर्षों के लिए सममित आलेखों के दो बुनियादी परिवार चक्र आलेखों (डिग्री 2 के) और पूर्ण आलेखों हैं। आगे सममित ग्राफ नियमित और क्वासिरेगुलर पॉलीहेड्रा के शीर्षों और किनारों द्वारा बनाए जाते हैंः घन, ऑक्टाहेड्रॉन, आइकोसाहेड्रॉन, डोडेकाहेड्रॉन, क्यूबोक्टेहेड्रॉन और आइकोसिडोडेकाहेड्रॉन। घन का n आयामों तक विस्तार हाइपरक्यूब ग्राफ (2n शीर्ष और डिग्री n के साथ) देता है। इसी तरह ऑक्टाहेड्रॉन का n आयामों तक विस्तार क्रॉस-पॉलीटोप के ग्राफ देता है, ग्राफ के इस परिवार (2n शीर्ष और डिग्री 2n-2 के साथ) को कभी-कभी कॉकटेल पार्टी ग्राफ के रूप में संदर्भित किया जाता है-वे किनारों के एक सेट के साथ पूर्ण ग्राफ होते हैं जो एक सही मिलान को हटा देते हैं। 2n शीर्षों की सम संख्या के साथ सममित आलेखों के अतिरिक्त परिवार, समान रूप से विभाजित पूर्ण द्विदलीय आलेखों Kn, n और 2n शीर्षों पर मुकुट आलेखों हैं। कई अन्य सममित आलेखों को परिसंचारी आलेखों के रूप में वर्गीकृत किया जा सकता है (लेकिन सभी नहीं)। राडो ग्राफ असीम रूप से कई शीर्षों और अनंत डिग्री क्यूबिक सममित ग्राफ के साथ एक सममित ग्राफ का एक उदाहरण बनाता है जो सममित स्थिति को इस प्रतिबंध के साथ जोड़ता है कि ग्राफ क्यूबिक (यानी। सभी शीर्षों की डिग्री 3) काफी मजबूत स्थिति प्रदान करती है, और इस तरह के ग्राफ सूचीबद्ध होने के लिए दुर्लभ हैं। उन सभी में शीर्षों की संख्या सम होती है। पालक जनगणना और इसके विस्तार ऐसी सूचियाँ प्रदान करते हैं। पालनहार जनगणना 1930 के दशक में रोनाल्ड एम. फोस्टर द्वारा शुरू की गई थी, जब वे बेल लैब्स द्वारा कार्यरत थे, और 1988 में (जब पालनहार 92 वर्ष के थे) तत्कालीन वर्तमान पालनहार जनगणना (512 शीर्षों तक के सभी घन सममित आलेखों को सूचीबद्ध करते हुए) पुस्तक के रूप में प्रकाशित की गई थी। सूची में पहले तेरह आइटम 30 शीर्षों के साथ घन सममित ग्राफ हैं (इनमें से दस भी दूरी-सकर्मक हैं; अपवाद संकेत के अनुसार हैं): अन्य प्रसिद्ध घन सममित ग्राफ डाइक ग्राफ, फोस्टर ग्राफ और बिग्स-स्मिथ ग्राफ हैं। ऊपर सूचीबद्ध दस दूरी-संक्रमण ग्राफ, फोस्टर ग्राफ और बिग्स-स्मिथ ग्राफ के साथ, केवल घन दूरी-संक्रमण ग्राफ हैं। गुण एक सममित ग्राफ की शीर्ष-संयोजकता हमेशा डिग्री डी के बराबर होती है। इसके विपरीत, सामान्य रूप से शीर्ष-सकर्मक ग्राफ के लिए, शीर्ष-संयोजकता नीचे 2 (डी + 1)/3 से घिरी होती है। डिग्री 3 या उससे अधिक के टी-ट्रांजिटिव ग्राफ का घेर कम से कम 2 (टी-1) होता है। हालाँकि, टी ≤ 8 के लिए डिग्री 3 या उससे अधिक का कोई परिमित टी-संक्रमक ग्राफ नहीं हैं। डिग्री के ठीक 3 (घन सममित ग्राफ) होने के मामले में, t ≤ 6 के लिए कोई नहीं है। बीजगणितीय ग्राफ सिद्धांत भी देखें नामित ग्राफों की गैलरी नियमित मानचित्र संदर्भ बाहरी लिंक घन सममित ग्राफ (पालक जनगणना)। 768 शीर्षों तक के सभी घन सममित आलेखों के लिए डेटा फाइलें, और 1000 शीर्षों तक के कुछ घन आलेखों के लिए। गॉर्डन रॉयले, फरवरी 2001 में अद्यतन किया गया, 2009-04-18 पुनर्प्राप्त किया गया। 10000 शीर्षों तक त्रिभुज (घन) सममित ग्राफ। मार्स्टन कोंडर, 2011। बीजगणितीय ग्राफ सिद्धांत ग्राफ परिवार नियमित ग्राफ