Folded cube graph
ग्राफ सिद्धांत में, एक मुड़ा हुआ घन ग्राफ एक दिशाहीन ग्राफ है जो एक हाइपरक्यूब ग्राफ से बना है जिसमें एक सही मिलान जोड़ा जाता है जो हाइपरक्यूब शीर्षों के विपरीत जोड़े को जोड़ता है। निर्माण आयाम k (2k−1 शीर्षों वाला) का मुड़ा हुआ घन ग्राफ आयाम k−1 के अति घन ग्राफ में शीर्षों के विपरीत जोड़े के बीच किनारों को जोड़कर बनाया जा सकता है। (2n शीर्षों वाले एक हाइपरक्यूब में, शीर्षों की एक जोड़ी विपरीत होती है यदि उनके बीच के सबसे छोटे पथ की लंबाई n हो।) यह, समान रूप से, आयाम k के एक हाइपरक्यूब ग्राफ (भी) से बनाया जा सकता है, जिसमें दो गुना अधिक शीर्ष होते हैं, शीर्षों की प्रत्येक विपरीत जोड़ी को एक साथ पहचानकर (या संकुचित करके)। गुण एक आयाम-के मुड़ा हुआ घन ग्राफ 2k−1 शीर्षों और 2k−2k किनारों के साथ एक के-नियमित है। आयाम-k मुड़े हुए घन ग्राफ की वर्णात्मक संख्या दो होती है जब k सम होता है (यानी, इस मामले में, ग्राफ द्विदलीय होता है) और चार जब k विषम होता है। विषम आयाम के मुड़े हुए घन का विषम परिधि k है, इसलिए तीन से अधिक विषम k के लिए मुड़े हुए घन ग्राफ रंगीन संख्या चार और मनमाने ढंग से बड़े विषम परिधि के साथ त्रिभुज-मुक्त ग्राफ का एक वर्ग प्रदान करते हैं। विषम परिधि k और व्यास (k−1)/2 के साथ एक दूरी-नियमित ग्राफ के रूप में, विषम आयाम के मुड़े हुए घन सामान्यीकृत विषम ग्राफ के उदाहरण हैं। जब k विषम होता है, तो आयाम-k मुड़े हुए घन का द्विदलीय दोहरा आवरण वह आयाम-k घन होता है जिससे यह बना था। हालाँकि, जब k सम होता है, तो आयाम-k घन एक दोहरा आवरण होता है लेकिन द्विदलीय दोहरा आवरण नहीं होता है। इस मामले में, मुड़ा हुआ घन पहले से ही द्विदलीय है। फोल्डेड क्यूब ग्राफ अपने हाइपरक्यूब सबग्राफ से हैमिल्टनियन चक्र होने का गुण विरासत में प्राप्त करते हैं, और हाइपरक्यूब से जो उन्हें दूरी-सकर्मक ग्राफ होने का गुण दो बार कवर करते हैं। जब k विषम होता है, तो आयाम-k मुड़े हुए घन में 2k−1 नोड्स के साथ एक पूर्ण द्विआधारी वृक्ष उपग्राफ के रूप में होता है। हालाँकि, जब k सम होता है, तो यह संभव नहीं है, क्योंकि इस मामले में मुड़ा हुआ घन एक द्विदलीय ग्राफ है जिसमें द्विदलीय विभाजन के प्रत्येक तरफ समान संख्या में शीर्ष होते हैं, जो एक पूर्ण द्विदलीय वृक्ष के द्विदलीय विभाजन के लिए लगभग दो-से-एक अनुपात से बहुत अलग होता है। उदाहरण आयाम तीन का मुड़ा हुआ घन ग्राफ एक पूर्ण ग्राफ K4 है। आयाम चार का मुड़ा हुआ घन ग्राफ पूर्ण द्विदलीय ग्राफ K4,4 है। आयाम पाँच का मुड़ा हुआ घन ग्राफ क्लेबश ग्राफ है। आयाम छह का मुड़ा हुआ घन ग्राफ कुम्मर ग्राफ है, अर्थात। कुमेर बिंदु-तल विन्यास का लेवी ग्राफ। अनुप्रयोग समानांतर संगणना में, हाइपरक्यूब के विकल्प के रूप में, एक संभावित नेटवर्क टोपोलॉजी के रूप में मुड़े हुए घन ग्राफ का अध्ययन किया गया है। एक हाइपरक्यूब की तुलना में, समान संख्या में नोड्स के साथ एक मुड़े हुए क्यूब में लगभग समान शीर्ष डिग्री होती है लेकिन व्यास का केवल आधा होता है। कुशल वितरित एल्गोरिदम (एक हाइपरक्यूब के लिए उन लोगों के सापेक्ष) एक मुड़े हुए घन में जानकारी प्रसारित करने के लिए जाने जाते हैं। आधा घन ग्राफ नोट्स संदर्भ भी देखें। .. .. .. .. .. बाहरी लिंक ग्राफ के पैरामीट्रिक परिवार नियमित ग्राफ